Diferencias
Muestra las diferencias entre dos versiones de la página.
Próxima revisión | Revisión previa | ||
algoritmo_hierholzer [2012/05/18 09:02] – creado admin | algoritmo_hierholzer [2023/03/13 14:40] (actual) – editor externo 127.0.0.1 | ||
---|---|---|---|
Línea 2: | Línea 2: | ||
**// | **// | ||
+ | {{ : | ||
+ | Hierholzer demostró que un grafo tiene un ciclo euleriano si y sólo si es conexo y cada vértice tiene grado par. Este resultado había sido dado, sin demostración, | ||
+ | Puede encontrar más información en: | ||
+ | |||
+ | * [[http:// | ||
+ | * [[http:// | ||
Línea 11: | Línea 17: | ||
A continuación se muestra el pseudocódigo del Algoritmo: | A continuación se muestra el pseudocódigo del Algoritmo: | ||
< | < | ||
+ | ListaArcosCircuito_K = vacío | ||
+ | NodoUsado = false | ||
+ | ArcoDisponible = true | ||
+ | se toma NodoInicial | ||
+ | NodoUsado(NodoInicial) = true | ||
+ | Añadir NodoInicial a ListaNodosUsados | ||
+ | | ||
+ | |||
+ | DO UNTIL que ListaNodosUsados = vacío | ||
+ | Tomar último vértice u en ListaNodosUsados | ||
+ | | ||
+ | | ||
+ | |||
+ | | ||
+ | |||
+ | | ||
+ | |||
+ | LOOP | ||
</ | </ | ||
+ | |||
+ | ==ejemplo de circuito euleriano== | ||
+ | Para comprender mejor el funcionamiento del algoritmo de Hierholzer puede seguir este sencillo ejemplo. En primer lugar construya el siguiente grafo euleriano a partir de su matriz de distancias. | ||
+ | |||
+ | < | ||
+ | N1\N2 1 2 3 4 5 6 7 8 9 | ||
+ | 1 1 1 1 | ||
+ | 2 1 | ||
+ | 3 1 | ||
+ | 4 1 | ||
+ | 5 1 1 | ||
+ | 6 1 | ||
+ | 7 1 | ||
+ | 8 1 | ||
+ | 9 1 | ||
+ | </ | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | El resultado dibujado será más o menos como muestra la siguiente imagen. | ||
+ | {{ : | ||
+ | |||
+ | Seguidamente, | ||
+ | {{ : | ||
+ | |||
+ | Rápidamente aparecerá la solución, marcando los arcos del circuito euleriano: | ||
+ | {{ : | ||
+ | |||
+ | y la ventana con el texto de la solución: | ||
+ | < | ||
+ | Arcos del circuito euleriano: | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | Coste total = 12 | ||
+ | |||
+ | Secuencia de nodos en el circuito: | ||
+ | 1-2-3-1-4-5-6-7-5-8-1-9-1 | ||
+ | </ | ||
+ | |||
+ | Como este grafo es de grado par, el grafo es euleriano. En este caso, su grado máximo es 6, y su grado mínimo es 2. | ||
+ | |||
+ | En el caso de que el grafo no sea euleriano, Grafos le informará automáticamente y el algoritmo no se ejecutará. En ese caso, puede probar a cambiar las conexiones entre los vértices para intentar construir un circuito euleriano. | ||
+ | |||
+ | ~~NOTOC~~ |