Verificador de Grafos Planares — Teste Se um Grafo Pode Ser Desenhado Sem Cruzamentos
Nosso Verificador de Grafos Planares testa se um grafo poderia potencialmente ser desenhado em um plano sem que nenhuma aresta se cruze, aplicando a condição necessária de contagem de arestas (E ≤ 3V − 6, ajustada para E ≤ 2V − 4 para grafos bipartidos) e, para grafos de 8 ou menos vértices, uma busca explícita por um subgrafo K₅ ou K₃,₃ — qualquer um dos quais prova definitivamente a não planaridade pelo teorema de Kuratowski.
Resposta rápida
Digite seu grafo como uma lista de arestas para verificar a condição necessária de contagem de arestas e buscar subgrafos proibidos K₅/K₃,₃ — uma verificação de planaridade forte, mas não totalmente exaustiva.
Digite arestas como NóA-NóB, ex. A-B, A-C, A-D, B-C, B-D, C-D.
Como usar Verificador de Grafos Planares — Teste Estilo Kuratowski Online
- 1
Digite seu grafo como uma lista de arestas separadas por vírgula, ex. A-B, A-C, A-D, B-C, B-D, C-D.
- 2
Clique em 'Calcular' para verificar as condições necessárias e buscar subgrafos proibidos.
- 3
Revise o veredito — 'definitivamente não planar' ou 'provavelmente planar (inconclusivo)' — e as etapas de raciocínio.
Por que usar Verificador de Grafos Planares — Teste Estilo Kuratowski Online?
Um grafo é planar se pode ser desenhado em um plano sem que duas arestas se cruzem. O teorema de Kuratowski dá uma caracterização exata: um grafo é não planar se e somente se contém uma subdivisão de K₅ (o grafo completo de 5 vértices) ou K₃,₃ (o grafo bipartido completo de dois grupos de 3). Detectar completamente subdivisões ou menores desses grafos requer algoritmos sofisticados (como Boyer-Myrvold) muito além do que uma calculadora do lado do cliente pode executar instantaneamente — então esta ferramenta adota uma abordagem de escopo transparente em vez disso: sempre verifica o limite necessário de contagem de arestas (uma forma rápida e exata de descartar muitos grafos não planares), e para grafos pequenos (8 ou menos vértices) também busca diretamente K₅ ou K₃,₃ aparecendo como subgrafos literais. Encontrar qualquer um deles prova a não planaridade conclusivamente; não encontrar nenhum é um forte indício de planaridade, mas não uma prova completa, já que não detectará cópias subdivididas (com arestas expandidas) desses grafos proibidos.
Perguntas frequentes
Ferramentas relacionadas
Validador de Sequência de Graus de Grafo — Teorema de Erdős–Gallai Online
Verifique se uma sequência de números é uma sequência de graus válida (gráfica) usando o teorema de Erdős–Gallai. Calculadora gratuita com verificação passo a passo.
Calculadora de Coloração de Grafos — Algoritmo de Welsh-Powell Online
Colora os vértices de um grafo de modo que nenhum dois nós conectados compartilhem uma cor, usando o algoritmo guloso de Welsh-Powell. Calculadora gratuita com uma entrada simples de lista de arestas.
Calculadora de Matriz de Adjacência — Construa uma Matriz de Grafo Online
Construa e exiba a matriz de adjacência de um grafo a partir de uma entrada simples de lista de arestas, junto com sua sequência de graus. Calculadora gratuita, ponderada ou não ponderada.