15/09/2021
En teoría de grafos, una gráfica plana, también conocida como grafo planar, es un grafo que puede dibujarse en un plano sin que ninguna de sus aristas se crucen. Esta definición, aunque intuitiva, requiere una formalización más rigurosa que implica la posibilidad de incrustar el grafo en un plano.
Grafos Planos vs. Grafos No Planos
No todos los grafos son planos. Algunos ejemplos de grafos no planos minimalesson el K 5 (grafo completo de 5 vértices) y el K 3,3 (grafo bipartito completo de 3 vértices en cada partición). Estos grafos sirven como base para identificar otros grafos no planos.
Es importante destacar que un grafo plano puede dibujarse en una esfera sin que se crucen las aristas, y viceversa. Esta equivalencia se extiende a la generalización de grafos incrustados en superficies de género arbitrario, donde los grafos planos poseen género 0.
El Teorema de Kuratowski : Una Caracterización Fundamental
El matemático polaco Kazimierz Kuratowski proporcionó una caracterización fundamental de los grafos planos a través de su teorema:
Un grafo es plano si y solo si no contiene ningún subgrafo homeomorfo a K 5 o K 3,3 .
Un subgrafo homeomorfo se obtiene mediante subdivisiones elementales: insertar vértices en las aristas. Este teorema, aunque elegante, no resulta práctico para determinar rápidamente si un grafo es plano.
Algoritmos para la Planaridad
Existen algoritmos eficientes para determinar la planaridad de un grafo. Dados nvértices y aaristas, es posible determinar en tiempo lineal O(n) si un grafo es plano. Estos algoritmos se basan en los siguientes teoremas:
Teorema 1
Si G es un grafo plano con n ≥ 3 vértices, entonces a ≤ 3n -
Demostración (esquema):Se considera un grafo plano triangular (maximal). Usando la fórmula de Euler (v - a + c = 2, donde v son vértices, a aristas y c caras), y la relación entre aristas y caras en un grafo triangular (3c ≤ 2a), se deduce la desigualdad a ≤ 3v -
Teorema 2
Si n > 3 y no existen ciclos de longitud 3, entonces a ≤ 2n -
Demostración (esquema):Para un grafo plano libre de triángulos, se utiliza la fórmula de Euler y la condición de que cada cara tiene al menos 4 aristas (2a ≥ 4c). La combinación de estas relaciones lleva a a ≤ 2v -
Nota: Estos teoremas proporcionan una condición suficiente pero no necesaria para la planaridad. Si un grafo no cumple estas desigualdades, entonces no es plano; pero si las cumple, se requieren métodos adicionales para confirmar su planaridad.
La Fórmula de Euler : Una Relación Fundamental
La fórmula de Euler establece una relación fundamental entre el número de vértices (v), aristas (a) y caras (c) de un grafo plano conexo:
v - a + c = 2
Esta fórmula es crucial en la demostración de los teoremas de planaridad y tiene aplicaciones en diversas áreas, incluyendo la geometría y la topología. La fórmula de Euler también se aplica a poliedros simples, ya que todo poliedro simple puede representarse como un grafo plano conexo.
Aplicaciones de los Grafos Planares
Los grafos planos tienen aplicaciones en diversas áreas, incluyendo:
- Diseño de circuitos integrados: Minimizar cruces de cables.
- Cartografía: Colorear mapas.
- Química: Representación de moléculas.
- Redes de comunicación: Diseño de redes eficientes.
Grafos Planares Maximales
Un grafo planar maximal es un grafo plano al que no se le puede agregar ninguna arista sin perder la planaridad. En un grafo planar maximal, todas las regiones (incluyendo la región exterior) están limitadas por tres aristas. Estos grafos tienen exactamente 3v - 6 aristas y 2v - 4 regiones (para v > 2).
Conclusión
La teoría de grafos planares es un campo rico y complejo con aplicaciones en diversas áreas. Comprender los conceptos de planaridad, los teoremas de Kuratowski y la fórmula de Euler, así como los algoritmos de detección de planaridad, es esencial para cualquier estudiante o profesional interesado en la teoría de grafos y sus aplicaciones.
Consultas Habituales sobre Gráficas Planas
A continuación, se responden algunas consultas habituales sobre gráficas planas:
¿Cómo puedo determinar si un grafo es planar?
Puedes utilizar el teorema de Kuratowski, buscar subgrafos homeomorfos a K 5o K 3,3. Sin embargo, para grafos grandes, es más eficiente utilizar algoritmos de detección de planaridad basados en los teoremas presentados anteriormente.
¿Cuál es la importancia de la fórmula de Euler en el contexto de gráficas planas?
La fórmula de Euler proporciona una relación fundamental entre el número de vértices, aristas y caras de un grafo plano conexo. Esta relación es crucial para la demostración de varios teoremas de planaridad y tiene implicaciones en otras áreas de las matemáticas.
¿Qué aplicaciones tienen las gráficas planas en el entorno real?
Las gráficas planas se aplican en el diseño de circuitos, la cartografía, la química, las redes de comunicación y otras áreas donde la minimización de cruces o la representación eficiente de datos es importante.
¿Qué es un grafo planar maximal?
Un grafo planar maximal es un grafo plano al cual no se le puede agregar ninguna arista sin perder la propiedad de planaridad.