camino euleriano

Sendero en un gráfico que visita cada borde una vez

Los multigrafos de los puentes de Königsberg y de los acertijos de cinco habitaciones tienen más de dos vértices impares (en naranja), por lo que no son eulerianos y, por lo tanto, los acertijos no tienen solución.

Cada vértice de esta gráfica tiene un grado par . Por tanto, este es un grafo euleriano. Siguiendo los bordes en orden alfabético se obtiene un circuito/ciclo euleriano.

En teoría de grafos , un sendero euleriano (o camino euleriano ) es un sendero en un grafo finito que visita cada borde exactamente una vez (lo que permite volver a visitar los vértices). De manera similar, un circuito euleriano o ciclo euleriano es un sendero euleriano que comienza y termina en un mismo vértice . Fueron discutidos por primera vez por Leonhard Euler mientras resolvía el famoso problema de los Siete Puentes de Königsberg en 1736. El problema se puede plantear matemáticamente así:

Dado el gráfico de la imagen, ¿es posible construir un camino (o un ciclo ; es decir, un camino que comienza y termina en el mismo vértice) que visite cada borde exactamente una vez?

Euler demostró que una condición necesaria para la existencia de circuitos eulerianos es que todos los vértices del grafo tengan un grado par , y afirmó sin pruebas que los grafos conectados con todos los vértices de grado par tienen un circuito euleriano. La primera prueba completa de esta última afirmación fue publicada póstumamente en 1873 por Carl Hierholzer . ^[1] Esto se conoce como Teorema de Euler:

Un grafo conexo tiene un ciclo de Euler si y sólo si cada vértice tiene grado par.

El término gráfico euleriano tiene dos significados comunes en la teoría de grafos. Un significado es un gráfico con un circuito euleriano y el otro es un gráfico con cada vértice de grado par. Estas definiciones coinciden para gráficos conectados. ^[2]

Para la existencia de senderos eulerianos es necesario que cero o dos vértices tengan grado impar; esto significa que el gráfico de Königsberg no es euleriano. Si no hay vértices de grado impar, todos los caminos eulerianos son circuitos. Si hay exactamente dos vértices de grado impar, todos los senderos eulerianos comienzan en uno de ellos y terminan en el otro. Un grafo que tiene un sendero euleriano pero no un circuito euleriano se llama semieuleriano .

Definición

Un sendero euleriano , ^{[nota 1]} o paseo de Euler , en un grafo no dirigido es un paseo que utiliza cada arista exactamente una vez. Si tal recorrido existe, el grafo se llama transitable o semieuleriano . ^[3]

Un ciclo euleriano , ^{[nota 1]} también llamado circuito euleriano o recorrido de Euler , en un grafo no dirigido es un ciclo que utiliza cada arista exactamente una vez. Si tal ciclo existe, el grafo se llama eulerian o unicursal . ^[4] El término "gráfico euleriano" también se utiliza a veces en un sentido más débil para denotar un gráfico donde cada vértice tiene un grado par. Para gráficos finitos conectados, las dos definiciones son equivalentes, mientras que un gráfico posiblemente no conectado es euleriano en el sentido más débil si y sólo si cada componente conectado tiene un ciclo euleriano.

Para gráficos dirigidos , "ruta" debe reemplazarse por ruta dirigida y "ciclo" por ciclo dirigido .

La definición y las propiedades de los senderos, ciclos y gráficos eulerianos también son válidas para multigrafos .

Una orientación euleriana de un gráfico no dirigido G es una asignación de una dirección a cada borde de G tal que, en cada vértice v , el grado interno de v es igual al grado externo de v . Tal orientación existe para cualquier gráfico no dirigido en el que cada vértice tenga un grado par, y se puede encontrar construyendo un recorrido de Euler en cada componente conectado de G y luego orientando los bordes de acuerdo con el recorrido. ^[5] Cada orientación euleriana de un grafo conectado es una orientación fuerte , una orientación que hace que el grafo dirigido resultante sea fuertemente conexo .

Propiedades

