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 . Leonhard Euler los discutió por primera vez 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 declaró sin prueba que los gráficos 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:
El término grafo 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 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 gráfico que tiene un rastro euleriano pero no un circuito euleriano se llama semi-euleriano .
Un sendero euleriano , [3] o paseo de Euler en un gráfico no dirigido es un paseo que usa cada borde exactamente una vez. Si existe tal caminata, el gráfico se llama transitable o semi-euleriano . [4]
Un ciclo euleriano , [3] circuito euleriano o recorrido de Euler en un gráfico no dirigido es un ciclo que usa cada borde exactamente una vez. Si tal ciclo existe, el gráfico se llama euleriano o unicursal . [5] El término "gráfico 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 conectados finitos, las dos definiciones son equivalentes, mientras que un gráfico posiblemente no conectado es euleriano en el sentido más débil si y solo si cada componente conectado tiene un ciclo euleriano.
1. Como el acertijo de Haus vom Nikolaus tiene dos vértices impares (naranja), el camino 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 forma un ciclo euleriano.
4. Los extremos sueltos se consideran vértices de grado 1.
