Glossário

Selecione uma das palavras-chave à esquerda…

Grafos e RedesGrafos planares

Tempo de leitura: ~25 min

Aqui está outro quebra-cabeça relacionado à teoria dos grafos. Em uma pequena vila, existem três fornecedores de água, eletricidade e gás, respectivamente. Há também três casas que precisam ser atendidas. Infelizmente, devido ao layout da cidade, os tubos e cabos dos fornecedores não podem se cruzar.

Tente conectar cada um dos fornecedores abaixo a cada uma das casas, sem que nenhuma das linhas cruze:

Assim como as pontes de Königsberg, você rapidamente descobre que esse problema também é impossível. Parece que alguns grafos podem ser desenhados sem arestas sobrepostas - esses são chamados grafos planares - mas outros não.

K3 é planar.

K4 .

K5 .

O grafo completo K5 é o menor grafo que não é planar. Qualquer outro grafo que contenha K5 como subgrafo também não é planar. Isso inclui K6, K7 e todos os grafos completos que são maiores. O grafo no quebra-cabeça dos três serviços (água, energia e gás) é o grafo bipartido K3,3. Acontece que qualquer grafo não-planar deve conter K5 ou K3,3 (ou uma subdivisão desses dois grafos) como subgrafo. Este teorema é chamado de teorema de Kuratowski.

Planaridade

Esse é um grafo planar, mas os ${n} vértices foram misturados. Rearranje os vértices de modo que nenhuma das arestas se cruzem.

Fórmula de Euler

Todos os gráficos planares dividem o plano em que são desenhados em várias áreas, chamadas faces.

Vértices
Faces
Arestas
11 Vértices + Faces

Vértices
Faces
Arestas
15 Vértices + Faces

Vértices
Faces Arestas 25 Vértices + Faces

Ao comparar esses números, você notará que o número de arestas é sempre do que o número de faces mais o número de vértices. Em outras palavras, F + V = E + 1. Esse resultado é chamado equação de Euler e recebe o nome do mesmo matemático que resolveu o problema das pontes de Königsberg.

Infelizmente, existem infinitos grafos e não podemos verificar todos um a um para ver se a equação de Euler funciona mesmo. Em vez disso, podemos tentar encontrar uma prova simples que funcione para qualquer grafo...

FVE
010

0 + 1  =  0 + 1

O grafo mais simples consiste de um único vértice. Podemos facilmente checar que a equação de Euler é válida.
Vamos adicionar um novo vértice ao nosso grafo. Podemos adicionar uma aresta, e a equação de Euler ainda é válida.
Se adicionarmos um terceiro vértice teremos duas possibilidades. Podemos criar um triângulo pequeno: isso adiciona mais um vértice, uma face e duas arestas, e a equação de Euler ainda é válida.
Outra possibilidade é estender a linha com o vértice adicional: assim temos mais um vértice e uma aresta, e a equação de Euler ainda é válida.
Vamos continuar: se criarmos um quadrilátero, adicionamos mais um vértice, duas arestas e uma face. A equação de Euler ainda é válida.

Qualquer grafo (finito) pode ser construído começando com um vértice e adicionando mais vértices um por um. Mostramos que, independentemente da maneira como adicionamos novos vértices, a equação de Euler é válida. Portanto, é válido para todos os grafos. O processo que usamos é chamado de indução matemática. É uma técnica muito útil para provar resultados em infinitos casos, simplesmente iniciando com o caso mais simples e mostrando que o resultado é válido a cada passo na construção de casos mais complexos.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Muitos grafos planares se parecem muito com as planificações de poliedros, formas tridimensionais com faces poligonais. Se pensarmos nos poliedros como elásticos, podemos imaginá-los esticando-os até que se tornem grafos planares:

Isso significa que nós pode usar a fórmula de Euler não apenas para grafos planares, mas também para todos os poliedros - com uma pequena diferença. Ao transformar o poliedro em grafos, uma das faces desaparece: a face superior do poliedro se torna o "exterior" dos grafos. Em outras palavras, se você contar o número de arestas, faces e vértices de qualquer poliedro, você descobrirá que F + V = E + .

Icosaedro
20 Faces
12 Vértices
30 Arestas

Rombicosidodecaedro
62 Faces
60 Vértices
120 Arestas

Icosaedro truncado
32 Faces (12 pretas, 20 brancas)
60 Vértices
90 Arestas