Grafos e RedesGrafos planares

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.

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.

Fórmula de Euler

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

Ao comparar esses números, você notará que o número de arestas é sempre um a menosmaioro mesmo 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...

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.

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 + .