Verificador de Grafo Planar

Verificador de Grafo Planar

El Verificador de Grafo Planar decide si un grafo simple no dirigido es planar — dibujable en el plano sin que dos aristas se crucen — y, cuando el grafo falla la prueba, encuentra y visualiza el testigo de Kuratowski: una subdivisión de K₅ (el grafo completo de 5 vértices) o K₃,₃ (el grafo bipartito completo de 3 + 3 vértices). La herramienta está diseñada para la enseñanza, calentamientos de programación competitiva y para verificar rápidamente la cordura de construcciones de grafos pequeños.

¿Qué significa "planar"?

Un grafo G = (V, E) es planar si puede incrustarse en el plano de modo que las aristas se encuentren solo en sus extremos compartidos, sin cruces. Equivalentemente, G puede dibujarse en la superficie de una esfera sin cruces. La planaridad es una propiedad puramente topológica: no depende de cómo se dibuje el grafo, sino de si existe algún dibujo sin cruces.

Los grafos planares aparecen en todas partes: redes de carreteras y servicios públicos, enrutamiento de placas de circuito impreso, los grafos de aristas de sólidos platónicos y la estructura de caras de poliedros. Sin embargo, muchos grafos "naturales" son obstinadamente no planares: cada vez que intenta conectar 3 casas a 3 servicios públicos sin cruces, se encuentra con la barrera K₃,₃.

Teorema de Kuratowski: el corazón del verificador

Kazimierz Kuratowski demostró en 1930 que la planaridad tiene una caracterización puramente combinatoria:

Una subdivisión de un grafo H se obtiene reemplazando algunas aristas de H con caminos más largos cuyos vértices internos son todos nuevos vértices de grado 2. El teorema de Kuratowski, por lo tanto, dice que K₅ y K₃,₃ son las únicas obstrucciones a la planaridad; cada grafo no planar contiene uno de ellos en una forma "estirada".

Los grafos prohibidos

Fórmula de Euler y condiciones necesarias rápidas

Antes de ejecutar la búsqueda de subdivisión (relativamente costosa), el verificador aplica dos condiciones necesarias rápidas derivadas de la fórmula de Euler: para cualquier grafo planar conexo dibujado en el plano con V vértices, E aristas y F caras (contando la cara exterior no acotada), tenemos

Combinado con la observación de que cada cara de un grafo planar simple tiene al menos 3 aristas en su límite, obtenemos el límite superior de aristas

Cualquier grafo que viole estas desigualdades es inmediatamente no planar, sin necesidad de búsqueda de subdivisión. K₅ tiene m = 10, n = 5 ⇒ 3n − 6 = 9, por lo que 10 > 9 — viola el límite. K₃,₃ tiene m = 9, n = 6 ⇒ 2n − 4 = 8, por lo que 9 > 8 — viola el límite bipartito.

Cómo funciona la búsqueda de subdivisiones

Después de las comprobaciones rápidas de Euler, el verificador busca una subdivisión directamente:

1. Victoria rápida: detectar K₅ o K₃,₃ como un subgrafo literal. Si 5 vértices son adyacentes por pares, eso es K₅ directamente. Si 6 vértices se dividen 3 + 3 con las 9 aristas cruzadas presentes, eso es K₃,₃.
2. Búsqueda de subdivisión K₅. Para cada conjunto de candidatos de 5 vértices "rama" (cada uno con grado ≥ 4 en G), intenta encontrar 10 caminos — uno por par de ramas — que sean internamente disjuntos en vértices (ningún vértice que no sea rama aparece en más de un camino) y evita usar las otras ramas como vértices internos. Un acierto prueba la no planaridad.
3. Búsqueda de subdivisión K₃,₃. Elige 6 ramas (cada una con grado ≥ 3) y una bipartición 3 + 3. Busca 9 caminos de pares cruzados con el mismo requisito de disyunción interna.
4. Sin testigo ⇒ planar. Si no se encuentra ninguna subdivisión dentro de los límites de tamaño, el teorema de Kuratowski garantiza que el grafo es planar.

Encontrar caminos disjuntos en vértices es NP-duro en general, por lo que el verificador utiliza una búsqueda codiciosa aleatoria acotada: cada iteración ordena los pares requeridos por dificultad, elige primero un camino para el par más difícil mediante un BFS aleatorio, elimina esos vértices internos y continúa. Si ese orden en particular falla, vuelve a intentarlo con un orden barajado — hasta 40 intentos por configuración de rama. En cada grafo pequeño probado (hasta 16 vértices), esto es suficiente para localizar un testigo siempre que exista uno.

Cómo usar esta calculadora

1. Elija un formato de entrada usando las pestañas en la parte superior: lista de aristas o lista de adyacencia. Ambos codifican el mismo grafo.
2. Ingrese su grafo. El grafo se trata como no dirigido, por lo que A-B y B-A son la misma arista.
3. Haga clic en Verificar Planaridad. La herramienta informa un veredicto, muestra el razonamiento paso a paso (Euler, bipartito, Kuratowski) y renderiza el grafo.
4. Para un grafo no planar, la visualización colorea la subdivisión K₅ o K₃,₃ y enumera los 10 (o 9) caminos disjuntos en vértices. Haga clic en una fila de camino para aislarlo.
5. Para un grafo planar, el recuento de caras F = m − n + 1 + c se informa junto con la estructura del grafo.