• Un grafo no dirigido tiene un ciclo euleriano si y sólo si cada vértice tiene grado par y todos sus vértices con grado distinto de cero pertenecen a un único componente conectado .
• Un gráfico no dirigido se puede descomponer en ciclos de aristas disjuntas si y sólo si todos sus vértices tienen grados pares. Entonces, un gráfico tiene un ciclo euleriano si y solo si se puede descomponer en ciclos de aristas disjuntas y sus vértices de grados distintos de cero pertenecen a un solo componente conectado.
• Un grafo no dirigido tiene un sendero euleriano si y sólo si exactamente cero o dos vértices tienen grado impar y todos sus vértices con grado distinto de cero pertenecen a un único componente conectado.
• Un grafo dirigido tiene un ciclo euleriano si y sólo si cada vértice tiene igual grado y grado , y todos sus vértices con grado distinto de cero pertenecen a un único componente fuertemente conectado . De manera equivalente, un gráfico dirigido tiene un ciclo euleriano si y solo si se puede descomponer en ciclos dirigidos de aristas disjuntas y todos sus vértices con grados distintos de cero pertenecen a un único componente fuertemente conectado.
• Un grafo dirigido tiene un sendero euleriano si y sólo si como máximo un vértice tiene ( grado exterior ) − ( grado interior ) = 1, como máximo un vértice tiene (grado interior) – (grado exterior) = 1, cada otro vértice tiene el mismo grado de entrada y de salida, y todos sus vértices con grados distintos de cero pertenecen a un único componente conectado del gráfico no dirigido subyacente. ^{[ cita necesaria ]}

Construyendo senderos y circuitos eulerianos

Usar senderos eulerianos para resolver acertijos que implican dibujar una forma con un trazo continuo:

1. Como el rompecabezas de Haus vom Nikolaus tiene dos vértices impares (naranja), el sendero debe comenzar en uno y terminar en el otro.
2. El de Annie Pope con cuatro vértices impares no tiene solución.
3. Si no hay vértices impares, el sendero puede comenzar en cualquier lugar y formar un ciclo euleriano.
4. Los cabos sueltos se consideran vértices de grado 1.

algoritmo de fleury

El algoritmo de Fleury es un algoritmo elegante pero ineficiente que data de 1883. ^[6] Considere un gráfico que se sabe que tiene todas las aristas en el mismo componente y como máximo dos vértices de grado impar. El algoritmo comienza en un vértice de grado impar o, si el gráfico no tiene ninguno, comienza con un vértice elegido arbitrariamente. En cada paso, elige el siguiente borde en la ruta para que sea uno cuya eliminación no desconectaría el gráfico, a menos que no exista tal borde, en cuyo caso elige el borde restante que queda en el vértice actual. Luego se mueve al otro punto final de ese borde y lo elimina. Al final del algoritmo no quedan aristas, y la secuencia de la que se eligieron las aristas forma un ciclo euleriano si el gráfico no tiene vértices de grado impar, o un sendero euleriano si hay exactamente dos vértices de grado impar.

Si bien el recorrido del gráfico en el algoritmo de Fleury es lineal en el número de aristas, es decir , también debemos tener en cuenta la complejidad de detectar puentes . Si volvemos a ejecutar el algoritmo de búsqueda de puentes de tiempo lineal de Tarjan ^[7] después de eliminar cada borde, el algoritmo de Fleury tendrá una complejidad temporal de . Un algoritmo dinámico de búsqueda de puentes de Thorup (2000) permite mejorar esto , pero sigue siendo significativamente más lento que los algoritmos alternativos. ${\displaystyle O(|E|)}$ ${\displaystyle O(|E|^{2})}$ ${\displaystyle O(|E|\cdot \log ^{3}|E|\cdot \log \log |E|)}$

algoritmo de hierholzer

El artículo de Hierholzer de 1873 proporciona un método diferente para encontrar ciclos de Euler que es más eficiente que el algoritmo de Fleury:

• Elija cualquier vértice inicial v y siga un rastro de aristas desde ese vértice hasta regresar a v . No es posible quedarse atascado en ningún otro vértice que no sea v , porque el grado par de todos los vértices garantiza que, cuando el sendero entre en otro vértice w , debe haber un borde no utilizado que salga de w . El recorrido formado de esta manera es un recorrido cerrado, pero puede no cubrir todos los vértices y aristas del gráfico inicial.
• Siempre que exista un vértice u que pertenezca al recorrido actual pero que tenga aristas adyacentes que no formen parte del recorrido, comience otro recorrido desde u , siguiendo las aristas no utilizadas hasta regresar a u , y una el recorrido formado de esta manera con el anterior. recorrido.
• Como asumimos que el gráfico original es conexo , al repetir el paso anterior se agotarán todos los bordes del gráfico.

