Los puentes de Königsberg: el comienzo de la teoría de grafos

Comenzamos esta semana con una entrada dedicada a un problema clásico pero no por ello falto de interés: los puentes de Konigsberg. Clásico porque es un problema muy conocido y estudiado; interesante porque está considerado como el comienzo de la topología, y, en particular, de la teoría de grafos.

El artículo consta de cuatro partes: descripción del problema y encuadre histórico del mismo, iniciación a la teoría de grafos, resolución del problema y aplicación a la resolución del problema del sobre y similares.

Los puentes de Königsberg

Königsberg (actualmente Kaliningrado, Rusia) era una ciudad de Prusia del siglo XVIII. El problema que nos ocupa tiene como protagonista a un río, el río Pregel, que cruzaba la ciudad, a dos islas que se encontraban en el mismo y a siete puentes que comunicaban las dos partes de la ciudad con las mismas. Concretamente la situación era como se describe en la imagen (A y B son las dos partes de la ciudad y C y D las dos islas):

Königsberg y sus puentes

(Imagen tomada de Historias de la Ciencia)

El problema consistía en comenzar en un punto, pasar por los siete puentes sin repetir ninguno y volver al punto de partida. Antes de seguir leyendo podéis intentarlo vosotros mismos, aunque os recomiendo que no le dediquéis demasiado tiempo.

Iniciación a la teoría de grafos

Un grafo es básicamente un conjunto no vacío (al menos contiene un elemento) de puntos llamados vértices y un conjunto de líneas llamadas aristas cada una de las cuales une dos vértices. Se llama lazo a una arista que une un vértice consigo mismo. Se dice que dos vértices son adyacentes si existe una arista que los une.

Se dice que un grafo es simple si para cualesquiera dos vértices existe a lo sumo una arista que los une. En otro caso se denomina multigrafo.

Si v es un vértice de un grafo, se denomina grado de v al número de aristas que inciden en el mismo (por convenio de considera que un lazo cuenta dos veces al determinar el grado de su vértice).

Se dice que un grafo es conexo si no puede expresarse como la unión de dos grafos de vértices disjuntos. Os dejo un ejemplo:

Grafo conexo y grafo no conexo

Un camino de longitud n es una sucesión de vértices, v_i, y aristas, a_j, de la siguiente forma: v_0,a_1,v_1, \ldots ,v_{n-1},a_n,v_n. Se dice que un camino es cerrado si v_n=v_0, es decir, el vértice inicial y el final son el mismo. Se dice que es simple si todas sus aristas son distintas. Se llama trayectoria a un camino simple en el que todos sus vértices (salvo probablemente el inicial y el final) son distintos y se denomina circuito a una trayectoria cerrada con al menos una arista.

Se llama camino euleriano a un camino simple que contiene todas las aristas del grafo y se denomina circuito euleriano a un camino euleriano cerrado. Se dice que un grafo es euleriano si contiene un circuito euleriano.

Resolución del problema

Para empezar, ¿quién resolvió el problema? Pues como ya sabéis los que conocíais el problema y como habréis intuido los que no lo conocíais fue Leonhard Euler quien dio solución a este asunto. La idea genial de Euler fue representar la ciudad de Königsberg como un grafo en el que las cuatro partes de la misma eran los vértices y los siete puentes eran las aristas:

Königsberg representada por un grafo

Por tanto el problema de los puentes de Königsberg pasa a ser un problema de teoría de grafos cuya solución publicó Euler en su artículo Solución de un problema relativo a la geometría de posición.

Según las definiciones que hemos visto en el punto anterior lo que queremos saber es si este grafo en euleriano, es decir, si contiene un circuito euleriano (es decir, un camino que contiene a todas las aristas del grafo sin que ninguna se repita y que comienza y termina en el mismo vértice). Vamos a demostrar el siguiente resultado:

Teorema:

Un grafo G es euleriano y sin vértices aislados \Leftrightarrow G es conexo y el grado de todos sus vértices es par.

