Grafo plano

Grafo plano
Grafos de ejemplo
Plano No plano
6n-graf.svg
K5
El grafo completo K4 es plano
K3,3

Contenido

Definición y ejemplos

En teoría de grafos, un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se interseque (una definición más formal puede ser que este grafo pueda ser "embebido" en un plano). Un grafo no es plano si no puede ser dibujado sobre un plano sin que sus aristas se intersequen. Los grafos K5 y el K3,3 son los grafos no planos minimales, lo cual nos permitirán caracterizar el resto de los grafos no planos.

Teorema de Kuratowski

El matemático polaco Kazimierz Kuratowski encontró una caracterización de los grafos planos, conocida como el teorema de Kuratowski:

Un grafo es plano si y solo si no contiene un subgrafo que es una 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 plano sí y solo sí no contiene ningún subgrafo homeomorfo a K5 ó K3,3.

Otros criterios para determinar si un grafo es plano

En la práctica, es difícil usar el teorema de Kuratowski para decidir rápidamente si un grafo es plano. Sin embargo, existe un algoritmo rápido para este problema: dado un grafo de n vértices y e el número de aristas, es posible determinar en tiempo O(n) (lineal) si el grafo es plano o no, utilizando los dos teoremas siguientes:

Teorema 1. Si n ≥ 3 entonces e ≤ 3n - 6
Teorema 2. Si n > 3 y no existen ciclos de longitud 3, entonces e ≤ 2n - 4

El grafo K3,3, por ejemplo, tiene 6 vértices, 9 aristas y ningún ciclo de longitud 3. Por el teorema 2, no puede ser plano. Nótese que estos teoremas están construidos con una implicación unidireccional (si), y no bicondicional (si y solo si) y por tanto, solamente pueden ser usados para probar que el grafo no es plano, pero no que sea plano. Si ambos teoremas fallan, deben usarse otros métodos.

Fórmula de Euler

La fórmula de Euler enuncia que si un grafo conexo, plano es dibujado sobre un plano sin intersección de aristas, y siendo v el número de vértices, e el de aristas y f la cantidad de caras (regiones conectadas por aristas, incluyendo la región externa e infinita), entonces:

ve + f = 2,

Por ejemplo, la Característica de Euler es 2. De manera más ilustrativa, en los ejemplos anteriores, en el primer grafo plano tenemos: v=6, e=7 y f=3. Si el segundo grafo se redibuja sin las intersecciones de aristas, tenemos v=4, e=6 y f=4. La fórmula de Euler se puede probar de la siguiente manera: si el grafo no es un árbol, entonces se elimina una arista que completa un ciclo. Esto disminuye el valor de e y f en uno, dejando ve + f constante. Repítase hasta llegar a un árbol. Los árboles tienen v = e + 1 y f = 1, verificando la fórmula v - e + f = 2.

En un grafo simple, conexo y plano, cualquier región (posiblemente exceptuando la exterior) está conectada por al menos tres aristas y cada arista toca como mucho dos regiones. Usando la fórmula de Euler, se puede demostrar que estos grafos son escasos en el sentido que e ≤ 3v - 6 si v ≥ 3.

Se le dice plano maximal al grafo que es plano pero al agregarle cualquier arista dejase de serlo. Todas las regiones (incluso la externa) están conectadas por tres aristas, explicando la definición alternativa de triangular para este tipo de grafos. Si un grafo triangular tiene v vértices con v > 2, entonces tiene exactamente 3v - 6 aristas y 2v - 4 regiones.

Nótese que la fórmulta de Euler también es válida para poliedros simples. No es una casualidad: cada poliedro simple se puede ver como un grafo plano y conexo usando los vértices del poliedro como vértices del grafo, y las aristas del poliedro como aristas del grafo. Las caras o regiones del grafo plano resultante corresponden a las caras del poliedro. Por ejemplo, el segundo grafo plano del ejemplo corresponde a un tetraedro. Alternativamente, no todos los grafos planos y simples corresponden a un poliedro (los árboles, por ejemplo). Un teorema de Ernst Steinitz dice que los grafos planos formados a partir de poliedros convexos son precisamente los grafos planos simples y triangulares.


Referencias

  • Kazimierz Kuratowski (1930), 'Sur le problème des courbes gauches en topologie', Fund. Math., 15, pp. 271-283.
  • K. Wagner (1937), 'Über eine Eigenschaft der ebenen Komplexe', Math. Ann. 114, pp. 570–590.
  • John M. Boyer and Wendy J. Myrvold (2005), 'On the cutting edge: Simplified O(n) planarity by edge addition'. Journal of Graph Algorithms and Applications, vol. 8 no. 3, pp. 241-273. En inglés.
  • Brendan McKay & Gunnar Brinkmann, Generador de grafos planos

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Grafo — Para otros usos de este término, véase Grafo (desambiguación). Para la teoría en torno a este objeto matemático, véase Teoría de grafos. Grafo etiquetado con 6 vértices y 7 aristas. En matemáticas y ciencias de la computación, un grafo (del …   Wikipedia Español

  • Grafo cuadrado — Un grafo cuadrado. En teoría de grafos, un grafo cuadrado es un grafo no dirigido que puede dibujarse en el plano de modo que cada superficie acotada es un cuadrilátero y cada vértice con tres o menos vecinos es incidente a una cara no acotada.… …   Wikipedia Español

  • Grafo de una función — Si f:A → B es una función, su grafo es el conjunto formado por todos los pares ordenados (a, f(a)) y es, por tanto, subconjunto del producto cartesiano …   Enciclopedia Universal

  • Anexo:Glosario de teoría de grafos — Grafo simple no dirigido, con 6 vértices y 7 aristas. A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal correspondiente. Todos los… …   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

  • Coloración de grafos — Una vértice coloración propia del grafo de Petersen con 3 colores, el número mínimo posible. En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del …   Wikipedia Español

  • Glosario en teoría de grafos — Anexo:Glosario en teoría de grafos Saltar a navegación, búsqueda Grafo con 6 nodos A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal …   Wikipedia Español

  • Árbol (teoría de grafos) — Para otros usos de este término, véase Árbol (desambiguación). Árbol Árbol etiquetado con 6 vértices y 5 aristas. El único camino simple que conecta los vértices 2 y 6 es 2 4 5 6 …   Wikipedia Español

  • Poliedro dual — Saltar a navegación, búsqueda El octaedro y el cubo son poliedros duales. Poliedro dual o conjugado, en geometría, es el poliedro cuyos vértices se corresponden con el centro de las cara del otro poliedro dado. El poliedro dual del dual es… …   Wikipedia Español

  • Estrella (figura geométrica) — Saltar a navegación, búsqueda Esta figura tiene todos sus vértices conectados. Puede trazarse sin levantar el lápiz …   Wikipedia Español

Compartir el artículo y extractos

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