Ejemplo práctico 1: K₄ es planar

K₄ tiene n = 4, m = 6. Todo grafo con ≤ 4 vértices es planar y, de hecho, K₄ se incrusta como un triángulo con un único vértice interior conectado a las tres esquinas. Euler dice F = 6 − 4 + 2 = 4 caras: tres caras interiores triangulares más la cara exterior.

Ejemplo práctico 2: K₃,₃ es no planar

K₃,₃ tiene n = 6, m = 9. Es bipartito, por lo que se aplica el límite bipartito: m = 9 > 2n − 4 = 8. Solo esto ya demuestra la no planaridad. El testigo es trivial: K₃,₃ es en sí mismo el subgrafo prohibido. La herramienta resalta entonces la partición 3 + 3 y las 9 aristas directas.

Ejemplo práctico 3: El grafo de Petersen

El grafo de Petersen tiene n = 10, m = 15, por lo que m ≤ 3n − 6 = 24 y las comprobaciones rápidas de Euler pasan. Sin embargo, es famoso por no ser planar. El verificador localiza una subdivisión K₃,₃: elija seis vértices del pentágono exterior y del pentagrama interior de modo que cada par cruzado pueda enrutarse a través de los cuatro vértices restantes mediante caminos disjuntos en vértices. La herramienta dibuja el testigo, haciendo tangible la geometría de los años 30.

Aplicaciones de la planaridad

• Enrutamiento VLSI y PCB. Un circuito de una sola capa es factible solo si el grafo de conexión es planar; las redes no planares obligan a usar vías o capas adicionales.
• Dibujo y visualización de grafos. Los grafos planares admiten diseños claros y sin cruces, útiles para mapas de metro, grafos de llamadas y diagramas esquemáticos.
• Diseño de algoritmos. Muchos problemas NP-duros (corte máximo, cobertura de vértices, isomorfismo de grafos) pasan a ser de tiempo polinomial cuando se restringen a grafos planares.
• Coloración de grafos. El teorema de los cuatro colores garantiza que todo grafo planar es coloreable con 4 colores, un resultado clásico cuyo enunciado depende de la planaridad.
• Optimización combinatoria. El camino más corto planar, el flujo máximo y el corte mínimo admiten algoritmos rápidos especializados.
• Química molecular. Los grafos de hidrocarburos aromáticos de anillo de benceno son planares; ciertas moléculas de jaula no lo son.

Preguntas frecuentes

¿Qué significa que un grafo sea planar?

Un grafo es planar si se puede dibujar en el plano de modo que no haya dos aristas que se crucen excepto en los vértices compartidos. Equivalentemente, un grafo es planar si y solo si se puede dibujar en la superficie de una esfera sin cruces. Los árboles, los ciclos, el grafo del cubo y los sólidos platónicos son todos planares, mientras que K₅ y K₃,₃ son los ejemplos canónicos no planares.

¿Qué es el teorema de Kuratowski?

El teorema de Kuratowski establece que un grafo finito es planar si y solo si no contiene ningún subgrafo que sea una subdivisión de K₅ o K₃,₃. Una subdivisión se obtiene reemplazando algunas aristas por caminos más largos, cada uno a través de nuevos vértices de grado 2. Esto proporciona un certificado combinatorio concreto de no planaridad.

¿Cuál es la diferencia entre K₅ y K₃,₃?

K₅ tiene 5 vértices, cada par de los cuales está unido por una arista, para un total de 10 aristas. K₃,₃ tiene 6 vértices divididos en dos grupos de 3, con cada vértice de un grupo conectado a cada vértice del otro, para 9 aristas. Ambos son los grafos no planares más pequeños de su tipo, y juntos forman los menores prohibidos para la planaridad.

¿Cómo ayuda la desigualdad de Euler?

La fórmula de Euler V − E + F = 2 para grafos conexos planares combinada con el hecho de que cada cara de un grafo planar simple tiene al menos 3 aristas produce m ≤ 3n − 6. Cualquier grafo simple que viole este límite es inmediatamente no planar. Para grafos planares bipartitos, cada cara tiene al menos 4 aristas, lo que da el límite más estricto m ≤ 2n − 4. El verificador aplica ambos como reglas de rechazo rápido.

¿Cuál es el límite de tamaño?

El verificador maneja hasta 16 vértices y 60 aristas. Esto cubre grafos típicos de enseñanza y de estilo de competencia, incluyendo el grafo de Petersen, el grafo de Möbius-Kantor, pequeños hipercubos y el grafo completo K₇. Los grafos más grandes requieren pruebas especializadas de planaridad en tiempo lineal como Hopcroft-Tarjan o planaridad izquierda-derecha.

¿Cómo se dibuja la subdivisión testigo?

Cuando el grafo no es planar, los 5 vértices rama del K₅ encontrado — o los 6 vértices rama de K₃,₃ divididos en dos triples A y B — se resaltan en un anillo interior. Los 10 (o 9) caminos internamente disjuntos en vértices requeridos se dibujan cada uno en un color distinto para que pueda rastrear visualmente la topología de K₅ o K₃,₃. Los vértices y aristas que no forman parte de la subdivisión se atenúan.

Lectura adicional

• Grafo planar — Wikipedia
• Teorema de Kuratowski — Wikipedia
• Característica de Euler — Wikipedia
• Grafo de Petersen — Wikipedia
• Teorema de Wagner (versión menor) — Wikipedia