Calcular o caminho euleriano em PHP

08/09/2008 Ler e Comentar

Um caminho euleriano em um grafo � o caminho que usa cada aresta exatamente uma vez. Se tal caminho existir, o grafo � chamado travers�vel. Um ciclo euleriano � um ciclo que usa cada aresta exatamente uma vez. O ciclo euleriano � utilizado para resolver o problema do caixeiro viajante.
Existe um conceito paralelo: um caminho hamiltoniano em um grafo � o caminho que visita cada nodo uma s� vez; e um ciclo hamiltoniano � um ciclo que visita cada v�rtice uma s� vez. O caminho hamiltoniano � utilizado para resolver o problema do carteiro chin�s.
O algoritmo a seguir descobre o ciclo euleriano utilizando "Cycle finding algorithm".

This algorithm is based on the following observation: if C is any cycle in a Eulerian graph, then after removing the edges of C, the remaining connected components will also be Eulerian graphs.
The algorithm consists in finding a cycle in the graph, removing its edges and repeating this steps with each remaining connected component. It has a very compact code with recursion:


'tour' is a stack

find_tour(u):

        for each edge e=(u,v) in E:

                remove e from E

                find_tour(v)

        prepend u to tour



to find the tour, clear stack 'tour' and call find_tour(u),

where u is any vertex with a non-zero degree.

<?php /** * Euler Walk * Encontra o caminho euleriano a partir de uma matriz de adjac�ncias * @author Pablo Dall'Oglio <pablo at dalloglio.net> */ // matriz de adjacencia $m[0] = array(0,1,1,0,0,0,0,0); $m[1] = array(1,0,0,0,1,0,0,0); $m[2] = array(1,0,0,1,1,0,0,0); $m[3] = array(0,0,1,0,0,0,0,0); $m[4] = array(0,1,1,0,0,1,1,0); $m[5] = array(0,0,0,0,1,0,0,1); $m[6] = array(0,0,0,0,1,0,0,1); $m[7] = array(0,0,0,0,0,1,1,0); // conta os impares $min_sum=INF; foreach ($m as $key => $row) { $sum = array_sum($row); if ($sum % 2 !== 0) { $odds[] = $key; if ($sum<$min_sum) { $min_sum=$sum; $min_key=$key; } } } reset($m); $odds[] = key($m); // se tem mais de tr�s nodos com qtde �mpar de arestas, // n�o h� como ter caminho euleriano if (count($odds)>3) { die("Mais de tres impares"); } // come�a pelo menor �mpar, sen�o come�a pelo primeiro $first = count($odds)>0 ? $min_key : key($m);; echo find_tour($m, $first); echo "$first\n"; /** * fun��o recursiva para encontrar * o caminho euleriano */ function find_tour(&$matriz, $vertice) { // echo "=>$vertice\n"; // descobre o proximo vertice foreach ($matriz as $key => $row) { if ($row[$vertice]) { // marca como visitado $matriz[$key][$vertice] = 0; $matriz[$vertice][$key] = 0; $next = $key; find_tour($matriz, $next); echo $next."\n"; } } } ?>

Coment�rios

Erros

Alguns coment�rios com rela��o a sua solu��o para o problema:
1) Seu algoritmo n�o determina o caminho euleriano, mas sim o ciclo euleriano.
2) A condi��o 'n�mero de v�rtices �mpares' > 3 n�o est� correta. Para existir um ciclo euleriano em um grafo n�o-dirigido, n�o devem haver v�rtices de grau �mpar. Para haver um caminho euleriano, no entanto, deve haver exatamente 2 v�rtices com grau �mpar.

Enviado por Luiz Ribeiro em 2008-11-29

Adicionar Coment�rio

Nome
Email
T�tulo
Coment�rio

Outros

Arquivo

Google

Blogroll

Posts Aleat�rios

Calcular o caminho euleriano em PHP

Coment�rios

Livros