Page 144 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Figura 6.6. Los puentes de Königsberg representados en un grafo

Euler determinó, en el contexto del problema, que los puntos intermedios de un recorrido posible
necesariamente han de estar conectados a un número par de líneas. En efecto, si se llega a un punto
desde alguna línea, entonces el único modo de salir de ese punto es por una línea diferente.

Esto significa que tanto el punto inicial como el final serían los únicos que podrían estar conectados
con un número impar de líneas. Sin embargo, el requisito adicional del problema dice que el punto
inicial debe ser igual al final, por lo que no podría existir ningún punto conectado con un número
impar de líneas.

En particular, como en la figura 6.6, los cuatro puntos poseen un número impar de líneas incidentes
(tres de ellos inciden en tres líneas y el restante incide en cinco), por lo que se concluye que es im-
posible definir un camino con las características buscadas que son los siete puentes de Königsberg.
Por eso, un circuito euleriano en un grafo G es un circuito que recorre cada arista una y solo una vez
(figura 6.7):

Figura 6.7. Circuito euleriano en un grafo G

En 1859 William Rowan Hamilton inventó un juego que consistía en encontrar un recorrido de todos
los vértices de un dodecaedro sin repetir vértices y volviendo al original (figura 6.8).

138