Fórmula de Euler para Gráficos Planares

Imagine que você é um planejador de rodovias ou um designer de placa de circuito impresso. Quer se trate de uma estrada com tráfego fluido ou um fio com eletricidade fluindo, você gosta quando as linhas não se cruzam. Esses aplicativos e outros são exemplos de gráficos planos . É o tipo de figura que você desenharia com linhas em um pedaço de papel. Surpreendentemente, existe uma relação simples entre os números dos três itens principais de todos os gráficos planares.

Vértices, arestas e faces

Os três itens principais dos gráficos planos são os vértices, as arestas e as faces.

Um vértice é o ponto onde as linhas se encontram. É a esquina. Quantos vértices em um triângulo? Certo, três:

Se juntarmos esses vértices com linhas retas, obteremos a figura do triângulo. As linhas são as bordas :

Há mais uma margem que podemos desenhar. Começamos em qualquer um dos vértices e tentamos conectar este vértice a outro vértice que ainda não tenha uma conexão. Novamente, as linhas não podem se cruzar:

Que tal rostos? Um rosto é uma área no gráfico. Aí está a cara dentro do triângulo, a . A aresta adicional produziu uma segunda face, b . E, por fim, existe a área externa da figura. Este é o rosto, c :

O número de vértices é V , o número de arestas é E e o número de faces é F . Em nosso exemplo,

V é 3
E é 4
F é 3

Apenas por diversão,

pegue V e subtraia E : 3 – 4 é -1
em seguida, adicione F : -1 + 3 é 2

A resposta é 2. Essa resposta sempre será 2 para qualquer gráfico planar!

Este resultado é a fórmula de Euler:

Que tal mais vértices?

Vamos fazer outro exemplo. Pegue um pedaço de papel e coloque quatro pontos nele:

Ok, você não precisa organizar os pontos como os quatro cantos de um quadrado. Você pode colocá-los da maneira que quiser. Os pontos são os vértices.

Agora, junte esses quatro vértices com arestas. Uma primeira passagem provavelmente será assim:

Mas então há outra borda ao longo da diagonal:

E explorando cada vértice para ver se há outra aresta que encontramos:

A única regra é que as bordas não se cruzem. Que tal rostos? Em vez de rotular os rostos, podemos usar cores:

Quantas faces? Verde, azul e laranja, mas não se esqueça da face externa fazendo F = 4.

Quantas arestas? E = 6.

E, claro, quatro vértices: V = 4.

A fórmula de Euler é verdadeira?

V = 4
E = 6
F = 4

V – E – F = 4 – 6 – 4 = 8 – 6 = 2. Sim!

Resumo da lição

Um gráfico plano é um gráfico desenhado no plano no qual as linhas não se cruzam e se encontram apenas nos vértices. Um vértice é o ponto de encontro das linhas. A palavra que usamos para linhas é borda . Um rosto é uma superfície fechada. Incluímos a superfície externa ao contar o número de faces. A fórmula de Euler diz V – E + F = 2 onde

V é o número de vértices
E é o número de arestas
F é o número de faces