PROBLEMAS DE RECORRIDO DE ARISTAS
Primero vamos a ver varias definiciones:
Siendo G un grafo conexo y, en general, no simple:
1. Llamaremos tour de G a una cadena cerrada que atraviesa cada arista de G al menos una vez.
2. Llamaremos tour euleriano de G a un tour de G que atraviesa cada arista exactamente una vez, no más.
3. Llamaremos gafo euleriano a aquel en el que podemos encontrar un tour euleriano.
4. Llamaremos camino euleriano a una cadena (simple) que atraviesa cada arista exactamente una vez.
Teoremas:
Sabiendo esto, podemos decir que para un grafo G no dirigido y conexo:
a. es euleriano si no tiene vértices de grado impar.
b. contiene un camino euleriano si y sólo si tiene exactamente dos vértices de grado impar.
Siendo G un grafo dirigido y débilmente conexo:
a. es euleriano si y sólo si, para todo vértice v, el grado de entrada es igual al grado de salida.
b. contiene un camino euleriano si y sólo si, para todo vértice v del camino, el grado de entrada es igual al de salida, siendo diferentes el vértice inicial y final del camino. Además, el grado de entrada del vértice inicial es uno menos que el de salida, y el grado de entrada del vértice final es uno mas que el de salida.
ALGORITMO DE FLEURY
El algoritmo de Fleury ayuda a encontrar un tour o camino euleriano en un grafo no dirigido. El método es el siguiente:
1. Si el grafo es euleriano, a partir de un vértice cualquiera de G, construiremos una cadena simple de forma que no se repitan aristas y no se elijan aristas de corte a no ser que no haya otra alternativa. Al finalizar este proceso, es decir, cuando hayamos agotado todas las aristas, habremos obtenido un tour euleriano.
Una arista de corte es una arista que, al eliminarla, se crea una nueva componente conexa, es decir, que divide el grafo.
2. Si el grafo contiene un camino euleriano, comenzaremos con un vértice de grado impar siguiente el proceso descrito en el punto 1.
Para grafos dirigidos se seguiría el siguiente procedimiento:
1. Si el grafo es euleriano, a partir de un vértice cualquiera de G construimos una cadena simple de forma que no se repitan arcos y no se elija nunca un arco si al eliminarlo aumenta el numero de componentes conexas del grafo no dirigido asociado, es decir, que ese arco no sea el equivalente a una arista de corte en el grafo no dirigido asociado, a no ser que no tengamos otra alternativa.
2. Si el grafo contiene un camino euleriano, comenzamos con un vértice p tal que el grado de entrada de p sea igual al de salida menos 1, y seguimos el proceso del punto 1.