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

Vídeo: A Fórmula de Euler e a Dualidade dos Grafos

A Fórmula de Euler e a Dualidade dos Grafos

07:27

Transcrição do vídeo

No 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 partilhar uma demonstração particularmente interessante deste facto. É muito diferente da demonstração por indução normalmente dada, mas eu não estou a tentar dizer que esta é de alguma forma melhor ou mais fácil de entender que outras demonstrações. 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 diz. Se desenhares alguns pontos e algumas linhas entre eles, ou seja, um grafo, e se nenhuma destas linhas se cruzar, o que significa dizer que tens um grafo planar, e se o desenho estiver conectado, a fórmula de Euler diz-nos que o número de pontos menos o número de linhas mais o número de regiões em que essas linhas dividem o plano, incluindo aquela região externa, será sempre dois.

Como Euler estava originalmente a falar sobre poliedros em 3D quando descobriu esta 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 demonstração, preciso de passar por três partes da terminologia da teoria dos grafos: circuitos, árvores de abrangência e grafos duais. Se já conheces alguns destes tópicos e não te interessa como vou descrevê-los, fica à vontade para clicar na anotação apropriada e avançar.

Imagina uma pequena criatura sentada num 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 viajar, onde não permitimos que ele retroceda pela mesma aresta.

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

Agora imagina que Randolph quer ter acesso a todos os outros vértices, mas as arestas são caras, então ele só comprará acesso a uma aresta se lhe der um caminho para um vértice por onde ainda não passou. Esta frugalidade deixá-lo-á com um conjunto de arestas que não formam um circuito, já que a aresta que fecharia um circuito seria sempre desnecessária.

Em geral, um grafo conexo sem circuitos é designado por á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 é designada por árvore de abrangência.

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

Eu menti há pouco quando 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 aquelas coisas com pontos e as 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 fazer 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 representados: 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 que refletem sobre a representação real de um grafo no plano, podemos considerar o conjunto de faces em que esse grafo divide o plano e considerar dois deles conectados se partilham uma aresta.

Por outras palavras, se poderes desenhar um grafo no plano sem arestas a intersetarem-se, obténs automaticamente um segundo grafo, ainda não desenhado, cujos vértices são as faces e cujas arestas são, bem, as arestas do gráfico original. Chamamos a este de dual do grafo original.

Se quiseres representar o grafo dual com pontos e linhas, primeiro colocas 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 podes viajar em qualquer direção para chegar lá.

Em seguida, conecta estes 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 tem em mente que isto é 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 este ponto é para enfatizar que as arestas do grafo original e as arestas do grafo dual não estão apenas relacionadas; são a mesma coisa.

Repara, o que torna o grafo dual incrível é as muitas formas como se relaciona com o grafo original. Por exemplo, os circuitos no gráfico original correspondem às componentes conectadas do grafo dual e, da mesma forma, os circuitos no gráfico dual correspondem às componentes conectadas no gráfico original.

Agora para a parte fixe. Supõe que o nosso amigo Randolph tem um alter ego, Mortimer, que vive no grafo dual, viajando de face para 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 abrangência e que Mortimer esteja proibido de atravessar essas arestas. Acontece que as arestas que Mortimer tem disponíveis para si garantem formar uma árvore de abrangência do grafo dual.

Para ver o porquê, precisamos apenas de verificar as duas propriedades que definem as árvores de abrangência: devem dar acesso a Mortimer a todas as faces e não pode haver circuitos.

A razão pela qual ele ainda tem acesso a todas as faces é que seria preciso um circuito na árvore de abrangência de Randolph para isolá-lo de uma face, mas as árvores não podem ter circuitos.

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

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

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

Alternativamente, dentro da nossa narrativa, poderias pensar em Randolph como a começar com um vértice e ganhar exatamente mais um para cada aresta que ele compra no que se tornará uma árvore de abrangência. Como esta árvore cobre todos os vértices no nosso gráfico, o número de vértices é um a mais que o número de arestas na posse de Randolph.

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

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