Al utilizar una estructura de datos como una lista doblemente enlazada para mantener el conjunto de aristas no utilizadas incidentes en cada vértice, para mantener la lista de vértices en el recorrido actual que tienen aristas no utilizadas y para mantener el recorrido en sí, las operaciones individuales del El algoritmo (encontrar bordes no utilizados que salen de cada vértice, encontrar un nuevo vértice inicial para un recorrido y conectar dos recorridos que comparten un vértice) se puede realizar en tiempo constante cada uno, por lo que el algoritmo general toma tiempo lineal . ^[8] ${\displaystyle O(|E|)}$

Este algoritmo también se puede implementar con un deque . Debido a que solo es posible quedarse atascado cuando el deque representa un recorrido cerrado, se debe rotar el deque quitando los bordes de la cola y agregándolos a la cabeza hasta que se despegue, y luego continuar hasta que se tengan en cuenta todos los bordes. Esto también requiere tiempo lineal, ya que el número de rotaciones realizadas nunca es mayor que (intuitivamente, cualquier borde "malo" se mueve a la cabeza, mientras que los bordes nuevos se agregan a la cola) ${\displaystyle |E|}$

Proyecciones ortográficas y diagramas de Schlegel con ciclos hamiltonianos de los vértices de los cinco sólidos platónicos – sólo el octaedro tiene trayectoria o ciclo euleriano, al extender su trayectoria con el punteado

• v
• t
• mi

Contando circuitos eulerianos

Problemas de complejidad

El número de circuitos eulerianos en dígrafos se puede calcular utilizando el llamado teorema BEST , que lleva el nombre de de B ruijn , van Aardenne - Ehrenfest , Smith y Tutte . La fórmula establece que el número de circuitos eulerianos en un dígrafo es el producto de ciertos factoriales de grado y el número de arborescencias arraigadas . Este último se puede calcular como un determinante , mediante el teorema del árbol matricial , dando un algoritmo de tiempo polinomial.

El teorema MEJOR se establece por primera vez en esta forma en una "nota agregada en la prueba" al artículo de Aardenne-Ehrenfest y de Bruijn (1951). La prueba original era biyectiva y generalizaba las secuencias de De Bruijn . Es una variación de un resultado anterior de Smith y Tutte (1941).

Contar el número de circuitos eulerianos en gráficos no dirigidos es mucho más difícil. Se sabe que este problema es #P-completo . ^[9] En una dirección positiva, se cree que un enfoque de Monte Carlo de la cadena de Markov , a través de las transformaciones de Kotzig (introducidas por Anton Kotzig en 1968) proporciona una aproximación clara para el número de circuitos eulerianos en un gráfico, aunque hasta el momento no existe prueba de este hecho (incluso para gráficos de grado acotado).

Casos especiales

McKay y Robinson (1995) determinaron una fórmula asintótica para el número de circuitos eulerianos en los gráficos completos : ^[10]

${\displaystyle \operatorname {ec} (K_{n})=2^{\frac {(n+1)}{2}}\pi ^{\frac {1}{2}}e^{{\frac {-n^{2}}{2}}+{\frac {11}{12}}}n^{\frac {(n-2)(n+1)}{2}}{\bigl (}1+O(n^{-{\frac {1}{2}}+\epsilon }){\bigr )}.}$

Posteriormente, MI Isaev (2009) obtuvo una fórmula similar para gráficos bipartitos completos : ^[11]

${\displaystyle \operatorname {ec} (K_{n,n})=\left({\frac {n}{2}}-1\right)!^{2n}2^{n^{2}-n+{\frac {1}{2}}}\pi ^{-n+{\frac {1}{2}}}n^{n-1}{\bigl (}1+O(n^{-{\frac {1}{2}}+\epsilon }){\bigr )}.}$

