Algoritmo de Kuratowski

Defini√ß√Ķes

Subdivis√£o de um grafo

Consiste em adicionar um n√ļmero de v√©rtices qualquer ao longo de arestas quaisquer do grafo.

Grafos Isomorfos

Um grafo g1g_1 é isomorfo de um grafo g2g_2 se existe uma aplicação que coloca cada vértice do grafo g2g_2 no grafo g1g_1, preservando as arestas.

Exemplo

Iso 2 Os dois grafos separados pela linha vermelha s√£o isomorfos

Grafos Equivalentes

Dois grafos g1g_1 e g2g_2 s√£o equivalentes se s√£o isomorfos e preservam as fronteiras.

Exemplos

Iso 1 Os grafos acima s√£o isomorfos e equivalentes.

Iso 3 Os dois grafos separados pela linha vermelha são isomorfos, mas como a região a verde não é preservada (os vértices que forma a fronteira são diferentes nos 22 casos), não é equivalente.

Representação Grafo Planar

Um grafo é planar, se e só se conseguirmos representá-lo numa superfície esférica, tal que os seus vértices não se instersetem.

As projetarmos o desenho num plano, ficamos com uma representação do grafo planar.
Se rodarmos a esfera e projetarmos outra vez, teremos um desenho de um novo grafo planar, equivalente ao inicial.

Importante

Ao rodarmos a esfera sobre os eixos, conseguimos obter todas as representa√ß√Ķes do grafo planar.

Redução de um Grafo

Reduz-se um grafo, quando eliminamos um vértice de grau 22. Se eliminarmos vv, cujas arestas eram (v1,v)(v_1,v) e (v2,v)(v_2,v), essas arestas desaparecem e aparece um nova: (v1,v2)(v_1,v_2)

Exemplo

Redux

Grafo Homeomórfico

Dois grafos são homeomórficos se conseguimos aplicar a redução, até os grafos ficarem iguais.

Teorema de Kuratowski

Um grafo é planar se e só se não contém um subgrafo homeomórfico ao grafo k5k_5 ou ao grafo k3,3k_{3,3}.

Relembrar

  • k5‚Üík_5 \rightarrow Grafo Completo de 5 v√©rtices$
  • k3,3‚Üík_{3,3} \rightarrow Grafo bipartido com parti√ß√Ķes de dimens√£o 3:3:
Exemplos

Exemplo 1
Exemplo 2
Exemplo 3

Às vezes até pode ser planar
Exemplo 4

Dica

Neste processo nunca adicionamos vértices, apenas removemos. Por isso, se os graus dos vértices forem <4<4, sabemos que nunca encontraremos um k5k_5, apenas k3,3k_{3,3}.
Por outro lado, se os vértices tiverem grau 44 podemos encontrar o k5k_5.