Camino euleriano

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

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

Cada vértice de este grafo tiene un grado par. Por lo tanto, se trata de un grafo euleriano. Siguiendo las aristas 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 arista 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 el mismo vértice . Leonhard Euler los analizó por primera vez al resolver el famoso problema de los Siete Puentes de Königsberg en 1736. El problema se puede plantear matemáticamente de la siguiente manera:

Dado el gráfico de la imagen, ¿es posible construir una ruta (o un ciclo ; es decir, una ruta que comienza y termina en el mismo vértice) que visite cada arista 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 prueba que los grafos conexos 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 el Teorema de Euler:

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

El término grafo euleriano tiene dos significados comunes en la teoría de grafos. Uno de ellos es el de grafo con un circuito euleriano y el otro es el de grafo con todos los vértices de grado par. Estas definiciones coinciden para los grafos conexos. ^[2]

Para que existan caminos eulerianos es necesario que ninguno o dos vértices tengan grado impar ; esto significa que el grafo 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 caminos eulerianos empiezan en uno de ellos y terminan en el otro. Un grafo que tiene un camino 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 existe tal paseo, el grafo se denomina 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 existe tal ciclo, el grafo se llama euleriano o unicursal . ^{[4] El término "grafo euleriano" también se usa a veces en un sentido más débil para denotar un grafo donde cada vértice tiene grado par. Para} grafos conexos finitos las dos definiciones son equivalentes, mientras que un grafo posiblemente no conexo es euleriano en el sentido más débil si y solo si cada componente conexo tiene un ciclo euleriano.

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

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

Una orientación euleriana de un grafo no dirigido G es una asignación de una dirección a cada arista de G tal que, en cada vértice v , el grado de entrada de v es igual al grado de salida de v . Tal orientación existe para cualquier grafo no dirigido en el que cada vértice tiene grado par, y puede encontrarse construyendo un recorrido de Euler en cada componente conexo de G y luego orientando las aristas de acuerdo con el recorrido. ^[5] Cada orientación euleriana de un grafo conexo 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 conexo . ^[6]
• Un grafo no dirigido puede descomponerse en ciclos disjuntos en sus aristas si y solo si todos sus vértices tienen grado par. Por lo tanto, un grafo tiene un ciclo euleriano si y solo si puede descomponerse en ciclos disjuntos en sus aristas y sus vértices de grado distinto de cero pertenecen a un único componente conexo.
• Un gráfico no dirigido tiene un recorrido euleriano si y solo 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 ^[6].
• Un grafo dirigido tiene un ciclo euleriano si y solo si cada vértice tiene igual grado de entrada y grado de salida , y todos sus vértices con grado distinto de cero pertenecen a un único componente fuertemente conexo . De manera equivalente, un grafo dirigido tiene un ciclo euleriano si y solo si se puede descomponer en ciclos dirigidos disjuntos en sus aristas y todos sus vértices con grado distinto de cero pertenecen a un único componente fuertemente conexo. ^[6]
• Un grafo dirigido tiene un camino euleriano si y solo si como máximo un vértice tiene ( grado de salida ) − ( grado de entrada ) = 1, como máximo un vértice tiene ( grado de entrada ) − ( grado de salida ) = 1, cada otro vértice tiene igual grado de entrada y grado de salida, y todos sus vértices con grado distinto de cero pertenecen a un único componente conexo del grafo no dirigido subyacente. ^[6]

Construcción de senderos y circuitos eulerianos

Uso de senderos eulerianos para resolver problemas que implican dibujar una forma con un trazo continuo:

