TEORÍA DE GRAFOS

PLANTEAMIENTO:

El problema que Will Hunting resuelve al principio de la película se enmarca dentro de la teoría de grafos. Esta rama de la matemática discreta se ocupa de problemas que tienen que ver únicamente con puntos y sus conexiones y surgió del estudio de problemas concretos.

A continuación trataremos de describir el problema que la mayoría de los autores señalan como el origen histórico de la teoría de grafos:

El problema de los siete puentes de Königsberg (Prusia oriental en el siglo XVIII -ciudad natal de Kant- y actualmente, Kaliningrado, provincia rusa) es un célebre problema matemático que fue resuelto por Leonhard Euler en 1736 y dio origen a la Teoría de los grafos.

 

 

Tiene como protagonista a un río, el Pregel, que cruzaba la ciudad de Königsberg , 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.

¿Es posible dar un paseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada puente una sola vez y volviendo al punto de partida?

 

Algunos de los habitantes de Königsberg opinaban que sí y otros que no.

 

 

Antes de seguir leyendo podéis intentarlo vosotros mismos,

 aunque se recomienda no dedicarle demasiado tiempo...

 

Euler (1707-1783) enfocó el problema representando cada parte de tierra por un punto y cada puente, por una línea, uniendo los puntos que se corresponden. Entonces, el problema anterior se puede trasladar a la siguiente pregunta:

 

 ¿se puede recorrer el dibujo terminando

en el punto de partida sin repetir las líneas?

 

 

INICIACIÓN A LA TEORÍA DE GRAFOS:

 

¿Qué es un grafo?

Es un conjunto no vacío formado por Nodos o vértices conectados por un  conjunto de líneas mediante arcos o aristas. En ocasiones, se indican sobre los arcos (o sobre los nodos) unos valores, con interpretación muy variada según los casos (distancias, tiempos, costes, beneficios, etc.). 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.

Un grafo se dice conexo si todo par de nodos está unido por un camino.

Un camino de longitud "n" es una sucesión de vértices y aristas. Se dice que un camino es cerrado si 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.

 

RESOLUCIÓN DEL PROBLEMA:

Leonhard Euler fue 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.

Observa el grafo resultante. En él está contenida toda la información necesaria: para pasar de las zonas C a la A y de la C a la B hay dos puentes, y para hacerlo de D al resto, sólo hay un puente.

 

 

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".

Para conocer la solución vamos a ver el concepto de  CAMINO EULERIANO.

Son aquellos caminos que, partiendo de un nodo, regresan a ese nodo recorriendo una, y sólo una, vez cada uno de los arcos del grafo.

Hierholzer prueba (1873) que los caminos eulerianos se pueden construir en aquellos grafos conexos a cuyos nodos llegan un número par de arcos.

Según lo dicho, ¿Alguno de estos 2 son caminos eulerianos?

 

 

 

Como vemos, en el primero, hay nodos a los que le llegan un número impar de nodos.

Concretamente al señalado en rojo le llegan 3.

 

 

 

CONCLUSIÓN DEL PROBLEMA:

En resumen:

1.- Si todos los vértices de un grafo son de orden par (es decir, llegan a él un número par de lados), éste se puede recorrer de una sola pasada y volver al punto de partida. Es un grafo euleriano.

2.- Si dos de los vértices son de orden impar y el resto de orden par, se puede recorrer el grafo de una sola pasada pero no se puede acabar en el punto de partida. En este caso el grafo se llama semieuleriano.

3.- Si el grafo tiene más de dos vértices con un número impar de lados concurrentes, el problema planteado no tiene solución.

 

 

 

ACTIVIDADES OPCIONALES. NO OBLIGATORIAS

ACTIVIDAD 1

En la actualidad en Kaliningrado se han construido dos puentes más que permiten recorrer todos los puentes una sola vez y acabar en el punto de partida. ¿Puedes indicar dónde se han construido y dar un posible camino euleriano que los recorra?

ACTIVIDAD 2

Si no hiciera falta volver al punto de partida al final del recorrido, ¿bastaría con un único puente más? ¿Dónde se situaría? ¿Cuál sería un posible recorrido?

ACTIVIDAD 3

Si en lugar de construir, se derribase uno, dejándolos en seis, ¿sería posible la cuestión que le plantearon a Euler? ¿Cómo?

ACTIVIDAD 4

¿Sabrías realizar la figura siguiente sin levantar el lápiz del papel y sin pasar dos veces por el mismo sitio?

Vemos que en esta actividad se trata de un camino semieuleriano, es decir, no tiene que empezar y acabar por el mismo sitio.

Como hemos visto, estos ejercicios SÍ tienen solución.

 

 

ACTIVIDAD 5

Trata de unir los 9 puntos de la imagen con solo 4 líneas rectas y sin levantar el lápiz del papel, es decir, donde acaba una tiene que empezar la otra. No puedes pasar 2 veces por el mismo punto pero las líneas pueden cruzarse.

 

EL INTERNADO (SERIE - A3TV, 2007)

 

Como veis, estas actividades son clásicas en los pasatiempos de dibujar una figura de un solo trazo, sin repeticiones y sin levantar el lápiz del papel.

Pero los grafos no sólo aparecen en el análisis de juegos y pasatiempos. La teoría de grafos es una de las actuales líneas de investigación matemática más importante. No en vano se aplican en múltiples campos: estudio de circuitos eléctricos (reglas de Kirchkoff), diseño de redes en informática, trazado de itinerarios en empresas de servicio urgente, regulación del tráfico de una ciudad, trazado de carreteras en ingeniería, estudio de enlaces químicos y cristalográficos, en zoología, antropología, etc.

 

Entramos en el mundo ANIMADO de los grafos