OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
===== Camino euleriano =====

Un camino euleriano es un camino que pasa por todas las aristas de un grafo exactamente una vez. Un ciclo euleriano, la única diferencia es que el nodo inicial del camino es el mismo que el nodo donde el camino finaliza (aunque por ser un ciclo, no es del todo correcto hablar de inicio ya que podría empezar en cualquier nodo).

Es interesante ver cuáles son las características que tiene que tener un grafo para que exista un camino euleriano en él.


Si lo pensamos más inocentemente, el camino euleriano es el típico juego de "dibujar sin levanta el lápiz". El típico desafío de "a que no podés dibujar esto sin levantar el lápiz", se puede resolver mediante el uso de grafos. (FIXME: Link a grafos)


Hablaremos primero de caminos, y luego de haber comprendido eso, nos extenderemos a ciclos.

Supongamos que yo empiezo mi camino en un nodo, voy recorriendo aristas, y llego al final, pasando por todas las aristas exactamente una vez.
Si miramos los nodos "del medio", es decir que no son ni el primero ni el último, ese nodo fue recorrido primero a través de una arista para llegar a él (debemos excluir el inicial ya que nadie llegó a él al principio), y luego a través de una arista para salir de él (ya que como no es el último, el camino debió haber seguido).
Podemos pasar varias veces por estos nodos, pero siempre primero llegando a él, y luego yéndonos.

La conclusión que sacamos de esto, es que la cantidad de veces que "usamos sus aristas" es par.
Entonces, sí o sí, todos los nodos menos los extremos, deben ser extremos de una cantidad par de aristas. Como ya mencionamos en otros posts, este número se llama el grado de un nodo.

Entonces, todos los nodos menos dos, sí o sí deben tener nodo par.
Y los extremos del camino?
Primero veamos que si uno de los extremos tiene grado impar, el otro tambien (SUMA DE GRADOS = 2*ARISTAS)

Por lo tanto, o bien el grado de ambos es par, o bien es impar. Pero qué significa que el grado de los extremos sea par? Que para pasar por todas las aristas, por ejemplo si miramos el primer nodo, luego de "salir" de él, debemos volver. Entonces si pasa esto, existirá un ciclo euleriano! Y no un camino, para que exista un camino que no sea ciclo, debe haber exactamente dos nodos con grado impar, que serán nuestros extremos.

La condición de las pariedades de los nodos que vimos, ya vimos que son necesarias. Pero son suficientes?
DEMO
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
