Teoría de grafos

La isla Kueiphof en Koenigsberg (Pomerania) el río que la rodea se divide en dos brazos.

 

Sobre los brazos estaban construidos siete puentes y para los habitantes era motivo de distracción descubrir un itinerario de manera que pudieran regresar al punto de partida, después de haber cruzado por los siete puentes pero pasando sólo una vez por cada uno de ellos.

 

Euler estudió el asunto, representó las distintas zonas A, B, C y D por medio de puntos, mientras que los puentes estaban representados por líneas que unían estos puntos. A la figura la llamó grafo, a los puntos los llamó vértices y a las líneas las denominó aristas.

Estudió si una figura lineal (grafo, los anteriores dibujos son ejemplos de grafos) se podía dibujar con un solo trazo, sin levantar el lápiz del papel y sin pasar dos veces por el mismo sitio.

Llegó a la siguiente conclusión:

1. Es imposible si hay más de dos vértices impares.

2. Es posible cuando:

a) Todos los vértices son pares y el punto de partida puede ser cualquiera.

b) Cuando no hay más de dos vértices impares y en este caso el comienzo del recorrido comienza en uno de ellos y termina en el otro.

 

(Impar es un vértice si de él parten un número impar de caminos).

 

A la isla A llegan 5 puentes; a la B llegan 3 puentes; a la orilla C llegan 3 puentes y a la orilla D llegan 3 puentes, por tanto, según las conclusiones anteriores, el problema no tiene solución.