Adicción Matemática Blog

Un grafo es un conjunto de puntos en el plano o en el espacio, llamados vértices, conectados por un conjunto de líneas, llamadas aristas. 

Se llama grado de un vértice al número de aristas que tienen por extremo dicho vértice. En el grafo anterior el vértice F tienen grado 4, el vértice B tiene grado3, los vértices C, D, E y G tienen grado 2 y el vértice A tiene grado 1.

Un grafo en el que todos los vértices tienen el mismo grado, se llama regular.

Si en un grafo existen varias aristas entre los mismos vértices, se llama multigrafo. Si existe al menos una arista, llamada lazo, cuyos extremos coinciden, el grafo se llama pseudografo.

Königsberg era una ciudad de Prusia Oriental. Actualmente es la ciudad rusa de Kaliningrado. Está atravesada por el río Pregolya, que se bifurca en dos brazos dejando la isla de Kneiphof entre ellos.

En el siglo XVIII había siete puentes, aproximadamente como se puede observar en la figura. En esa época se planteó la situación de si era posible recorrer la ciudad a pie, pasando una sola vez por cada uno de los puentes y volviendo al punto inicial. Esta situación se extendió como juego y, posteriormente, como problema matemático.

El matemático suizo Leonhard Euler (1707-1783) resolvió el problema en 1736, dando origen con la solución a la Teoría de Grafos.

Si se representan con los puntos azules las regiones de tierra firme separadas por el río, cada puente une dos puntos azules, existiendo siete caminos posibles que unen cuatro puntos, representados en color naranja en la imagen derecha.

Hacer el recorrido propuesto, equivale a construir la siguiente figura sin levantar el lápiz del papel y sin pasar dos veces por la misma línea. 

Euler resolvió el problema de los puentes de Königsberg demostrando que no es posible realizar dicho recorrido.