Teorema de Kuratowski

Teorema de Kuratowski

En teoría de grafos, el teorema de Kuratowski, desarrollado por el matemático polaco Kazimierz Kuratowski, es una caracterización de los grafos planares.

Definición

K5
K3,3

Un grafo es planar si y sólo si no contiene un subgrafo que es subdivisión elemental de K5 (el grafo completo de 5 vértices) o K3,3 (el grafo bipartito completo de 6 vértices)

Una subdivisión elemental de un grafo resulta de insertar vértices en las aristas (por ejemplo, cambiando •——• por •—•—•). Una formulación equivalente a este teorema es:

Un grafo es planar si y sólo si no contiene ningún subgrafo homeomorfo a K5 ó K3,3.

Ejemplo

K6

¿El grafo K6 completo puede ser plano?

Se puede observar que el grafo K6 contiene como subgrafo un K5. Por el Teorema de Kuratowski se puede afirmar que el grafo K6 no es planar.


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Kazimierz Kuratowski — Kazimierz Kuratowski. Kazimierz Kuratowski (Varsovia, 2 de febrero de 1896 18 de junio de 1980) fue un matemático y lógico polaco. Contenido 1 Biografía …   Wikipedia Español

  • Grafo plano — Grafos de ejemplo Plano No plano …   Wikipedia Español

  • Grafo completo — K7, grafo completo de 7 vértices. Vértices n Aristas …   Wikipedia Español

  • Axiomas de Zermelo-Fraenkel — Los axiomas de Zermelo Fraenkel, formulados por Ernst Zermelo y Adolf Fraenkel, son un sistema axiomático concebido para formular la teoría de conjuntos. Normalmente se abrevian como ZF o en su forma más común, complementados por el axioma de… …   Wikipedia Español

  • Teoría de grafos — Diagrama de un grafo con 6 vértices y 7 aristas. En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un… …   Wikipedia Español

  • Lema de Zorn — El lema de Zorn, también llamado de Kuratowski Zorn, es una proposición de la teoría de conjuntos que afirma lo siguiente: Todo conjunto parcialmente ordenado no vacío en el que toda cadena (subconjunto totalmente ordenado) tiene una cota… …   Wikipedia Español

  • Funtores adjuntos — La existencia de muchos pares de funtores adjuntos es una observación importante de la rama de la matemática conocida como teoría de categorías. (La teoría de categorías continúa en cierta forma la visión estructuralista en matemática; ver… …   Wikipedia Español

  • Lema de Zorn — El lema de Zorn, también conocido como el lema de Kuratowski Zorn, es un teorema en teoría de conjuntos que establece que: Todo conjunto parcialmente ordenado en el que toda cadena (es decir, subconjunto totalmente ordenado) tiene un límite… …   Enciclopedia Universal

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”