Verificador de Grafo Planar

Verificador de Grafo Planar

O Verificador de Grafo Planar decide se um grafo simples não direcionado é planar — desenhável no plano sem que duas arestas se cruzem — e, quando o grafo falha no teste, ele encontra e visualiza o testemunho de Kuratowski: uma subdivisão de K₅ (o grafo completo em 5 vértices) ou K₃,₃ (o grafo bipartido completo em 3 + 3 vértices). A ferramenta foi construída para o ensino, aquecimento de programação competitiva e para verificação rápida de sanidade de pequenas construções de grafos.

O que significa "Planar"?

Um grafo G = (V, E) é planar se puder ser mergulhado no plano de modo que as arestas se encontrem apenas em seus pontos finais compartilhados — sem cruzamentos. Equivalentemente, G pode ser desenhado na superfície de uma esfera sem cruzamentos. A planaridade é uma propriedade puramente topológica: não depende de como você desenha o grafo, mas apenas se algum desenho livre de cruzamentos existe.

Grafos planares aparecem em todos os lugares — redes de estradas e serviços públicos, roteamento de placas de circuito impresso, os grafos de arestas dos sólidos Platônicos e a estrutura de faces de poliedros. No entanto, muitos grafos "naturais" são obstinadamente não-planares: toda vez que você tenta conectar 3 casas a 3 serviços públicos sem cruzamentos, você se depara com a barreira K₃,₃.

Teorema de Kuratowski — O Coração do Verificador

Kazimierz Kuratowski provou em 1930 que a planaridade tem uma caracterização puramente combinatória:

Uma subdivisão de um grafo H é obtida substituindo algumas arestas de H por caminhos mais longos cujos vértices internos são todos novos vértices de grau 2. O teorema de Kuratowski, portanto, diz que K₅ e K₃,₃ são as únicas obstruções à planaridade — todo grafo não-planar contém um deles em uma forma "esticada".

Os Grafos Proibidos

Fórmula de Euler e Condições Necessárias Rápidas

Antes de executar a busca por subdivisão (relativamente cara), o verificador aplica duas condições necessárias rápidas derivadas da fórmula de Euler: para qualquer grafo planar conexos desenhado no plano com V vértices, E arestas e F faces (contando a face externa ilimitada), temos

Combinado com a observação de que cada face de um grafo planar simples tem pelo menos 3 arestas em seu limite, obtemos o limite superior de arestas

Qualquer grafo que viole essas desigualdades é imediatamente não-planar, sem necessidade de busca por subdivisão. K₅ tem m = 10, n = 5 ⇒ 3n − 6 = 9, logo 10 > 9 — viola o limite. K₃,₃ tem m = 9, n = 6 ⇒ 2n − 4 = 8, logo 9 > 8 — viola o limite bipartido.

Como Funciona a Busca por Subdivisão

Após as verificações baratas de Euler, o verificador busca por uma subdivisão diretamente:

1. Ganho rápido — detectar K₅ ou K₃,₃ como um subgrafo literal. Se 5 vértices são adjacentes par a par, isso é K₅ puro. Se 6 vértices se dividem em 3 + 3 com todas as 9 arestas cruzadas presentes, isso é K₃,₃.
2. Busca de subdivisão K₅. Para cada conjunto candidato de 5 vértices de "ramificação" (cada um com grau ≥ 4 em G), tenta encontrar 10 caminhos — um por par de ramificações — que sejam internamente disjuntos nos vértices (nenhum vértice que não seja de ramificação aparece em mais de um caminho) e evitem usar as outras ramificações como vértices internos. Um acerto prova a não-planaridade.
3. Busca de subdivisão K₃,₃. Escolhe 6 ramificações (cada uma com grau ≥ 3) e uma bipartição 3 + 3. Busca por 9 caminhos de pares cruzados com o mesmo requisito de disjunção interna.
4. Nenhum testemunho ⇒ planar. Se nenhuma subdivisão for encontrada dentro dos limites de tamanho, o teorema de Kuratowski garante que o grafo é planar.

Encontrar caminhos disjuntos nos vértices é NP-difícil em geral, portanto, o verificador usa uma busca gananciosa aleatória limitada: cada iteração ordena os pares necessários por dificuldade, escolhe um caminho para o par mais difícil primeiro usando um BFS aleatório, remove esses vértices internos e continua. Se essa ordenação específica falhar, ele tenta novamente com uma ordem embaralhada — até 40 tentativas por configuração de ramificação. Em todos os pequenos grafos testados (até 16 vértices), isso é suficiente para localizar um testemunho sempre que existir.

Como Usar Esta Calculadora

1. Escolha um formato de entrada usando as abas no topo: lista de arestas ou lista de adjacência. Ambos codificam o mesmo grafo.
2. Insira seu grafo. O grafo é tratado como não direcionado, então A-B e B-A são a mesma aresta.
3. Clique em Verificar Planaridade. A ferramenta reporta um veredito, mostra o raciocínio passo a passo (Euler, bipartido, Kuratowski) e renderiza o grafo.
4. Para um grafo não-planar, a visualização colore a subdivisão K₅ ou K₃,₃ e lista os 10 (ou 9) caminhos disjuntos nos vértices. Clique em uma linha de caminho para isolá-lo.
5. Para um grafo planar, a contagem de faces F = m − n + 1 + c é reportada juntamente com a estrutura do grafo.

