De um só traço
Vértices ímpares
Arestas traçadas
Maneiras de a traçar

    • 0 vértices ímpares: um circuito, de qualquer vértice de volta a ele
    • 2 vértices ímpares: um caminho de um para o outro
    • 4 ou mais: impossível de um só traço

    Método

    Mais sobre caminhos e circuitos eulerianos

    Localizador de caminhos eulerianos

    Consegue desenhar a casa de São Nicolau sem levantar o lápis e sem passar duas vezes por uma linha? Consegue, mas só começando num dos dois cantos de baixo, e há 44 maneiras a partir de cada um. A razão é o grau de um vértice, o número de linhas que ali se encontram: de cada vez que o lápis passa por um vértice gasta duas das suas linhas. Leonhard Euler encontrou esta regra em 1736 com as sete pontes de Königsberg. Trace você mesmo uma figura, veja onde fica preso e porquê, peça uma dica ou veja um algoritmo desenhá-la. Escolha uma figura e trace-a: toque num vértice para começar e depois nas arestas ou nos vértices seguintes por ordem, ou arraste de vértice em vértice. Cada aresta só pode ser usada uma vez. Voltar desfaz um passo, Dica mostra a próxima aresta segura e Resolver executa passo a passo o algoritmo de Fleury ou o de Hierholzer. Os vértices ímpares estão preenchidos e a marca em cada vértice é o seu grau. Em Desenhar, toque num espaço vazio para acrescentar um vértice e em dois vértices para os unir, outra vez para uma segunda aresta; arraste um vértice para o mover. Apagar remove vértices e arestas. Quando mais de dois vértices são ímpares, Adicionar coloca as arestas que tornam a figura traçável.

    Como funciona

    1. Escolha uma figura, como as sete pontes de Königsberg, a casa de São Nicolau ou uma estrela, ou desenhe a sua em Desenhar, com tantas arestas quantas quiser entre dois vértices.
    2. Toque num vértice para começar e depois nas arestas ou nos vértices por ordem, ou arraste de vértice em vértice. Se ficar preso, a linha de estado diz porquê; Voltar desfaz um passo e Dica mostra uma aresta segura.
    3. Leia a regra dos graus por baixo da figura, acrescente a uma figura impossível as arestas sugeridas, ou carregue em Resolver para ver o algoritmo de Fleury ou o de Hierholzer desenhá-la passo a passo.

    Porque é que são os vértices ímpares que decidem

    Um traço que passa por um vértice chega por uma linha e sai por outra, por isso gasta as linhas desse vértice duas a duas. Só onde o traço começa ou acaba é que uma linha pode ficar sem par. Assim, um vértice com um número ímpar de linhas tem de ser o início ou o fim. Sem vértices ímpares, o traço acaba onde começou: um circuito euleriano. Com dois, vai de um para o outro: um caminho euleriano. Com quatro ou mais há extremos a mais para um só traço, e k vértices ímpares precisam de k/2 traços. Königsberg tinha quatro porções de terra, com cinco, três, três e três pontes: todas ímpares, por isso nenhum passeio podia atravessar cada ponte uma vez. Uma ponte nova entre duas delas teria tornado o passeio possível.

    Os algoritmos de Fleury e de Hierholzer

    Saber que uma figura pode ser desenhada não é o mesmo que desenhá-la: um traço descuidado pode cortar-se das linhas de que ainda precisa. O algoritmo de Fleury, de 1883, evita isso com uma regra: nunca atravesse uma ponte, isto é, uma linha cuja remoção dividiria em duas partes as linhas que faltam, a não ser que não haja outra linha. O algoritmo de Hierholzer, de um artigo publicado em 1873, é mais rápido: caminhe por onde quiser até ficar preso, o que só pode acontecer no ponto de partida, e depois, a partir de um vértice do percurso que ainda tenha linhas livres, percorra outro laço fechado e insira-o no percurso. O seu tempo cresce proporcionalmente ao número de arestas, e é assim que os computadores encontram caminhos eulerianos.

    Perguntas frequentes

    Qual é a diferença entre um caminho euleriano e um circuito euleriano?

    Ambos usam cada aresta de um grafo exatamente uma vez. Um circuito euleriano acaba onde começou; um caminho euleriano acaba noutro sítio. Um grafo conexo tem um circuito quando todos os vértices têm grau par, e um caminho quando exatamente dois vértices têm grau ímpar; o caminho vai então de um para o outro.

    Porque é que não se podem atravessar uma vez cada uma as sete pontes de Königsberg?

    Desenhe cada porção de terra como um vértice e cada ponte como uma aresta. A ilha de Kneiphof tinha cinco pontes e as outras três porções três cada uma, por isso os quatro vértices são ímpares. Um passeio só pode começar ou acabar num vértice ímpar, e quatro são demasiados. Acrescentar uma ponte entre dois deles deixa dois vértices ímpares, e o passeio passa a ser possível.

    De quantas maneiras se pode desenhar a casa de São Nicolau?

    44 a partir de cada um dos dois cantos de baixo, 88 ao todo, contando outra ordem ou outro sentido como outra maneira. A partir de qualquer outro vértice não dá, porque os cantos de baixo são os dois únicos com um número ímpar de linhas. A aplicação conta assim as maneiras das figuras pequenas.

    O que é uma ponte num grafo?

    Uma aresta cuja remoção divide um grafo conexo em duas partes. O algoritmo de Fleury nunca atravessa uma ponte das arestas que faltam enquanto tiver outra escolha, porque deixaria para trás parte da figura. Nesta aplicação, a um traço que fica preso depois de atravessar uma ponte cedo demais é dito qual foi o passo.

    Pode haver mais do que uma aresta entre dois vértices?

    Pode. Um grafo com arestas paralelas chama-se multigrafo, e Königsberg precisa de um: duas pontes ligavam o Kneiphof a cada margem. Em Desenhar, toque outra vez em dois vértices para acrescentar mais uma aresta entre eles, até quatro. A regra dos graus funciona da mesma maneira, contando cada aresta.

    Pronto para experimentar?

    Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

    Ir para o editor