Vídeo: A Fórmula de Euler e a Dualidade do Gráfico

Grant Sanderson • 3Blue1Brown • Boclips

A Fórmula de Euler e a Dualidade do Gráfico

07:26

Transcrição do vídeo

Em meu vídeo sobre o problema da divisão de círculos, fiz referência à fórmula característica de Euler. E aqui, gostaria de compartilhar uma prova particularmente interessante desse fato. É muito diferente da prova indutiva normalmente dada, mas eu não estou tentando argumentar que isso é de alguma forma melhor ou mais fácil de entender do que outras provas. Em vez disso, escolhi este tópico para ilustrar um exemplo da incrível noção de dualidade e como ela pode produzir uma matemática maravilhosamente elegante.

Primeiro, vamos ver o que o teorema afirma. Se você desenhar alguns pontos e algumas linhas entre eles, ou seja, um grafo, e se nenhuma dessas linhas se cruzarem, o que equivale a dizer que você tem um grafo planar e se o desenho estiver conectado, a fórmula de Euler nos diz que o número de pontos menos o número de linhas mais o número de regiões em que essas linhas cortam o plano, incluindo essa região externa, será sempre dois.

Como Euler estava originalmente falando sobre poliedros em 3D quando encontrou essa fórmula, que só depois foi reformulada em termos de grafos planares, em vez de dizer pontos, dizemos vértices; em vez de dizer linhas, dizemos arestas; e em vez de dizer regiões, dizemos faces. Assim, escrevemos a descoberta de Euler como 𝑉 menos 𝐸 mais 𝐹 é igual a dois.

Antes de descrever a prova, preciso passar por três partes da terminologia da teoria dos grafos: ciclos, abrangendo árvores e grafos duplos. Se você já conhece alguns desses tópicos e não sabe como descrevê-los, fique à vontade para clicar na anotação apropriada e pular para frente.

Imagine uma pequena criatura sentada em um dos vértices. Vamos chamá-lo de Randolph. Se pensarmos nas arestas como algo que Randolph pode percorrer, de um vértice para outro, podemos falar sensatamente sobre um “caminho” como sendo uma sequência de arestas pelas quais Randolph poderia percorrer, onde não permitimos que ele retroceda na mesma aresta.

Um ciclo é simplesmente um caminho que termina no mesmo vértice onde começa. Você pode ser capaz de adivinhar como os ciclos serão importantes para nossos propósitos, pois eles sempre incluirão um conjunto de faces.

Agora imagine que Randolph quer acesso a todos os outros vértices, mas as arestas são caras, então ele só comprará acesso a uma aresta se isso der a ele um caminho para um vértice intocado. Esta frugalidade o deixará com um conjunto de arestas sem nenhum ciclo, já que a aresta que termina um ciclo seria sempre desnecessária.

Em geral, um grafo conectado sem ciclos é chamado de árvore, assim chamado porque podemos mover as coisas e fazer com que pareça um sistema de ramificações, e qualquer árvore dentro de um grafo que toque todos os vértices é chamada de árvore de extensão.

Antes de definir o grafo dual, que corre o risco de ser confuso, é importante lembrar por que as pessoas realmente se importam com os grafos em primeiro lugar.

Eu estava mentindo mais cedo quando eu disse que um grafo é um conjunto de pontos e linhas; na verdade, é um conjunto de qualquer coisa com qualquer noção de conexão, mas normalmente representamos essas coisas com pontos e essas conexões com linhas.

Por exemplo, o Facebook armazena um enorme grafo, onde os vértices são contas e as arestas são amizades. Embora pudéssemos usar desenhos para representar esse grafo, o próprio grafo é o conjunto abstrato de contas e amizades, completamente distinto do desenho.

Todos os tipos de coisas são grafos não desenhados: o conjunto de palavras inglesas, consideradas conectadas quando diferem por uma letra; matemáticos, considerados conectados se tiverem escrito um artigo juntos; neurônios conectados por sinapses, ou, talvez, para aqueles de nós raciocinando sobre o desenho real de um grafo no plano, podemos pegar o conjunto de faces em que esse grafo corta o plano e considerar dois deles conectados se eles compartilham uma aresta.