Exemplo Prático 1 — K₄ é planar

K₄ tem n = 4, m = 6. Todo grafo em ≤ 4 vértices é planar e, de fato, K₄ se mergulha como um triângulo com um único vértice dentro conectado aos três cantos. Euler diz F = 6 − 4 + 2 = 4 faces: três faces internas triangulares mais a face externa.

Exemplo Prático 2 — K₃,₃ é não-planar

K₃,₃ tem n = 6, m = 9. Ele é bipartido, então o limite bipartido se aplica: m = 9 > 2n − 4 = 8. Isso por si só prova a não-planaridade. O testemunho é trivial — K₃,₃ é ele mesmo o subgrafo proibido. A ferramenta destaca a partição 3 + 3 e as 9 arestas diretas.

Exemplo Prático 3 — O grafo de Petersen

O grafo de Petersen tem n = 10, m = 15, então m ≤ 3n − 6 = 24 e as verificações rápidas de Euler passam. No entanto, ele é famosamente não-planar. O verificador localiza uma subdivisão K₃,₃: escolhe seis vértices do pentágono externo e do pentagrama interno de modo que cada par cruzado possa ser roteado através dos quatro vértices restantes por caminhos disjuntos nos vértices. A ferramenta desenha o testemunho, tornando a geometria de 1930 tangível.

Aplicações da Planaridade

• Roteamento de VLSI e PCB. Um circuito de camada única é viável apenas se o grafo de conexão for planar; redes não-planares forçam vias ou camadas extras.
• Desenho e visualização de grafos. Grafos planares admitem layouts claros e livres de cruzamentos — úteis para mapas de metrô, grafos de chamadas e diagramas esquemáticos.
• Design de algoritmos. Muitos problemas NP-difíceis (corte máximo, cobertura de vértices, isomorfismo de grafos) tornam-se de tempo polinomial quando restritos a grafos planares.
• Coloração de grafos. O Teorema das Quatro Cores garante que todo grafo planar é 4-colorível — um resultado clássico cuja declaração depende da planaridade.
• Otimização combinatória. Caminho mais curto planar, fluxo máximo e corte mínimo admitem algoritmos rápidos especializados.
• Química molecular. Grafos de hidrocarbonetos aromáticos com anel de benzeno são planares; certas moléculas em gaiola não são.

Perguntas Frequentes

O que significa planar para um grafo?

Um grafo é planar se você puder desenhá-lo no plano de forma que nenhuma das duas arestas se cruzem, exceto nos vértices compartilhados. Equivalentemente, um grafo é planar se, e somente se, puder ser desenhado na superfície de uma esfera sem cruzamentos. Árvores, ciclos, o grafo do cubo e os sólidos Platônicos são todos planares, enquanto K₅ e K₃,₃ são os exemplos não-planares canônicos.

O que é o teorema de Kuratowski?

O teorema de Kuratowski afirma que um grafo finito é planar se, e somente se, não contiver nenhum subgrafo que seja uma subdivisão de K₅ ou K₃,₃. Uma subdivisão é obtida substituindo algumas arestas por caminhos mais longos, cada um através de novos vértices de grau 2. Isso fornece um certificado combinatório concreto de não-planaridade.

Qual é a diferença entre K₅ e K₃,₃?

K₅ tem 5 vértices, cada par dos quais é unido por uma aresta, totalizando 10 arestas. K₃,₃ tem 6 vértices particionados em dois grupos de 3, com cada vértice em um grupo conectado a cada vértice no outro, totalizando 9 arestas. Ambos são os menores grafos não-planares de seu tipo e, juntos, formam os menores proibidos para planaridade.

Como a desigualdade de Euler ajuda?

A fórmula de Euler V − E + F = 2 para grafos planares conexos combinada com o fato de que cada face de um grafo planar simples tem pelo menos 3 arestas resulta em m ≤ 3n − 6. Qualquer grafo simples que viole esse limite é imediatamente não-planar. Para grafos planares bipartidos, cada face tem pelo menos 4 arestas, resultando no limite mais rígido m ≤ 2n − 4. O verificador aplica ambos como regras de rejeição rápida.

Qual é o limite de tamanho?

O verificador lida com até 16 vértices e 60 arestas. Isso abrange grafos típicos de ensino e estilo de competição, incluindo o grafo de Petersen, o grafo de Möbius-Kantor, pequenos hipercubos e o grafo completo K₇. Grafos maiores exigem testes de planaridade especializados em tempo linear, como Hopcroft-Tarjan ou planaridade left-right.

Como a subdivisão testemunha é desenhada?

Quando o grafo é não-planar, os 5 vértices de ramificação do K₅ encontrado — ou os 6 vértices de ramificação do K₃,₃ divididos em dois triplos A e B — são destacados em um anel interno. Os 10 (ou 9) caminhos exigidos internamente disjuntos nos vértices são cada um desenhados em uma cor distinta para que você possa rastrear a topologia de K₅ ou K₃,₃ visualmente. Vértices e arestas que não fazem parte da subdivisão são esmaecidos.

Leitura Adicional

• Grafo planar — Wikipédia
• Teorema de Kuratowski — Wikipédia
• Característica de Euler — Wikipédia
• Grafo de Petersen — Wikipédia
• Teorema de Wagner (versão menor) — Wikipédia