camino euleriano
En la teoría de grafos , un camino euleriano (o camino euleriano ) es un camino en un gráfico 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 camino euleriano que comienza y termina en el 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í:
Euler demostró que una condición necesaria para la existencia de circuitos eulerianos es que todos los vértices del gráfico tengan un grado par y afirmó sin prueba que los gráficos 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:
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 todos los vértices de grado par. Estas definiciones coinciden para grafos conexos. [2]
Para la existencia de senderos eulerianos es necesario que cero o dos vértices tengan un grado impar; esto significa que el gráfico de Königsberg no es euleriano. Si no hay vértices de grado impar, todos los senderos 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 una estela euleriana pero no un circuito euleriano se llama semi-euleriano .
Un camino euleriano , [3] o un camino de Euler en un gráfico no dirigido es un camino que usa cada borde exactamente una vez. Si tal paseo existe, el grafo se llama transitable o semi-euleriano . [4]
Un ciclo euleriano , [3] un circuito euleriano o un recorrido euleriano en un grafo no dirigido es un ciclo que utiliza cada arista exactamente una vez. Si tal ciclo existe, el grafo se llama euleriano o unicursal . [5] El término "grafo euleriano" también se usa 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 conexos finitos , las dos definiciones son equivalentes, mientras que un gráfico posiblemente no conexo es euleriano en el sentido más débil si y solo si cada componente conexo tiene un ciclo euleriano.
1. Como el rompecabezas 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 camino puede comenzar en cualquier lugar y formar un ciclo euleriano.
4. Los cabos sueltos se consideran vértices de grado 1.
