Grafo euleriano

Grafo euleriano. Dícese de los grafos no orientados formados por un ciclo euleriano; es decir, aquellos que pueden recorrerse completamente desde un vértice y regresar al punto de origen sin pasar dos veces por la misma arista.

El nombre de este tipo de grafos proviene del matemático Leonard Euler quien abordó por primera vez el asunto de cómo debían caracterizarse los grafos para poder recorrerse de la manera deseada tras desestimar el problema de los puentes de Königsberg.

El problema análogo de recorrido pero que en lugar de limitar el doble paso por las aristas lo hace impidiendo que se transite dos veces por los vértices ha dado lugar a la existencia de los grafos hamiltonianos.

Casos particulares

• Un grafo G=<V,A> no dirigido y conexo que tiene exactamente 2 vértices de grado impar, entonces tiene un camino euleriano no cerrado.
• Un grafo G=<V,A> no dirigido y conexo cuyos vértices tienen grado par, entonces tiene un ciclo euleriano.

Teorema general

• Sea un grafo G=<V,A> no dirigido y conexo, entonces las expresiones siguientes equivalen:

1. G es grafo euleriano.
2. Todos sus vertices tienen grado par no nulo.

Propiedades

• Un grafo conexo y no dirigido se dice que es euleriano si cada vértice tiene un grado par.
• Un grafo no dirigido es euleriano si es conexo y si se puede descomponer en uno con los vértices disjuntos.
• Si un grafo no dirigido G es euleriano entonces su gráfo-línea L(G) se dice que es también euleriano.
• Un grafo dirigido es euleriano si es conexo y cada vértice tiene grados internos iguales a los externos.
• Un grafo no dirigido se dice que es susceptible de ser recorrido (en inglés: traversable) si es conexo y al menos dos vértices en el grafo tienen grado impar.

Grafo compuesto por un ciclo euleriano