Grafos Eulerianos y Hamiltonianos

Existen todavía algunas familias de grafos que se derivan del concepto de grafos conexos. Este es el caso de los grafos eulerianos y los grafos hamiltonianos. Estas familias de grafos nos permiten resolver el famoso problema de los puentes de Königsberg:

¿cuándo es posible hacer un recorrido de una figura (en este caso de un grafo múltiple) sin pasar dos veces por la misma línea o por el mismo vértice?

En la fig. 3.10 tenemos dos grafos G1 y G2; es posible recorrer uno de ellos sin repetir ninguna línea, pero el otro no. ¿Cuál es cuál? Es evidente que el grafo G1 no puede ser recorrido sin repetir alguna de sus líneas, mientras que el grafo G2 sí.

Fig 3.10

I. GRAFOS EULERIANOS

Recorrido cerrado

Cubre todas las líneas de un grafo, comenzando y terminando en un mismo vértice, recorriendo sin repetición y en forma continua todas las líneas de un grafo G cualquiera. Cuando tal recorrido existe, se denomina euleriano y un grafo que se puede trazar mediante un recorrido euleriano se llama grafo euleriano. En la fig. 3.11, G1 es obviamente un grafo euleriano; G2 no lo es, a pesar de que se puede trazar continuamente, ya que el recorrido comienza y termina en vértices distintos; finalmente, G3 no es un grafo euleriano, porque no se puede trazar continuamente.

Fig. 3.11

Teorema 3.2

Diremos que un grafo G es la unión disjunta de ciclos, si podemos descomponer a G como la unión de ciclos que no tienen líneas en común, aunque se permite que tengan, al menos, un vértice en común.

Fig. 3.12

En la fig. 3.12, el grafo se puede descomponer como la unión disjunta de los ciclos C = v1v2v3v4v5v6v1; C' = v1v7v5v1; C'' = v2v7v4v2; C''' = v3v8v9v3 y el recorrido euleriano para el grafo G viene dado por la secuencia de sus líneas 1, 2,..., 15.

Observacion 3.1.5: Esta descomposición por lo general no es única. El grafo de la fig. 3.11 admite otra descomposición como unión disjunta de ciclos, por ejemplo, C = v1v2v7v1; C' = v3v4v2v3; C'' = v3v8v9v3; C''' = v7v4v5v7; C'''' = v5v1v6v5 .

Teorema 3.2

Un grafo G conexo es euleriano si y sólo si es la unión disjunta de ciclos.

Demostración:
Si G es euleriano, G admite un recorrido euleriano T. Como T es cerrado, T contiene un ciclo C. Sea T' el recorrido obtenido al eliminar en T las líneas de C. T' sigue siendo un recorrido cerrado, por lo tanto, contiene un ciclo C'. Repitiendo este proceso, obtenemos una descomposición de G como la unión disjunta de los ciclos C, C'..., etc.

Recíprocamente, supongamos que G es una unión disjunta de ciclos. Sea C un ciclo cualquiera en G. Si

entonces G es un ciclo y por lo tanto euleriano. Si

existe un ciclo C' en G que tiene un vértice v en común con C (por hipótesis). Si G es la unión de C y C', entonces, comenzando en v trazamos C y luego C', obteniendo así un recorrido euleriano de G. Si la unión de C y C' no es todo G, existe un ciclo C'' que tiene algún vértice v' en común con C o con C', digamos por ejemplo con C'. Si G es la unión de C, C' y C'', entonces comenzando en v trazamos C, luego trazamos C' hasta llegar a v' y luego trazamos C'' hasta completar C', luego regresamos a v como ilustra el diagrama de la fig. 3.13.

Fig. 3.13

Así, obtenemos un recorrido euleriano de G. Si la unión de C, C' y C'' no es todo G, continuamos con este procedimiento hasta obtener un recorrido euleriano de G.

Colonario 2: Un grafo conexo es euleriano si y sólo si todos sus vértices tienen valencia par. (Este teorema rige también para multigrafos).

Demostración:
En un recorrido euleriano, cuando visitamos un vértice, necesitamos al menos dos líneas distintas adyacentes al vértice (una para llegar al vértice y otra para salir de él), incluyendo al vértice inicial, porque tenemos que regresar a él para concluir el recorrido. Esto significa, que cada vértice contribuye con un número par de líneas y, por lo tanto, su valencia es par.

II. GRAFOS HAMILTONIANOS

¿Cuándo es posible hacer un recorrido en un grafo que pase por cada vértice exactamente una vez y termine en el vértice original?
O en otras palabras, ¿cuándo un grafo tiene un ciclo cerrado que contenga a todos sus vértices?

Cuando existe tal ciclo, lo llamaremos ciclo hamiltoniano y un grafo que posea un ciclo hamiltoniano se llama grafo hamiltoniano.

Un ciclo puro Cp es evidentemente hamiltoniano; el grafo de la fig. 3.14 también. En efecto, el ciclo v1v2... v7v1 representa un ciclo hamiltoniano del grafo G.

Fig. 3.14

La Fig. 3.15 muestra que no hay ninguna relación directa entre grafos eulerianos y hamiltonianos.

Fig. 3.15

Contrario al caso de los grafos eulerianos, para el caso de los grafos hamiltonianos no se conoce ninguna condición necesaria y suficiente que los caracterice. Esto es lamentable porque en muchas aplicaciones es fundamental poder determinar si un grafo es hamiltoniano.

¿Qué tan fuertemente conexo es un grafo?

Una posible interpretación de esta pregunta es analizar cuántas líneas o vértices deberíamos eliminar del grafo para convertirlo en no conexo. Introducimos a continuación algunas definiciones que aclaran este punto.