1. Como el rompecabezas de Haus vom Nikolaus tiene dos vértices impares (naranja), el recorrido debe comenzar en uno y terminar en el otro.
2. El problema de Annie Pope con cuatro vértices impares no tiene solución.
3. Si no hay vértices impares, el recorrido 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. ^[7] Consideremos un grafo 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 grafo no tiene ninguno, comienza con un vértice elegido arbitrariamente. En cada paso, elige la siguiente arista en el camino para que sea una cuya eliminación no desconecte el grafo, a menos que no exista dicha arista, en cuyo caso elige la arista restante que queda en el vértice actual. Luego se mueve al otro punto final de esa arista y elimina la arista. Al final del algoritmo, no quedan aristas, y la secuencia de la que se eligieron las aristas forma un ciclo euleriano si el grafo 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 grafo 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 ^[8] después de la eliminación de cada arista, el algoritmo de Fleury tendrá una complejidad de tiempo de . Un algoritmo dinámico de búsqueda de puentes de Thorup (2000) permite mejorar esto a , pero esto 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 un vértice inicial cualquiera v y siga un rastro de aristas desde ese vértice hasta regresar a v . No es posible quedarse atascado en ningún vértice que no sea v , porque el grado par de todos los vértices garantiza que, cuando el rastro entre en otro vértice w, debe haber una arista sin usar 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 grafo inicial.
• Mientras exista un vértice u que pertenezca al recorrido actual pero que tenga aristas adyacentes que no formen parte del recorrido, se inicia otro recorrido desde u , siguiendo las aristas no utilizadas hasta volver a u , y se une el recorrido así formado al recorrido anterior.
• Como suponemos que el gráfico original está conexo , repetir el paso anterior agotará 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 a 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 algoritmo (encontrar aristas no utilizadas que salen de cada vértice, encontrar un nuevo vértice de inicio para un recorrido y conectar dos recorridos que comparten un vértice) se pueden realizar en tiempo constante cada una, por lo que el algoritmo general toma un tiempo lineal , . ^[9] ${\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 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 la cantidad 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 un camino o ciclo euleriano, al prolongar su camino con el punteado

• en
• a
• mi

Contando circuitos eulerianos

Problemas de complejidad

El número de circuitos eulerianos en dígrafos se puede calcular utilizando el llamado teorema BEST , llamado así por de Bruijn , 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 enraizadas . Este último se puede calcular como determinante , mediante el teorema del árbol matricial , dando un algoritmo de tiempo polinomial.

El teorema BEST se enuncia por primera vez en esta forma en una "nota añadida a la prueba" del 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 grafos no dirigidos es mucho más difícil. Se sabe que este problema es #P-completo . ^[10] En una dirección positiva, se cree que un enfoque de Monte Carlo de cadena de Markov , a través de las transformaciones de Kotzig (introducidas por Anton Kotzig en 1968) proporciona una aproximación precisa para el número de circuitos eulerianos en un grafo, aunque hasta ahora no hay prueba de este hecho (incluso para grafos 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 : ^[11]

${\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 )}.}$

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

${\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 senderos eulerianos se utilizan en bioinformática para reconstruir la secuencia de ADN a partir de sus fragmentos. ^[13] También se utilizan en el diseño de circuitos CMOS para encontrar un ordenamiento de puertas lógicas óptimo . ^[14] Hay 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). ^{[15] [16]} Las secuencias de De Bruijn se pueden construir como senderos eulerianos de grafos de De Bruijn . ^[17]

En grafos infinitos

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

En un grafo infinito , el concepto correspondiente a un camino euleriano o ciclo euleriano es una línea euleriana, un camino doblemente infinito que cubre todas las aristas del grafo. No es suficiente para la existencia de dicho camino que el grafo sea conexo y que todos los grados de los vértices sean pares; por ejemplo, el grafo infinito de Cayley mostrado, con todos los grados de los vértices iguales a cuatro, no tiene línea euleriana. Los grafos infinitos que contienen líneas eulerianas fueron caracterizados por Erdõs, Grünwald y Weiszfeld (1936). Para que un grafo infinito o multigrafo G tenga una línea euleriana, es necesario y suficiente que se cumplan todas las siguientes condiciones: ^{[18] [19]}

• G está conectado.
• G tiene conjuntos contables de vértices y aristas.
• G no tiene vértices de grado impar (finito).
• Al eliminar cualquier subgrafo finito S de G quedan como máximo dos componentes conexos infinitos en el grafo restante, y si S tiene grado par en cada uno de sus vértices, entonces al eliminar S quedan exactamente un componente conexo infinito.

Grafos eulerianos no dirigidos

Euler enunció una condición necesaria para que un grafo finito sea euleriano, ya que todos los vértices deben tener un grado par. Hierholzer demostró que esta es una condición suficiente en un artículo publicado en 1873. Esto conduce 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 solo si cada vértice de G tiene un grado par. ^[20]

El siguiente resultado fue demostrado por Veblen en 1912: Un grafo conexo no dirigido es euleriano si y sólo si es la unión disjunta de algunos ciclos. ^[20]

Un gráfico 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 gráfico 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.

Grafos eulerianos dirigidos

Es posible tener un grafo dirigido que tenga todos los grados de salida 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 él, una condición necesaria para que exista un circuito euleriano es que el grado de entrada y el grado de salida sean iguales en cada vértice. Obviamente, 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 solo si es conexo y el grado de entrada y el grado de salida son iguales en cada vértice. ^[20]

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 gráficos dirigidos. ^[20]

Grafos eulerianos mixtos

Este grafo mixto es euleriano. El grafo es par pero no simétrico, lo que demuestra que la paridad y la simetría no son condiciones necesarias ni suficientes para que un grafo mixto sea euleriano.

