CAPÍTULO 3. RELACIONES
90
3.5.1.
El problema de los puentes de Königsberg
El estudio de los grafos lo inició el matemático Leonhard Euler en 1736 resolviendo un
viejo problema conocido como el problema de los Puentes de Königsberg. El problema era
el siguiente: Dos islas que se hallan en el río Pregel en Königsberg (en la antigua Unión
Soviética) están conectadas entre sí y con las márgenes del río por puentes como lo indica la
figura.
D
A
C
B
El problema consiste en partir de cualquier lugar (A, B, C o D); seguir caminando y
pasar por cada uno de los puentes exactamente una vez, y luego regresar al punto de partida.
Tal ruta se llama un circuito de Euler.
Euler representó este problema con un grafo donde los vértices corresponden a los lugares
y los lados (arcos ó aristas) corresponden a los puentes.
D
A
C
B
Euler demostró que no existe una solución para el problema de los puentes. De hecho
mostró un resultado general sobre grafos que resuelve problemas similares al de los puentes
de Königsberg. El método ideado por Euler para resolver este problema usa el concepto de
la valencia o grado de un vértice. Se define la valencia de un vértice como el número de
arcos que “tocan” al vértice. Por ejemplo, en el caso del problema de los puentes tenemos que
las valencias de los vértices son: A tiene valencia 5, B, C y D tienen cada uno valencia 3. El
teorema de Euler dice que para que exista un circuito de Euler es necesario que la valencia