Aplicaciones

Los rastros eulerianos se utilizan en bioinformática para reconstruir la secuencia de ADN a partir de sus fragmentos. ^[12] También se utilizan en el diseño de circuitos CMOS para encontrar un orden óptimo de puertas lógicas . ^[13] Existen algunos algoritmos para procesar árboles que se basan en un recorrido de Euler del árbol (donde cada borde se trata como un par de arcos). ^{[14] [15]} Las secuencias de De Bruijn se pueden construir como senderos eulerianos de gráficos de De Bruijn . ^[dieciséis]

En gráficos infinitos

Un gráfico infinito con todos los grados de vértice iguales a cuatro pero sin línea euleriana

En un gráfico infinito , el concepto correspondiente a un sendero euleriano o ciclo euleriano es una línea euleriana, un sendero doblemente infinito que cubre todos los bordes del gráfico. No es suficiente para la existencia de tal sendero que el grafo esté conexo y que todos los grados de los vértices sean pares; por ejemplo, el gráfico infinito de Cayley que se muestra, con todos los grados de vértice iguales a cuatro, no tiene línea euleriana. Las gráficas infinitas que contienen líneas eulerianas fueron caracterizadas por Erdõs, Grünwald y Weiszfeld (1936). Para que un gráfico o multigrafo infinito G tenga una recta euleriana, es necesario y suficiente que se cumplan todas las condiciones siguientes: ^{[17] [18]}

• G es conexo.
• G tiene conjuntos numerables de vértices y aristas.
• G no tiene vértices de grado impar (finito).
• Eliminar cualquier subgrafo finito S de G deja como máximo dos componentes infinitos conectados en el gráfico restante, y si S tiene un grado par en cada uno de sus vértices, entonces eliminar S deja exactamente un componente infinito conectado.

Gráficos eulerianos no dirigidos

Euler estableció una condición necesaria para que un grafo finito sea euleriano, ya que todos los vértices deben tener grados pares. Hierholzer demostró que esta es una condición suficiente en un artículo publicado en 1873. Esto lleva a la siguiente afirmación necesaria y suficiente sobre lo que debe tener un grafo finito para ser euleriano: Un grafo finito conexo no dirigido es euleriano si y sólo si cada vértice de G tiene incluso grado. ^[19]

Veblen demostró el siguiente resultado en 1912: Un grafo conexo no dirigido es euleriano si y sólo si es la unión disjunta de algunos ciclos. ^[19]

Un grafo dirigido con todos los grados pares que no es euleriano, que sirve como contraejemplo a la afirmación de que una condición suficiente para que un grafo dirigido sea euleriano es que tenga todos los grados pares.

Hierholzer desarrolló un algoritmo de tiempo lineal para construir un recorrido euleriano en un gráfico no dirigido.

Gráficos eulerianos dirigidos

Es posible tener un gráfico dirigido que tenga todos los grados pares pero que no sea euleriano. Dado que un circuito euleriano sale de un vértice el mismo número de veces que entra en ese vértice, una condición necesaria para que exista un circuito euleriano es que los grados de entrada y salida sean iguales en cada vértice. Evidentemente, la conectividad también es necesaria. König demostró que estas condiciones también son suficientes. Es decir, un grafo dirigido es euleriano si y sólo si está conexo y los grados de entrada y salida son iguales en cada vértice. ^[19]

En este teorema no importa si "conectado" significa "débilmente conectado" o "fuertemente conectado", ya que son equivalentes para los gráficos eulerianos.

El algoritmo de tiempo lineal de Hierholzer para construir un recorrido euleriano también es aplicable a grafos dirigidos. ^[19]

Gráficos eulerianos mixtos

Este grafo mixto es euleriano. La gráfica es par pero no simétrica, lo que demuestra que la uniformidad y la simetría no son condiciones necesarias ni suficientes para que una gráfica mixta sea euleriana.

Se garantiza que todos los gráficos mixtos que sean pares y simétricos serán eulerianos. Sin embargo, esta no es una condición necesaria, ya que es posible construir un gráfico par, no simétrico, que sea euleriano. ^[20]

