Caminhos e circuitos eulerianos explicados
Algumas figuras podem ser desenhadas de um só traço, sem levantar o lápis e sem passar duas vezes por uma linha, e outras não, por muito que se tente. Nem é preciso tentar: conte as linhas em cada canto. Se no máximo dois cantos tiverem um número ímpar de linhas, a figura pode ser desenhada, e é nesses cantos que o traço tem de começar e acabar. Leonhard Euler encontrou esta regra em 1736 e com ela fundou a teoria dos grafos.
As sete pontes de Königsberg
A cidade prussiana de Königsberg, hoje Kaliningrado, ficava nas duas margens do rio Pregel e em duas ilhas, o Kneiphof e a Lomse. Sete pontes ligavam as quatro partes: duas do Kneiphof a cada margem, uma entre as duas ilhas e uma da Lomse a cada margem. Os habitantes perguntavam-se se um passeio poderia atravessar cada ponte exatamente uma vez. Euler respondeu num trabalho que apresentou à Academia de São Petersburgo em 1735 e que foi impresso em 1741: não pode. O seu passo decisivo foi deitar fora tudo menos as partes da cidade e as pontes entre elas, que é o que um grafo faz: um vértice para cada porção de terra e uma aresta para cada ponte, com duas arestas onde duas pontes ligam os mesmos sítios.
A regra dos graus
O grau de um vértice é o número de arestas que nele chegam. Um traço que passa por um vértice entra por uma aresta e sai por outra, por isso gasta as arestas desse vértice aos pares. Só o primeiro e o último vértice do traço podem ficar com uma aresta sem par. Assim, um vértice de grau ímpar tem de ser o início ou o fim do traço. O Kneiphof tinha cinco pontes e as outras três partes três cada uma: quatro vértices ímpares, dois a mais. Em geral, um grafo conexo tem um circuito euleriano, um traço que acaba onde começou, quando todos os graus são pares, e um caminho euleriano quando exatamente dois graus são ímpares, de um para o outro. O número de vértices ímpares nunca é um, nem qualquer outro número ímpar: cada aresta acrescenta 2 à soma de todos os graus, por isso a soma é par. Euler também reparou nisto, e hoje chama-se lema do aperto de mão.
Porque é que a regra chega
Euler mostrou que uma figura com mais de dois vértices ímpares não pode ser traçada e afirmou, sem demonstrar, que qualquer outra figura conexa pode. A demonstração veio de Carl Hierholzer, um matemático alemão que morreu novo em 1871; o seu artigo saiu em 1873. Comece num vértice ímpar, se houver, e senão em qualquer um, e caminhe por arestas não usadas enquanto puder. Como todos os outros vértices têm grau par, só pode ficar preso no vértice final. Se sobrarem arestas, algumas tocam no percurso já feito, porque a figura é conexa. A partir de um desses vértices caminhe outra vez até ficar preso, o que agora acontece de volta a esse vértice, e insira aí o laço no percurso. Repita até não sobrar nenhuma aresta. A demonstração é também o algoritmo mais rápido: cada aresta é olhada um número fixo de vezes.
O algoritmo de Fleury: não queime as pontes
Um traço pode falhar mesmo numa figura que pode ser desenhada. Tome dois triângulos ligados por uma única aresta e comece num canto do primeiro: se passar para o segundo triângulo antes de acabar o primeiro, nunca mais consegue voltar. A aresta de ligação é uma ponte: removê-la divide a figura em duas. O algoritmo de Fleury, de 1883, dá uma regra: em cada vértice escolha uma aresta que não seja uma ponte das arestas que faltam, a não ser que não haja outra. Seguindo-a, acaba-se sempre. Testar uma ponte leva tempo, por isso o algoritmo de Fleury é mais lento do que o de Hierholzer, mas é aquele que se pode seguir com um lápis, e a dica da aplicação usa-o.
Arranjar uma figura
Uma figura com k vértices ímpares precisa de k/2 traços. Para a desenhar com um só, acrescente arestas que liguem os vértices ímpares aos pares: cada aresta nova torna pares dois vértices ímpares. Com k/2 − 1 arestas sobram dois vértices ímpares e sai um caminho; com k/2 não sobra nenhum e sai um circuito. Mais uma ponte em Königsberg, entre duas quaisquer das quatro partes, teria tornado o passeio possível, e duas teriam permitido um percurso de ida e volta. A história fez algo parecido: duas pontes perderam-se na Segunda Guerra Mundial e duas foram substituídas por uma estrada moderna, e as cinco pontes que hoje estão nos locais antigos podem ser atravessadas uma vez cada uma, de uma ilha para a outra.
Contar as maneiras
A casa de São Nicolau, um quadrado com as duas diagonais e um telhado, é a versão alemã infantil do enigma: «Das ist das Haus vom Ni-ko-laus» tem oito sílabas, uma por cada linha. Os seus dois cantos de baixo são os únicos vértices ímpares, e há exatamente 44 maneiras de a desenhar a partir de cada um, 88 ao todo. Para grafos orientados, o número de circuitos eulerianos tem uma fórmula, o teorema BEST, com o nome de de Bruijn, van Aardenne-Ehrenfest, Smith e Tutte. Para grafos vulgares não se conhece nenhuma fórmula assim e contar é considerado difícil em geral, por isso a aplicação conta as figuras pequenas experimentando todas as maneiras e saltando os passos que dividiriam a figura em duas.
Onde se usam os caminhos eulerianos
Um limpa-neves, uma varredora ou um carteiro quer percorrer cada rua uma vez e voltar. Se cada cruzamento tiver um número par de ruas, um circuito euleriano chega; senão, algumas ruas têm de ser percorridas duas vezes, e escolher as mais baratas é o problema do carteiro chinês, posto por Meigu Guan em 1962. Um traçador de pena ou uma cortadora a laser poupa tempo traçando o máximo de linhas sem levantar a ferramenta. Na sequenciação do genoma, milhões de pedaços curtos de ADN são juntos procurando um caminho euleriano num grafo de De Bruijn, em que cada pedaço é uma aresta. E a mesma regra diz quais os desenhos de um livro de passatempos que vale a pena tentar.
Experimente
Abra o localizador de caminhos eulerianos para traçar você mesmo doze figuras, de Königsberg em 1736 e hoje a estrelas, quadrados encaixados e um cubo, ou desenhe as suas com arestas paralelas. Os vértices ímpares estão preenchidos, cada vértice mostra o seu grau, e a regra dos graus por baixo da figura diz o que é possível e que arestas a arranjariam. Se ficar preso, a aplicação diz se começou no vértice errado ou se atravessou uma ponte cedo demais, e em que passo. Dica dá uma aresta segura, e Resolver desenha a figura com o algoritmo de Fleury, mostrando o teste da ponte, ou com o de Hierholzer, mostrando cada inserção.
Perguntas frequentes
Um caminho euleriano é o mesmo que um caminho hamiltoniano?
Não. Um caminho euleriano usa cada aresta uma vez e pode passar várias vezes por um vértice; um caminho hamiltoniano visita cada vértice uma vez e não tem de usar todas as arestas. Contar os vértices ímpares diz logo se um grafo tem um caminho euleriano, mas para os caminhos hamiltonianos não se conhece nenhum teste rápido, e encontrar um é um dos problemas difíceis clássicos da informática.
A regra dos graus vale quando dois vértices estão ligados por mais do que uma aresta?
Vale. Cada aresta conta para o grau das suas duas pontas, haja ou não outra aresta a ligar os mesmos dois vértices. Königsberg é um multigrafo desses, com duas pontes do Kneiphof a cada margem. Uma aresta de um vértice para si próprio, um laço, acrescenta 2 ao seu grau e nunca muda se ele é ímpar.
E com ruas de sentido único?
Num grafo orientado cada aresta tem um sentido, e a regra compara as arestas que entram em cada vértice com as que saem. Há um circuito euleriano quando cada vértice tem tantas arestas a entrar como a sair e as arestas formam uma só peça, e um caminho euleriano quando um vértice tem mais uma aresta a sair, outro mais uma a entrar e todos os outros estão equilibrados. O caminho vai então do primeiro para o segundo.
Pode existir uma figura com exatamente um vértice ímpar?
Não. Os graus de todos os vértices somados dão o dobro do número de arestas, porque cada aresta tem duas pontas. Essa soma é par, por isso o número de graus ímpares nela também tem de ser par: 0, 2, 4 e assim por diante, nunca 1 nem 3.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Abrir o localizador de caminhos eulerianos