Haz click sobre el tema de ayuda que te interese
1. ¿Es euleriano?
Caracterización grafos no dirigidos
Un grafo conexo G es euleriano si y sólo si todos los vértices de G tienen grado par.
Caracterización grafos dirigidos
Un grafo dirigido conexo G es euleriano si y sólo si todos los vértices
tienen igual grado de entrada
que de salida.
Corolario
Un grafo conexo G posee un recorrido euleriano no cerrado si y sólo
si G tiene exactamente dos vértices
impares (grafos no dirigidos).
En grafos dirigidos si tiene exactamente dos vértices con grado
de entrada distinto al grado de salida.
En esta opción de menú se indica si el grafo del área
de trabajo es o no euleriano. En caso de no serlo indica
las condiciones que no cumple el grafo para ser euleriano.
2 ejemplos: uno de grafo no euleriano y otro de grafo euleriano.
A continuación se muestra un ejemplo de la salida que muestra el
programa para un grafo no euleriano.
2. Algoritmo de Hierholzer
Este algoritmo, desarrollado por Hierholzer en 1873 construye un recorrido
euleriano en un grafo
conexo G cuyos vértices tienen todos grado par.
Las condiciones que debe cumplir el grafo para ejecutar el algoritmo de
Hierholzer son:
- Conexo.
- Todos los vértices de grado par (grafos no dirigidos) o todos
los vértices con grado de entrada igual
al grado de salida (grafos dirigidos).
Los pasos del algoritmo son:
1 - Se elige un vértice v y se construye un circuito C0
(recorrido cerrado sin repetición de aristas),
empezando en v y avanzando, en cada paso, por una arista no incluida en
el circuito.
Hacemos i = 0
2 - Si A(Ci)=A(G) entonces se termina pues Ci es
el circuito euleriano buscado.
Si hay aristas en G no usadas en el circuito Ci elegimos un
vértice vi en Ci que sea incidente con una
arista de G que no esté en Ci.
Construimos ahora un circuito Ci* empezando en vi
en el grafo G-A(Ci).
3 - Construimos el circuito Ci+1 que contiene las aristas de
Ci y de Ci* empezando en v, recorriendo
Ci hasta alcanzar vi, siguiendo por Ci*
hasta completarlo volviendo a vi y terminando el recorrido
por Ci hasta volver a v.
Hacemos i=i+1 y volvemos a 2.
En esta opción de menú se construye un recorrido euleriano
cerrado sobre el grafo del área de trabajo.
Si el grafo no cumple las condiciones para ejecutar el algoritmo se muestra
un mensaje informativo
indicando cuales son las condiciones que no cumple.
El algoritmo se puede ejecutar de forma completa o paso a paso.
En modo de ejecución completa se muestra el resultado final
del algoritmo.
En modo de ejecución paso a paso se muestran además
los resultados intermedios en la ejecución
del algoritmo.
En este algoritmo, en el recorrido euleriano construido las aristas que
pertenecen al mismo circuito están
pintadas con el mismo color. Así nos podemos hacer una mejor idea
de los pasos intermedios para
construir el recorrido.
3. Algoritmo de Fleury
Quizá el más antiguo de los algoritmos que construyen recorridos
eulerianos sea el de Fleury.
La idea es ir añadiendo aristas a un recorrido hasta completar
el recorrido euleriano.
Algunas aplicaciones requieren recorridos eulerianos abiertos, que no terminen
en el mismo vértice de inicio.
El algoritmo de Fleury construye recorridos eulerianos abiertos, si hay
sólo 2 vértices de grado impar.
Las condiciones que debe cumplir el grafo para ejecutar el algoritmo de
Fleury son:
- Conexo.
- Con todos sus vértices pares (recorrido cerrado) o con sólo
2 impares (recorrido abierto) (Grafos no dirigidos)
Con todos sus vértices con igual grado de entrada y de salida (recorrido
cerrado) o con sólo
2 vértices con distinto grado de entrada que de salida (recorrido
abierto).
Los pasos del algoritmo son:
Se comienza en un vértice impar salvo que todos los vértices
sean pares, en cuyo caso se empieza en
un vértice cualquiera v0.
Hacer
Si se ha construido el camino v0 a1 v1
a2...vk-1 ak vk con aristas
distintas, se elige la arista
siguiente ak+1 con las condiciones:
(1) ak+1 incidente con vk
(2) no ser puente en el grafo G - {a1,a2,...,ak}
(salvo que no haya alternativa).
Hasta que el camino contenga todas las aristas.
En esta opción de menú es el usuario el que va construyendo
el recorrido euleriano.
Para ello, en el cuadro de resultados se le muestran mensajes que le ayudan
a construirlo.
Ejemplo de mensaje de ayuda:
Si el grafo no cumple alguna condición para ejecutar el algoritmo
se muestra un mensaje informando de
cuales son las condiciones que no cumple.
Para ir construyendo el recorrido el usuario debe ir pinchando en los vértices
del grafo. 2 vértices
definen una arista. Por lo que si queremos continuar por una arista determinada
debemos pinchar en los
vértices extremos de esa aristas.
El algoritmo finaliza cuando se han pinchado en todas las aristas.
En esta opción de menú el recorrido euleriano lo construye
el ordenador.
Si el grafo no cumple alguna condición para ejecutar el algoritmo
se muestra un mensaje informando de
cuales son las condiciones que no cumple.
Se permite ejecutar en modo completo o paso a paso.
Tucker desarrolló un algoritmo que esencialmente es una combinación
de los algoritmos de Hierholzer y Fleury.
El algoritmo de Tucker consiste en separar las aristas hasta formar una
partición del grafo en ciclos.
Después hay que reensamblar los ciclos de una forma controlada,
construyendo a su vez el recorrido euleriano.
Las condiciones que debe cumplir el grafo para ejecutar el algoritmo de
Hierholzer son:
- Conexo.
- Todos los vértices de grado par (grafos no dirigidos) o todos
los vértices con grado de entrada igual
al grado de salida (grafos dirigidos).
Los pasos del algoritmo son:
Separar pares de aristas de G hasta que sólo haya vértices
de grado 2.
Al grafo obtenido de esta forma le llamamos G1.
Hacemos i = 1. ci = número de componentes de Gi.
Bucle
Si ci = 1 entonces
Paramos y devolvemos C = Gi
Si no
Escogemos 2 componentes T y T* de Gi con un vértice vi
en común.
Formamos un circuito Ci+1 empezando en vi y recorriendo
T y T*, finalizando de nuevo en vi.
Definir Gi+1 = Gi - {T,T*} U Ci+1. (Consideramos
Ci+1 como una componente de Gi+1).
Hacemos T = Ci+1, i = i + 1, ci = número de
componentes de Gi.
Fin bucle
Si el grafo no cumple las condiciones para ejecutar Tucker se muestra un
mensaje informando de cuales
son las condiciones que no cumple.
Después de hacer estas comprobaciones pregunta al usuario si quiere
ejecución completa o paso a paso.
En la ejecución paso a paso, primeramente distribuye los
vértices en forma de círculo para una
mejor visualización del algoritmo. Posteriormente, sigue con la
ejecución del algoritmo.
Puede ocurrir que en el proceso de duplicación de vértices,
se supere el máximo número de vértices
de un grafo (50 vértices). En este caso, restaura el grafo, muestra
un mensaje informativo y termina
la ejecución del algoritmo.
Una vez terminado el algoritmo, restaura las posiciones de los vértices
y muestra el resultado final.
Las aristas que forman parte de la misma componente conexa en el grafo
resultamte de duplicar vértices
para que todos tengan grado 2 (o grado de entrada = grado de salida = 1)
tendrán el mismo color.
Las aristas que formen parte de distintas componentes conexas tendrán
distinto color.
5. Problema del cartero.
El matemático chino Meigu Guan introdujo el problema de encontrar
el recorrido cerrado de mínimo coste
atravesando cada arista de un grafo al menos una vez.
Guan planteó el problema de un cartero que sale de la estafeta,
recorre todas las calles de su barrio y vuelve
a la estafeta. Es decir, en su recorrido debe pasar al menos una vez por
cada arista del grafo que modela
las calles del barrio. Al cartero le interesa caminar la menor distancia
posible.
El objetivo del Problema del Cartero es, por tanto, encontrar un recorrido
de ese tipo en un grafo ponderado
y con mínimo peso.
Desde luego, si el grafo correspondiente es euleriano, cualquier recorrido
euleriano cerrado es el
recorrido óptimo buscado. Pero si no lo es, algunas aristas deben
atravesarse más de una vez.
Es fácil ver que cada recorrido de cartero de un grafo G corresponde
a un recorrido euleriano de un
grafo G* construido a partir de G añadiendo aristas para hacer que
todos los vértices tengan grado par.
Las condiciones que debe cumplir el grafo son:
- Conexo (y con aristas).
- Ponderado.
Los pasos del algoritmo son:
1-
Hallar el conjunto de vértices impares S de G.
Para cada par de vértices u, v que pertenecen a S, hallar el camino
más corto de u a v y su longitud duv
2-
Construir el grafo completo sobre el conjunto S.
Asignar a cada arista uv el peso duv.
3-
Hallar un emparejamiento perfecto M en el grafo anterior KS
de peso mínimo.
4-
Construir un grafo G* a partir de G añadiendo las siguientes aristas:
Para cada arista e del emparejamiento anterior M, tomar el camino mínimo
P correspondiente de G
y duplicar en G las aristas correspondientes.
5-
Construir un recorrido euleriano en G*. Este será el recorrido del
cartero en G.
Si el grafo no cumple las condiciones para ejecutar el algoritmo del cartero,
se muestra un mensaje informativo
y termina la ejecución del algoritmo. Si cumple con las condiciones
pregunta al usuario si quiere ejecución
completa o paso a paso.