Se garantiza que todos los grafos mixtos que sean pares y simétricos son eulerianos. Sin embargo, esto no es una condición necesaria, ya que es posible construir un grafo no simétrico, par, 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, a saber, 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 que el número de aristas incidentes con S. ^[20]

El proceso de comprobar si un gráfico mixto es euleriano es más difícil que comprobar si un gráfico dirigido o no dirigido es euleriano porque la condición del conjunto equilibrado concierne a cada posible subconjunto de vértices.

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

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

Véase también

• Matroide euleriano , una generalización abstracta de los grafos eulerianos
• Rompecabezas de cinco habitaciones
• Lema del apretón de manos , demostrado por Euler en su artículo original, que muestra que cualquier gráfico conexo 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 , búsqueda del camino más corto que visite todos los bordes, posiblemente repitiendo bordes si no existe un camino euleriano.
• Teorema de Veblen , que establece que los gráficos con grado de vértice par se pueden dividir en ciclos disjuntos en las aristas independientemente de su conectividad.

Notas

1. Algunas personas reservan los términos camino y ciclo para referirse a caminos y ciclos que no se autointersecan . Un camino (potencialmente) autointersecan se conoce como sendero o paseo abierto ; y un ciclo (potencialmente) autointersecante, como circuito o 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). "Los dos grafos, las clases de conmutación y los grafos de Euler son iguales en número" (PDF) . Revista SIAM de Matemáticas Aplicadas . 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 Schaum de la teoría y los problemas de la teoría de grafos Por VK Balakrishnan [1].
5. Schrijver, A. (1983), "Límites en el número de orientaciones eulerianas", Combinatorica , 3 (3–4): 375–380, doi :10.1007/BF02579193, MR  0729790, S2CID  13708977.
6. Pólya, George ; Tarjan, Robert E. ; Woods, Donald R. (octubre de 2009), "Caminos hamiltonianos y eulerianos", Notas sobre combinatoria introductoria , Birkhäuser Boston, págs. 157-168, doi :10.1007/978-0-8176-4953-1_13, ISBN 9780817649531
7. 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.
8. Tarjan, R. Endre (1974), "Una nota sobre cómo encontrar los puentes de un gráfico", Information Processing Letters , 2 (6): 160–161, doi :10.1016/0020-0190(74)90003-9, MR  0349483.
9. Fleischner, Herbert (1991), "X.1 Algoritmos para senderos eulerianos", Grafos eulerianos y temas relacionados: Parte 1, Volumen 2, Anales de matemáticas discretas, vol. 50, Elsevier, págs. X.1–13, ISBN 978-0-444-89110-5.
10. Brightwell y Winkler , "Nota sobre el conteo de circuitos eulerianos", 2004.
11. Brendan McKay y Robert W. Robinson, Enumeración asintótica de circuitos eulerianos en el gráfico completo, Combinatorica , 10 (1995), n.º 4, 367–377.
12. MI Isaev (2009). "Número asintótico de circuitos eulerianos en grafos bipartitos completos". Proc. 52.ª Conferencia MFTI (en ruso). Moscú: 111–114.
13. 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. Bibcode :2001PNAS...98.9748P. doi : 10.1073/pnas.171285098 . PMC 55524 . PMID  11504945. 
14. Roy, Kuntal (2007). "Ordenamiento óptimo de puertas lógicas CMOS mediante el enfoque de trayectorias de Euler: algunas ideas y explicaciones". Revista de informática y tecnología de la información . 15 (1): 85–92. doi : 10.2498/cit.1000731 .
15. 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. 
16. Berkman, Omer; Vishkin, Uzi (abril de 1994). "Encontrar ancestros de nivel en árboles". J. Comput. Syst. Sci . 2. 48 (2): 214–230. doi :10.1016/S0022-0000(05)80002-9.
17. Savage, Carla (enero de 1997). "Un estudio de los códigos combinatorios de Gray". SIAM Review . 39 (4): 605–629. doi :10.1137/S0036144595295272. ISSN  0036-1445.
18. 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.
19. Bollobás, Béla (1998), Teoría de grafos moderna, Textos de posgrado en matemáticas, vol. 184, Springer-Verlag, Nueva York, p. 20, doi :10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, Sr.  1633290.
20. Corberán, Ángel; Laporte, Gilbert, eds. (2015). Enrutamiento de arcos: problemas, métodos y aplicaciones. Serie MOS-SIAM sobre optimización. SIAM. doi :10.1137/1.9781611973679. ISBN 978-1-61197-366-2. Recuperado el 19 de agosto de 2022 .

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, "Deux 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 completamente 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 Enciclopedia de Matemáticas .