Em outras palavras, se você pode desenhar um grafo no plano sem arestas de interseção, você obtém automaticamente um segundo grafo, ainda não desenhado, cujos vértices são as faces e cujas arestas são, bem, as arestas do grafo original. Chamamos isso de dualidade do grafo original.

Se você quiser representar o grafo dual com pontos e linhas, primeiro coloque um ponto dentro de cada uma das faces. Eu pessoalmente gosto de visualizar o ponto para aquela região externa como sendo um ponto em algum lugar no infinito, onde você pode percorrer em qualquer direção para chegar lá.

Em seguida, conecte esses novos pontos com novas linhas que passam pelos centros das linhas antigas, onde as linhas conectadas ao ponto no infinito podem sair da tela em qualquer direção, desde que se entenda que elas se encontram no mesmo ponto.

Mas tenha em mente que isso é apenas um desenho do grafo dual, assim como a representação de contas do Facebook e amizades com pontos e linhas é apenas um desenho do grafo social; o grafo dual em si é a coleção de faces e arestas.

A razão pela qual enfatizo esse ponto é enfatizar que as arestas do grafo original e as arestas do grafo dual não são apenas relacionadas: elas são a mesma coisa.

Você vê, o que torna o grafo dual de todos os tipos impressionantes é as muitas maneiras que ele se relaciona com o grafo original. Por exemplo, os ciclos no grafo original correspondem as componentes conectadas do grafo dual e, da mesma forma, os ciclos no grafo dual correspondem as componentes conectadas no grafo original.

Agora para a parte legal. Suponha que nosso amigo Randolph tenha um alter ego, Mortimer, vivendo no grafo dual, percorrendo de face a face em vez de vértice para vértice, passando por cima de arestas ao fazê-lo.

Digamos que Randolph tenha comprado todas as arestas de uma árvore de extensão e que Mortimer esteja proibido de cruzar essas arestas. Acontece que as arestas que Mortimer tem disponível para ele são garantidas para formar uma árvore de extensão do grafo dual.

Para ver por que, precisamos apenas verificar as duas propriedades definidoras das árvores de extensão: elas devem dar acesso a Mortimer a todas as faces e não pode haver ciclos.

A razão pela qual ele ainda tem acesso a todas as faces é que levaria um ciclo na árvore de extensão de Randolph para isolá-lo de uma face, mas as árvores não podem ter ciclos.

A razão pela qual Mortimer não pode atravessar um ciclo no gráfico dual é completamente simétrica. Se ele pudesse, separaria um conjunto de vértices de Randolph dos demais, de modo que a árvore de extensão da qual ele é banido não poderia abranger todo o gráfico.

Portanto, o grafo planar não só tem um grafo dual, como também qualquer árvore de extensão dentro desse grafo tem uma árvore de extensão dual no grafo dual.

Aqui está a jogada: o número de vértices em qualquer árvore é sempre um a mais que o número de arestas. Para ver isso, observe que, depois de começar com o vértice raiz, cada nova aresta fornece exatamente um novo vértice.

Alternativamente, dentro da nossa narrativa, você poderia pensar em Randolph como começando com um vértice e ganhando exatamente mais um para cada aresta que ele compra no que se tornará uma árvore de extensão. Como esta árvore cobre todos os vértices em nosso gráfico, o número de vértices é um a mais que o número de arestas de propriedade de Randolph.

Além disso, como as arestas remanescentes formam uma árvore de extensão para o grafo dual de Mortimer, o número de arestas que ele obtém é uma a mais que o número de vértices no grafo dual, que são faces do grafo original.

Juntando isso, significa que o número total de arestas é dois a mais que o número de vértices mais o número de faces, que é exatamente o que a fórmula de Euler indica.

A Nagwa usa cookies para garantir que você tenha a melhor experiência em nosso site. Saiba mais sobre nossa Política de privacidade.