Ford y Fulkerson demostraron en 1962 en su libro Flujos en redes una condición necesaria y suficiente para que un grafo sea euleriano, es decir, que cada vértice debe ser par y satisfacer la condición de equilibrio, es decir, para cada subconjunto de vértices S, la diferencia entre el número de arcos que salen de S y entran en S debe ser menor o igual al número de aristas incidentes con S. ^[20]

El proceso de verificar si un grafo mixto es euleriano es más difícil que verificar si un grafo dirigido o no dirigido es euleriano porque la condición del conjunto equilibrado concierne a todos los subconjuntos posibles de vértices.

Un gráfico incluso mixto que viola la condición de conjunto equilibrado y, por tanto, no es eulerian.

Un gráfico mixto par que satisface la condición del conjunto equilibrado y, por tanto, es un gráfico mixto euleriano.

Ver también

• Matroide euleriana , una generalización abstracta de los gráficos eulerianos
• Rompecabezas de cinco habitaciones
• Lema del apretón de manos , probado por Euler en su artículo original, que muestra que cualquier gráfico conectado no dirigido tiene un número par de vértices de grado impar.
• Camino hamiltoniano : un camino que visita cada vértice exactamente una vez.
• Problema de inspección de ruta , busque el camino más corto que visite todos los bordes, posiblemente repitiendo bordes si no existe un camino euleriano.
• El teorema de Veblen , que establece que los gráficos con grados de vértice pares se pueden dividir en ciclos de aristas disjuntas independientemente de su conectividad

Notas

1. Algunas personas reservan los términos camino y ciclo para significar camino y ciclo que no se cruzan entre sí . Un camino (potencialmente) que se cruza a sí mismo se conoce como sendero o paseo abierto ; y un ciclo (potencialmente) autocruzado, un circuito o un paseo cerrado . Esta ambigüedad se puede evitar utilizando los términos sendero euleriano y circuito euleriano cuando se permite la autointersección.

Referencias

