Verificador de Grafos Planares — Comprueba Si un Grafo Se Puede Dibujar Sin Cruces
Nuestro Verificador de Grafos Planares comprueba si un grafo podría potencialmente dibujarse en un plano sin que se crucen las aristas, aplicando la condición necesaria de conteo de aristas (E ≤ 3V − 6, ajustada a E ≤ 2V − 4 para grafos bipartitos) y, para grafos de 8 vértices o menos, una búsqueda explícita de un subgrafo K₅ o K₃,₃ — cualquiera de los cuales prueba definitivamente la no planaridad según el teorema de Kuratowski.
Respuesta rápida
Introduce tu grafo como una lista de aristas para comprobar la condición necesaria de conteo de aristas y buscar subgrafos prohibidos K₅/K₃,₃ — una comprobación de planaridad sólida pero no completamente exhaustiva.
Introduce aristas como NodoA-NodoB, p. ej. A-B, A-C, A-D, B-C, B-D, C-D.
Cómo usar Verificador de Grafos Planares — Prueba Estilo Kuratowski Online
- 1
Introduce tu grafo como una lista de aristas separadas por comas, p. ej. A-B, A-C, A-D, B-C, B-D, C-D.
- 2
Haz clic en 'Calcular' para comprobar las condiciones necesarias y buscar subgrafos prohibidos.
- 3
Revisa el veredicto — 'definitivamente no planar' o 'probablemente planar (no concluyente)' — y los pasos de razonamiento.
¿Por qué usar Verificador de Grafos Planares — Prueba Estilo Kuratowski Online?
Un grafo es planar si se puede dibujar en un plano plano sin que se crucen dos aristas. El teorema de Kuratowski da una caracterización exacta: un grafo es no planar si y solo si contiene una subdivisión de K₅ (el grafo completo de 5 vértices) o K₃,₃ (el grafo bipartito completo de dos grupos de 3). Detectar completamente subdivisiones o menores de estos grafos requiere algoritmos sofisticados (como Boyer-Myrvold) mucho más allá de lo que una calculadora del lado del cliente puede ejecutar al instante — así que esta herramienta adopta un enfoque de alcance transparente en su lugar: siempre comprueba la cota necesaria de conteo de aristas (una forma rápida y exacta de descartar muchos grafos no planares), y para grafos pequeños (8 vértices o menos) además busca directamente K₅ o K₃,₃ apareciendo como subgrafos literales. Encontrar cualquiera de ellos prueba la no planaridad concluyentemente; no encontrar ninguno es un fuerte indicio de planaridad pero no una prueba completa, ya que no detectará copias subdivididas (con aristas expandidas) de estos grafos prohibidos.
Preguntas frecuentes
Herramientas relacionadas
Validador de Secuencia de Grados de Grafo — Teorema de Erdős–Gallai Online
Comprueba si una secuencia de números es una secuencia de grados válida (gráfica) usando el teorema de Erdős–Gallai. Calculadora gratuita con verificación paso a paso.
Calculadora de Coloreado de Grafos — Algoritmo de Welsh-Powell Online
Colorea los vértices de un grafo para que no compartan color dos nodos conectados, usando el algoritmo voraz de Welsh-Powell. Calculadora gratuita con una entrada simple de lista de aristas.
Calculadora de Matriz de Adyacencia — Construye una Matriz de Grafo Online
Construye y muestra la matriz de adyacencia de un grafo a partir de una entrada simple de lista de aristas, junto con su secuencia de grados. Calculadora gratuita, ponderada o no ponderada.