Demostración:

  • \left ( \Rightarrow \right ) Si G es euleriano entonces contiene un circuito euleriano y como no tiene vértices aislados entonces cualquier par de vértice u y v están conectados por la parte del circuito que va de u a v. Por tanto G es conexo.

    Por otra parte, como G es euleriano contiene un circuito euleriano, es decir, un camino simple y cerrado que contiene a todas las aristas. Por tanto por cada arista que llegue a un vértice debe haber otra que salga del mismo y en consecuencia el grado de cada vértice es un número par.

  • \left ( \Leftarrow \right ) Partimos de que G es conexo y todos sus vértices tienen grado par.

    Si el número de aristas de G es 1 ó 2 el resultado es inmediato. Procedemos por inducción: supongamos que G tiene n aristas y que el resultado es cierto para los grafos que cumplan las condiciones y tengan menos de n aristas.

    Usando que todo grafo en el que todos sus vértices tienen grado mayor o igual que dos posee un circuito (¿por qué?) tenemos que el nuestro contiene un circuito, dikgamos C. Si C contiene todas las aristas de G, entonces C es un circuito euleriano y hemos terminado. En caso contrario sea G_1 el grafo obtenido al suprimir de G las aristas de C y suprimir después los vértices que han quedado aislados. Puede que el grafo haya quedado dividido en subgrafos no conectados entre sí; cada uno de ellos es una componente conexa de G_1.

    Por haber eliminado las aristas de un circuito todos los vértices de G_1 tiene grado par. Por la hipótesis de inducción, cada componente conexa G_{1i}de G_1 contiene un circuito euleriano.

    Como en cada componente conexa G_{1i} debe haber al menos un vértice v_i de C podemos obtener un circuito euleriano en G (que es lo que queríamos conseguir) del siguiente modo:

    Partimos de un vértice cualquiera de C (que recordemos que no era un circuito euleriano). Recorremos C hasta llegar a un vértice v_i de una componente conexa G_{1i} de G. Recorremos esta componente conexa a través del circuito euleriano que hemos visto que debe contener y continuamos recorriendo C hasta que nos encontremos con un vértice de otra de las componentes conexas, realizando entonces la misma operación. Repetimos el procedimiento hasta llegar al vértice de partida, obteniendo así un circuito euleriano.

c.q.d.

Observemos ahora el grafo que habíamos obtenido de la ciudad de Königsberg y calculemos el grado de todos sus vértices. Hay tres vértices con grado 3 y un vértice con grado 5. Es decir, no hay ninguno con grado par. Por tanto, según el teorema anterior, este grafo no contiene un circuito euleriano, esto es, no podemos comenzar en un punto de la ciudad y recorrer cada uno de los puentes sólo una vez y terminar en el punto de partida.

El problema del sobre y similares

Supongo que muchos de vosotros os habréis encontrado con el típico problema de recorrer todos los segmentos de un dibujo sólo una vez sin levantar el lápiz del papel. En esos problemas los vértices inicial y final no tiene que ser el mismo, es decir, puedo comenzar en el vértice que quiera y terminar en ese mismo o en cualquier otro, pero debo pasar por todas las líneas una y sólo una vez sin levantarme del papel. El más típico es el sobre:

Sobre cerrado

El siguiente resultado es un corolario del teorema anterior y nos ayudará a analizar todos estos problemas:

Corolario:

Un grafo G contiene un camino euleriano \Leftrightarrow G es conexo y tiene como máximo dos vértices de grado impar.

La demostración os la dejo a vosotros para que la penséis.

Un camino euleriano es precisamente lo que buscamos cuando queremos resolver estos problemas. Por tanto lo único que tenemos que hacer es calcular el grado de cada vértice. Si tenemos más de dos vértices de grado impar el recorrido no será posible; por el contrario, si tiene sólo dos vértices o ningún vértice con grado impar entonces sí se podrá recorrer de esa forma (no puede haber sólo un vértice con grado impar ya que el número de vértices de grado impar es par, ¿por qué?). En el caso de nuestro sobre tenemos cuatro vértices con grado impar y por tanto no podremos recorrer todas las aristas sólo una vez sin levantar el lápiz del papel.

Por contra, si tenemos el sobre abierto:

Sobre abierto

sí podremos recorrerlo así ya que ahora sólo hay dos vértices con grado impar, los dos de abajo. De hecho se sabe que para recorrer todas las aristas sólo una vez sin levantar el lápiz del papel debemos comenzar en uno de los vértices de grado impar y terminar en el otro.

Con estos resultados ya no habrá problema de este tipo que se os resista.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

