Ayuda sobre algoritmos eulerianos

Haz click sobre el tema de ayuda que te interese


 


                                                               1. ¿Es euleriano?

                                                               2. Algoritmo de Hierholzer

                                                               3. Algoritmo de Fleury

                                                                       3.1 Recorrido del usuario

                                                                       3.2 Recorrido automático

                                                               4. Algoritmo de Tucker

                                                               5. Problema del cartero
 



        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.


        3.1 Recorrido del usuario.

                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.


        3.2 Recorrido automático.

                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.




        4. Algoritmo de Tucker.

                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.