1. NL Biggs, EK Lloyd y RJ Wilson, Teoría de grafos, 1736-1936 , Clarendon Press, Oxford, 1976, 8-9, ISBN  0-19-853901-0 .
2. CL Mallows, NJA Sloane (1975). "Dos gráficos, clases de conmutación y gráficos de Euler son iguales en número" (PDF) . Revista SIAM de Matemática Aplicada . 28 (4): 876–880. doi :10.1137/0128070. JSTOR  2100368.
3. Jun-ichi Yamaguchi, Introducción a la teoría de grafos.
4. Esquema de la teoría de Schaum y los problemas de la teoría de grafos Por VK Balakrishnan [1].
5. Schrijver, A. (1983), "Límites del número de orientaciones eulerianas", Combinatorica , 3 (3–4): 375–380, doi :10.1007/BF02579193, MR  0729790, S2CID  13708977.
6. Fleury, Pierre-Henry (1883), "Deux problèmes de Géométrie de situación", Journal de mathématiques élémentaires , 2ª serie. (en francés), 2 : 257–261.
7. Tarjan, R. Endre (1974), "Una nota sobre cómo encontrar los puentes de un gráfico", Cartas de procesamiento de información , 2 (6): 160–161, doi :10.1016/0020-0190(74)90003-9, SEÑOR  0349483.
8. Fleischner, Herbert (1991), "Algoritmos X.1 para senderos eulerianos", Gráficos eulerianos y temas relacionados: Parte 1, Volumen 2, Annals of Discrete Mathematics, vol. 50, Elsevier, págs. X.1–13, ISBN 978-0-444-89110-5.
9. Brightwell y Winkler , "Nota sobre el conteo de circuitos eulerianos", 2004.
10. Brendan McKay y Robert W. Robinson, Enumeración asintótica de circuitos eulerianos en el gráfico completo, Combinatorica , 10 (1995), no. 4, 367–377.
11. MI Isaev (2009). "Número asintótico de circuitos eulerianos en gráficos bipartitos completos". Proc. 52ª Conferencia MFTI (en ruso). Moscú: 111-114.
12. Pevzner, Pavel A.; Tang, Haixu; Waterman, Michael S. (2001). "Un enfoque de sendero euleriano para el ensamblaje de fragmentos de ADN". Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 98 (17): 9748–9753. Código bibliográfico : 2001PNAS...98.9748P. doi : 10.1073/pnas.171285098 . PMC 55524 . PMID  11504945. 
13. Roy, Kuntal (2007). "Ordenación óptima de puertas lógicas CMOS utilizando el enfoque de ruta de Euler: algunas ideas y explicaciones". Revista de Computación y Tecnología de la Información . 15 (1): 85–92. doi : 10.2498/cit.1000731 .
14. Tarjan, Robert E.; Vishkin, Uzi (1985). "Un algoritmo eficiente de biconectividad paralela". Revista SIAM de Computación . 14 (4): 862–874. CiteSeerX 10.1.1.465.8898 . doi :10.1137/0214061. 
15. Berkman, Omer; Vishkin, Uzi (abril de 1994). "Encontrar ancestros de nivel en los árboles". J. Computación. Sistema. Ciencia . 2. 48 (2): 214–230. doi :10.1016/S0022-0000(05)80002-9.
16. Salvaje, Carla (enero de 1997). "Un estudio de códigos grises combinatorios". Revisión SIAM . 39 (4): 605–629. doi :10.1137/S0036144595295272. ISSN  0036-1445.
17. Komjáth, Peter (2013), "El trabajo de Erdős sobre gráficos infinitos", centenario de Erdös , Bolyai Soc. Matemáticas. Stud., vol. 25, János Bolyai Math. Soc., Budapest, págs. 325–345, doi :10.1007/978-3-642-39286-3_11, MR  3203602.
18. Bollobás, Béla (1998), Teoría de grafos moderna, Textos de Posgrado en Matemáticas, vol. 184, Springer-Verlag, Nueva York, pág. 20, doi :10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, señor  1633290.
19. Corberán, Ángel; Laporte, Gilbert, eds. (2015). Enrutamiento de arco | Biblioteca Digital SIAM. doi :10.1137/1.9781611973679. ISBN 978-1-61197-366-2. Consultado el 19 de agosto de 2022 . {{cite book}}: |website=ignorado ( ayuda )
20. Corberán, Ángel; Laporte, Gilbert, eds. (2015). Enrutamiento de arco | Biblioteca Digital SIAM. doi :10.1137/1.9781611973679. ISBN 978-1-61197-366-2. Consultado el 19 de agosto de 2022 . {{cite book}}: |website=ignorado ( ayuda )

Bibliografía

• Erdõs, Pál ; Grünwald, Tibor ; Weiszfeld, Endre (1936), "Végtelen gráfok Euler vonalairól" [Sobre líneas de Euler de gráficos infinitos] (PDF) , Mat. Arreglar. Lapok (en húngaro), 43 : 129-140. Traducido como Erdős, P .; Grünwald, T .; Vázsonyi, E. (1938), "Über Euler-Linien unendlicher Graphen" [Sobre líneas eulerianas en gráficos infinitos] (PDF) , J. Math. Física. (en alemán), 17 (1–4): 59–75, doi :10.1002/sapm193817159.
• Euler, L., "Solutio problematis ad geometriam situs pertinentis", Comentario. Academia de ciencia. I. Petropolitanae 8 (1736), 128-140.
• Hierholzer, Carl (1873), "Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren", Mathematische Annalen , 6 (1): 30–32, doi :10.1007/BF01442866, S2CID  119885172.
• Lucas, E., Récréations Mathématiques IV , París, 1921.
• Fleury, "Dos problemas de geometría de situación", Journal de mathematiques elementaires (1883), 257–261.
• T. van Aardenne-Ehrenfest y NG de Bruijn (1951) "Circuitos y árboles en gráficos lineales orientados", Simon Stevin 28: 203–217.
• Thorup, Mikkel (2000), "Conectividad gráfica totalmente dinámica casi óptima", Proc. 32º Simposio ACM sobre Teoría de la Computación , págs. 343–350, doi :10.1145/335305.335345, S2CID  128282
• WT Tutte y CAB Smith (1941) "Sobre caminos unicursales en una red de grado 4", American Mathematical Monthly 48: 233–237.

enlaces externos

• Discusión de las primeras menciones del algoritmo de Fleury.
• Gira de Euler en la Enciclopedia de Matemáticas .