MO405 - Atas das Aulas

6.1 - Imersões e a fórmula de Euler

Gás-água-eltricidade

Três inimigos de guerra vivem em casas na floresta. Deve-se definir caminhos destas casas para três fontes, que tradicionalmente são gás, água e eltricidade. Para evitar batalhas, os caminhos não devem se cruzar. Este problema quer saber se K_3,3 pode ser desenhado no plano sem que haja cruzamentos entre arestas.

K_3,3 e K₅ não podem ser desenhados sem cruzamentos

A justificativa é que se pegarmos um ciclo gerador (6-ciclo) no K_3,3, teremos 3 cordas que se cruzam, e como só conseguimos colocar uma dentro e outra fora do ciclo, a imersão não pode ser completada e o grafo não é planar. No caso do K₅, ao pegarmos um ciclo gerador (5-ciclo), ficamos com 5 cordas, e novamente não podemos terminar a imersão, pois no máximo 2 cordas podem ficar de um mesmo lado (dentro ou fora). Assim, K₅ também não é planar.

Grafo planar, imersão e grafo plano

Um grafo é planar se possui um desenho sem cruzamentos de arestas. Os termos imersão planar e grafo plano são sinônimos e representam um desenho de um grafo planar G.

Dual de um grafo plano

O grafo dual G^* de um grafo plano G é um grafo plano cujos vértices correspondem às faces de G. Para cada aresta e de G, há uma aresta e^* em G^* entre os vértices x e y, que representam as faces X e Y de G separadas por e.
Abaixo pode-se observar alguns grafos planos (em preto) e seus duais (em vermelho).
OBS: As arestas de corte de G dão origem a laços (loops) em G^*. Arestas paralelas são criadas em G^* quando duas faces em G são separadas por mais de uma aresta.
Propriedades:
- o dual de G sempre é um grafo conexo.
Abaixo, no grafo à esquerda, temos o exemplo do dual (em vermelho) de um grafo plano desconexo (em preto). À direita, temos o dual (em vermelho) do dual do grafo plano em preto à esquerda.

- o dual do dual de G é isomorfo ao grafo G se, e somente se, G é conexo.
Abaixo temos um grafo plano conexo (em preto) e seu dual (em vermelho). Percebe-se que o dual do grafo em vermelho é um isomorfo ao grafo em preto.

Fórmula de Euler

Caso um grafo plano G possua n vértices, e arestas e f faces, então n - e + f = 2. É possível estender esta fórmula para grafos desconexos. Tomando k como o número de componentes de um grafo desconexo G, temos que n - e + f = k + 1.
Existe um limite para o número de arestas para um grafo plano G. Caso o grafo G seja plano e possua pelo menos 3 vértices, então e(G) <= 3n - 6. Caso o grafo G também não possua triângulos, então e(G) <= 2n - 4.
É interessante notar que pode-se provar que K₅ não é planar, pois e = 10 > 9 = 3n - 6. Para K_3,3, que não possui triângulos, temos que e = 9 > 8 = 2n - 4, e portanto também não é um grafo planar.