Labirintos

Defini√ß√Ķes

Atalhos Eulerianos

Atalhos que percorrem todos os vértices e arestas.
Relembrar que um atalho nunca repete arestas.
Os Atalhos Eulerianos também podem ser fechados (se acabarem no mesmo vértice) ou abertos (se não acabarem no mesmo vértice).

Um atalho euleriano fechado também se pode designar por circuito euleriano e um atalho euleriano aberto por travessia euleriana.


Multigrafo Euleriano

Um multigrafo euleriano é um multigrafo que tem um atalho euleriano fechado.


Multigrafo Atravess√°vel

Um multigrafo atravessável é um multigrafo que tem um atalho euleriano aberto.

Representar um Labirinto com Grafo

Seja uma encruzilhada um sítio no labirinto, onde se pode escolher vários caminhos.
Podemos representar um Labirinto através de um grafo, onde todas as entradas, saídas, centros, encruzilhadas e becos sem sáida do labirinto são vértices e as arestas são os caminhos que existem entre cada vértice.

Exemplos

Labirinto Grafo1

Labirinto Grafo2

Teoremas e Algoritmos

Teorema de Euler-Hierholzer

Um multigrafo é euleriano se e só se é conexo e todo o seu vértice é par.
Relembrar: Conexo significa que quaisquer dois vértices estão conectados (não há vértices isolados).

AVISO

No próximo teste haverá uma Demontração, segundo o professor, que também disse que a Demonstração seguinte é Muito Importante. Se esta não ficar clara, poderá ficar mais fácil assistir à Prova feita pelo professor em aula, uma vez que são usados vários desenhos explicativos. Esta pode ser encontrada aqui e começa em 47:10 e acaba em 1:04:20.

Demonstração
  1. Condição Necessária

Seja gg um multigrafo euleriano, então este terá um atalho euleriano fechado (passa por todos os vértices e arestas, sem repetir arestas e acabando no vértice por onde começamos). Aqui podemos concluir logo que gg é conexo.

Supondo que começávamos o atalho num vértice vv, então, para todo o vértice do multigrafo gg diferente de vv, vamos ter de, obrigatoriamente, "chegar" e depois "sair" do vértice, visto que temos de percorrer todos os vértices e não podemos terminar o atalho sem ser em vv.
Quando saímos (e entramos) num vértice, nunca pode ser por uma aresta já percorrida, porque o multigrafo gg é euleriano. Deste modo, é fácil reparar que todo o vértice diferente de vv terá grau par, porque saímos e entramos sempre por arestas diferentes (não importa quantas vezes).

Já se provou que todo o vértice diferente de vv (vértice inicial) é par, agora falta provar o mesmo para vv.
A √ļnica diferen√ßa, face aos restantes v√©rtices, √© que em vv sa√≠mos primeiro. Tal como nos outros v√©rtices, tamb√©m podemos entrar e sair de vv, durante o atalho. Contudo, o seu grau tamb√©m ser√° par, porque no final regressamos a vv, por uma aresta diferente.

  1. Condição Suficiente - A parte mais Importante, segundo o professor

Seja gg um multigrafo conexo e com todos vértices são pares. Vamos tentar provar que gg é um multigrafo euleriano, por absurdo.

Sendo YY o maior atalho fechado que podemos arranjar em gg onde YY não é um atalho euleriano fechado. Deste modo, há arestas que não foram percorridas em gg.
Seja CC o grafo, que resulta de eliminar todas as arestas de YY. Se YY n√£o era um atalho euleriano fechado, ent√£o CC tem de ter arestas.
Como YY √© um atalho fechado, vamos remover a cada v√©rtice um n√ļmero par de arestas, ent√£o em CC vamos continuar com os v√©rtices todos pares (relembrar que gg tinha os v√©rtices todos pares).
Como gg era conexo, existe um v√©rtice uu de CC onde passava o atalho YY, que n√£o √© isolado (relembrar que CC tem arestas). Esse v√©rtice uu ter√° grau par ‚Č•0\geq 0.
Uma vez que os vértices têm todos grau par, será sempre possível "entrar" e "sair" de um vértice e se começarmos por sair de um, vamos, obrigatoriamente, ter de regressar ao mesmo, algures no atalho. Então existirá um atalho fechado a começar e acabar em uu, que vamos designar por UU

Finalmente, se existe um atalho fechado a começar e acabar em uu, com arestas não pertencentes a YY, será possível juntar os dois atalhos num só. Repare-se que, se YY é um atalho fechado, então podemos fazer um atalho semelhante, só que acaba e começa em uu, mas, em vez de terminarmos, passamos a percorrer o atalho UU, acabando finalmente em uu. Chegamos a um absurdo, afinal YY não é o maior atalho fechado que podemos arranjar em gg se não for um atalho euleriano fechado.

QED

NOTA

√Č importante referir tamb√©m que este processo √© recursivo. Poder√≠amos voltar a considerar CC um novo grafo, mas que a agora seria o resultado de retirar o atalho "Y+UY+U" e chegar√≠amos √† mesma conclus√£o. S√≥ terminar√° se CC for um grafo de v√©rtices isolados (sem arestas) e nesse caso conclui-se que o atalho fechado era um atalho euleriano fechado.


Teorema 2

Um multigrafo é atravessável se e só se tem apenas dois vértices ímpares.
Para al√©m disso, o atalho Euleriano aberto come√ßa e acaba nos v√©rtices √≠mpares, onde o primeiro √© diferente do √ļltimo.

AVISO

Demonstração semelhante à anterior. Também é Muito Importante, segundo o professor e na aula o professor usou desenhos explicativos que podem ajudar a perceber.
Podem encontrar a aula no mesmo link começa em 1:06:50 e acaba em 1:20:00.

