Nuevamente Gaussianos vuelve a dar en el blanco. Un artículo fácil de digerir, pero no por ello carente de rigor matemático: introducción a la teoría de los grafos. El artículo parte del famoso problema d elos puentes de Konigsberg. Disfrútenlo:
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 (
(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 
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:
Un camino de longitud n es una sucesión de vértices, 
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:
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
es euleriano y sin vértices aislados
Demostración:
Por otra parte, como
Si el número de aristas de 
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 
Por haber eliminado las aristas de un circuito todos los vértices de 
Como en cada componente conexa
Partimos de un vértice cualquiera de
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 
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:
El siguiente resultado es un corolario del teorema anterior y nos ayudará a analizar todos estos problemas:
Corolario:
Un grafo
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:
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.
Fuente:
