Circuito-Euleriano-Hierholzer-e-Fleury

1ª Parte do Trabalho De Algoritmos em Grafos

Circuito Euleriano: Hierholzer e Fleury

Gustavo Maciel – 478509

Danilo Gabriel – 478500 Eng. de Computação

Grafos Eulerianos

Um grafo Euleriano é aquele que contém um ciclo Euleriano, que é um caminho em um grafo que visita cada aresta exatamente uma vez, iniciando e terminando no mesmo vértice.

Um caminho Euleriano percorre cada aresta uma vez, sem a necessidade de voltar ao ponto de partida.

Um grafo conexo é Euleriano se e somente se todos seus vértices forem de grau par. Exemplo de um grafo euleriano:

[pic 1]

Prova:

   -ida:

Considerando G um grafo euleriano, existe um número V de vetrices e cada um possui uma aresta que incide no vértice e sai do mesmo. Todas as arestas devem ser utilizadas, necessariamente o número de arestas por vértices é par.

   -volta:

Supondo que todos os vértices V possuem grau par, seja Vn um vértice do grafo, como todos os vértices possuem grau par então é possível entrar e sair do vértices sem passar pela mesma aresta, exceto quando Vn é o vértice onde o caminho euleriano termina. Se Vn é o fim do caminho euleriano e este possui todas as arestas do grafo G, então teremos um ciclo euleriano. Caso isso não ocorra se retira todas as arestas de G que incidem no caminho formado C, o grafo G' resultante de todos os vértices possuem grau par e um deles faz parte do caminho C final senão o grafo não é conexo. É feito o mesmo processo com o grafo G' partindo de um ponto comum com o caminho C, obtendo um outro caminho C', e prosseguir com o processo ate obter um conjunto de caminhos e no final unir estes caminhos através do vértice em comum, onde um percurso continua o percurso do outro.

Algoritmo de Hierholzer

O algoritmo de Hierholzer consiste em, partir de um vértice aleatório, percorrer as arestas não visitadas de cada vértice até retornar ao vértice inicial, e havendo possibilidade de o ciclo não cobrir todas arestas do grafo, inicia-se novamente partindo de um vértice do ciclo formado (usando somente arestas não percorridas). Se não existir  mais aresta não visitada, é construído o ciclo euleriando a partir dos ciclos formados, unindo eles a partir de um vértice comum.

Suponhamos que um caminho de um vértice v1 até vk é representado por uma lista [v1, a1,..., ak-1, vk], que alterna vértices e arestas. Eis uma descrição do algoritmo de Hierholzer (supondo que já sabemos que o grafo é euleriano):

Descrição do algoritmo:

função Hierholzer(G = (V,E): grafo) : caminho

G' := G     { G' = (V', E')} v0 := um vértice de G'

C := [v0] {Inicialmente, o circuito contém só v0}

Enquanto E' não vazio vi := um vértice de C tal que d(vi) > 0 em G' C' := Circuito em G' que contém vi

G' := G' - {a | a é aresta contida em C'}

Em C, substituir o vértice vi pelo circuito C' Retornar C

Exemplo:

[pic 2]

Algoritmo de Fleury

O algoritmo de Fleury consiste em percorremos as arestas de forma aleatória, iniciando de um vértice qualquer, onde apaga-se as arestas já percorridas (apagando também caso apareça os vértices isolados), passando pelas pontes (se sua remoção produz um grafo com mais componentes conexos) apenas se não houver outra opção.