Diferencia entre revisiones de «Ciclo euleriano»
Contenido eliminado Contenido añadido
m Pequeñas correcciones WP:CEM. |
|||
Línea 49:
* Un grafo no dirigido se dice que es susceptible de ser recorrido (en inglés: '''traversable''') si es conexo y dos vértices en el grafo tienen grado impar.
==
===Algoritmo de Fleury===
El algoritmo de Fleury es un algoritmo elegante pero inefeciente cuyo origen se remonta al año 1883. Considerando un grafo del que sabemos que todas las líneas en la misma componente y al menos dos vértices de ángulo impar. El algoritmo comienza en el vértice del ángulo impar. En cada paso se elige el siguiente lado que queda unido al punto anterior por una sola línea. Finalmente nos movemos al lado que queda en el vértice sobrante. Al concluir el
La complejidad correspondiente a este algoritomo es O(n^2), aunque hace unos años, esta fue mejorada hasta alcanzar una complejidad <math>O(|E|(\log|E|)^3\log\log|E|)</math> pero sigue siendo todavía un recorrido más lento que otros algoritmos.
====
<source lang="cpp">
// Implemetación en c++
Línea 197:
El documento recogido en 1873 procedente de Hierholzer, proporciona un método diferente a la hora de recorrer los ciclos eulerianos de una forma más eficiente que los algoritmos de Fleury. A continuación se mostraran los pasos necesarios para este algoritmo:
*Elegir cualquier vértice ''v'' para empezar, y seguir el recorrido de una línea hasta llegar de nuevo a ''v''. No es posible dejar de avanzar en cualquier vértice que no sea ''v'', ya que incluso el grado de todos los vértices asegura que cuando se realiza una traza, deben usarse todas
*Mientras que exista un vértice ''u'' que pertenezca al actual recorrido pero que tenga lados adyacentes no pertenecientes a la traza, se comienza de nuevo desde ''u'', siguiendo los lados no usados hasta regresar a ''u'', y unir el recorrido formado durante esta traza a la anterior.
Línea 219:
== Referencias ==
* "Solutio problematis ad geometriam situs pertinentis", Euler, L.,''Comment. Academiae Sci. I. Petropolitanae'' '''8''' (1736), 128-140.
* "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechnung zu umfahren", Hierholzer, C. ''[[Mathematische Annalen]]'' '''6''' (1873), 30-32.
* ''Récréations Mathématiques IV'', Lucas, E., Paris, 1921.
* "Deux problemes de geometrie de situation", Fleury, ''Journal de mathematiques elementaires'' (1883), 257-261.
| |||