10 Comentarios

  1. “El enfoque axiomático es a las matemáticas lo que el robo al trabajo honrado”

    Por Dios…

    Publica una respuesta
  2. Muy buena esta entrada, no habia echado horas dibujando para sacar el sobre abierto sin levantar el lapiz, y sabes que es peor: Cada vez que encuentro el problema tengo que volver a hacerlo ya que nunca me acuerdo como se hacia, o sea que llevo media vida dandole al sobre….

    Publica una respuesta
  3. Conozco a una persona que con 13 o 14 años fue capaz de hacer un razonamiento, casi calcado al de Euler, que le permitía saber de un golpe de vista si un problema de este tipo tenía solución o no.

    Publica una respuesta
  4. La demostración del corolario:

    Cojamos un grafo conexo y con dos vértices de grado impar, y creemos una arista artificial que los una. Ahora el grafo sera euleriano segun el teorema, y podemos encontrar un camino euleriano sobre el mismo.

    Desde uno de los vertices de grado impar, seguimos el camino euleriano encontrado. Si luego retiramos la arista artificial, el camino empezará y acabara en los vertices de grado impar y sera euleriano.

    El otro caso posible es que no tenga ningun vertice de grado impar, pero entonces es un caso que cumple el teorema y es trivial.

    (un grafo no puede tener un numero impar vertices de grado impar, ya que la suma de los grados sera el doble del numero de aristas. Si esa suma fuera impar, el numero de aristas no seria entero, lo que es absurdo)
    (Lo siento, aun tengo que aprender a usar el latex)

    No se si ha quedado claro o he sido muy caótico… en cualquier caso, espero que se entienda.

    Publica una respuesta
  5. Vaya, esto parece mi relación de problemas de Fundamentos Matemáticos I…que recuerdos…resolví todos estos problemas…¿para cuando algo del teoremas sobre colores y mapas?
    Un saludo

    Publica una respuesta
  6. Enhorabuena Yrekthelas, perfectas demostraciones :).

    LordHASH paciencia, que se acercan los exámenes y tengo mucho trabajo en la academia. Está en proyecto…y hasta con sorpresas :).

    Sive: ¿sabes algo de ese razonamiento?

    Publica una respuesta
  7. El problema inicialmente no planteaba lo de “volver al punto de partida”, sólo lo de cruzar los siete puentes. Con esta restricción la solución era inmediata, ya que al tener la isla C cinco puentes y A, B y D tres cada una no puedes en ningún caso terminar donde empezaste.

    Es interesante ver que el problema de cruzar los siete puentes una vez cada uno sí tiene solución: por ejemplo, sales de C y haces C-A-C-B-C-D-A, subes hasta el nacimiento del río, bajas por B y cruzas a D:

    C-A-C-B-C-D-A=B-D

    Sólo hay que fijarse en que puedes pasar de A a B sin cruzar ningún puente. Por suerte Euler no se dio cuenta o nos habríamos quedado sin la Topología…

    Publica una respuesta
  8. Diamond, sé que el razonamiento fue parecido al de Euler porque las conclusiones eran las mismas, y por lo poco que recuerdo vagamente (yo también tenía 14 o 15 años). Pero bueno, supongo que coincidireis conmigo en que Euler no descubrió América con esto, el problema de los puentes es bastante sencillo. En este caso lo que sorprende es la edad del protagonista.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Euler y la larga sombra de la investigación | Politikon - [...] resolver algo más parecido a un acertijo que a un problema matemático: ¿se podía dar un paseo por la…
  2. Nicolaas de Bruijn, del "BEST theorem" al confirmador de teorías matemáticas - Gaussianos | Gaussianos - [...] otros avances realizados por de Bruijn, veamos de qué trata el BEST theorem. ¿Os acordáis del problema de los…
  3. El teorema de Turan: el comienzo de la teoría de grafos extrema - Gaussianos | Gaussianos - […] se considera el estudio y resolución del problema de los puentes de Königsberg por parte de Leonhard Euler como…
  4. 7 puentes para un sólo paseo | Matemáticas | Mati y sus matiaventuras - […] Si queréis profundizar más en este problema os recomiendo esta entrada en Gaussianos. […]
  5. I.E.S. Juan de Herrera (San Lorenzo de el Escorial) – PeDRoMaTe´s BloG - […] de Fermat, un libro de Alberto Durero, un triángulo de Reuleaux, un Tangram, una maqueta de los puentes de Königsberg,… tranquilos,…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *