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 $g_1$ é isomorfo de um grafo $g_2$ se existe uma aplicação que coloca cada vértice do grafo $g_2$ no grafo $g_1$, preservando as arestas.

Exemplo

Os dois grafos separados pela linha vermelha são isomorfos

Grafos Equivalentes

Dois grafos $g_1$ e $g_2$ são equivalentes se são isomorfos e preservam as fronteiras.

Exemplos

Os grafos acima são isomorfos e equivalentes.

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 $2$ 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 intersetem.

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.

Redução de um Grafo

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

Exemplo

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 $k_5$ ou ao grafo $k_{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$, sabemos que nunca encontraremos um $k_5$, apenas $k_{3,3}$.
Por outro lado, se os vértices tiverem grau $4$ podemos encontrar o $k_5$.