Demonstração
  1. Condição Necessária

    Seja gg um multigrafo atravess√°vel, significa que, se eu partir de um v√©rtice uu, consigo percorrer um atalho euleriano aberto (travessia euleriana), ou seja, que percorre todas as arestas sem repeti√ß√Ķes e termina num v√©rtice diferente, vv.

    Supondo que agora criávamos uma nova aresta de uu a vv, de modo a que fosse possível percorrer um circuito euleriano (atalho euleriano fechado). Basta pensar na travessia euleriana que tinhamos e agora acrescenta-se uma aresta que liga uu a vv.
    NOTA: uu e vv poderiam até já ter arestas que os interligassem, mas não eram suficientes para formar um circuito euleriano.

    Como se sabe, um circuito euleriano tem todos os v√©rtices pares. Ent√£o, se removermos a aresta que adicion√°mos uu e vv passaram a ter grau √≠mpar e ser√£o os √ļnicos, pois a aresta removida era comum aos dois. Os outros v√©rtice permanecer√£o com grau par.

    Logo, se gg é atravessável , então tem pelo apenas 22 vértices com grau ímpar.

  2. Condição Suficiente

    (A ideia é quase igual à da Condição Necessária)

    Seja gg um multigrafo com apenas 22 vértices com grau ímpar.

    Se unitrmos esses vértices com uma nova aresta, pelo Teorema de Euler-Hierholzer gg terá um circuito euleriano.
    Ent√£o, se eu remover a aresta adicionada, gg passar√° a ter uma travessia euleriana, logo ser√° atravess√°vel.

QED

NOTA

A prova para grafos (n√£o multigrafos) √© muito parecida. A √ļnica diferen√ßa √© que temos de adicionar um v√©rtice com duas arestas, uma que se liga a uu outra a vv, porque podemos ter uma travessia como:

Imagem Exceção

Como estamos a trabalhar com grafos, não podemos ter mais do que 11 aresta a ligar 22 vértices.
Apesar desta exceção a prova é igual, só que retiramos/adicionamos 22 arestas e 11 vértice como descrito.


Teorema 3 - Teorema de Euler

Se tivermos um grafo que não seja Euleriano, podemos duplicar cada aresta e dessa maneira todos os vértices terão grau par, assim já é Euleriano.
NOTA: Outra solução é percorrer cada aresta duas vezes, em vez de duplicar.


Teorema 4 - Teorema de Lucas

Um multigrafo G\mathcal G conexo com 2n2n vértices ímpares pode ser descrito por exatamente nn atalhos abertos que não partilham arestas.


Algoritmo de Fleury

Com este Algoritmo consegue-se percorrer um atalho euleriano fechado num multigrafo euleriano.

  1. Começa-se num vértice qualquer
  2. Se houver mais que 11 aresta possível a percorrer, escolhe-se uma que não seja Ponte (não interessa qual, desde que não seja uma Ponte)
  3. S√≥ se atravessam as Pontes em √ļltimo caso (quando j√° n√£o h√° mais arestas dispon√≠veis).

Relembrar: Ponte é uma aresta que, se removida, cria uma nova componente.

Exemplo

O exemplo encontra-se neste link

Algoritmo Fleury - Multigrafo Atravess√°vel

O Algoritmo de Fleury foi concebido para multigrados eulerianos.
Mas, também o podemos aplicar, informalmente, em multigrafos atravessáveis.

Para isso, basta come√ßar num v√©rtice √≠mpar, √© a √ļnica mudan√ßa no Algoritmo. Mas, neste caso, n√£o vamos acabar no mesmo v√©rtice, mas sim no outro v√©rtice √≠mpar. Reparem que, se, num multigrafo atravess√°vel, ligarmos os dois v√©rtices √≠mpares com uma aresta, ficamos com um multigrafo euleriano. Nesse caso, j√° poder√≠amos acabar no v√©rtice inicial.

Desvantagens

Não funciona em Labirintos se não o conhecermos, uma vez que nesses caso não sabemos se um aresta (caminho do Labirinto) é Ponte ou não.


Algoritmo de Trémaux

Com as regras deste Algoritmo, qualquer um pode sair de qualquer labirinto.

Passamos agora à descrição do Algoritmo:

  1. Sempre que chegamos a um vértice não visitado anteriormente, seguimos por uma aresta também não percorrida, qualquer.
  2. Sempre que chegarmos a um vértice através de uma aresta ainda não percorrida anteriormente, se chegarmos a um vértice já visitado ou a um beco sem saída, voltamos para o vértice de onde viemos pela aresta.
  3. Sempre que chegarmos a um vértice através de uma aresta que já tinha sido percorrida anteriormente e chegarmos a um vértice já visitado, escolhemos a aresta ainda não percorrida que incide no vértice. Se não existir, escolhemos percorrer uma aresta que já tenha sido percorrida apenas uma vez.
Exemplo

O exemplo encontra-se neste link


Algoritmo de Tarry

Se chegarmos a um vértice, escolhemos continuar por qualquer aresta que não tenha sido percorrida 22 vezes (dando prioridade às arestas ainda não percorridas), com exceção da aresta onde chegamos pela primeira vez ao vértice atual.
S√≥ percorremos essa aresta em √ļltimo caso, ou seja, se for um beco sem sa√≠da, ou se as outras arestas j√° tiverem sido percorridas 22 vezes.

Exemplo

O exemplo encontra-se neste link.

Teorema de Tarry

Iniciando um caminho num grafo conexo qualquer, e seguindo as regras do Algoritmo de Tarry, regressaremos ao vértice inicial, depois de ter percorrido cada aresta do grafo 22 vezes em sentidos opostos.