Euler fue la primera persona que usó un grafo para resolver un problema. El problema al que me refiero, el que resolvió don Leonhard con un grafo, es un problema bien conocido en divulgación matemática: el problema de los puentes de Königsberg.
Viajamos al siglo XVIII.
En una ciudad prusiana llamada Könisberg -actualmente Kaliningrado- había 7 puentes.
La orografía de Könisberg era un tanto especial alrededor de los puentes, ya que la ciudad quedaba dividida en cuatro partes por el río Pregel.
Así 👇
En aquellos tiempos, alguien formuló la siguiente pregunta:
¿Es posible, comenzando en cualquier sitio de la ciudad de Könisberg, elegir un recorrido que nos permita pasar una única vez por cada uno de los siete puentes sobre el río Pregel?
Esta cuestión es conocida como el "Problema de los puentes de Könisberg".
Fíjense que en la pregunta anterior no se impone que el punto de inicio coincida con el punto final del recorrido.
Esa sería una pregunta diferente: ¿se puede diseñar un circuito, empezando y terminando en el mismo punto de la ciudad, que pase una, y solo una vez, por todos los puentes de Könisberg?
Las respuestas a estas dos preguntas se la debemos al protagonista de nuestro hilo: Leonhard Euler.
Para ello, en 1736, representó el problema con puntitos y rayas: un vértice (punto) por cada zona de la ciudad y una arista (rayita) entre dos de esas zonas por cada puente que las una.
La pregunta sobre Könisberg se transforma en la siguiente pregunta: ¿se puede dibujar ese grafo rojo sin levantar el lápiz del papel y sin repetir ninguna de las líneas? ¿Y empezando y terminando en el mismo vértice?
La respuesta a ambas preguntas es NO, según el teorema de Euler.
De hecho, en su honor, a los grafos que tienen la propiedad de poder ser recorridos (empezando y terminando en el mismo vértice) sin repetir aristas se les conoce como "grafos eulerianos".
Pues bien, un grafo es euleriano si -y solamente si- el número de aristas (rayitas) que salen de cada vértice es un número par.
Y un grafo tiene un camino euleriano (puede empezar en un vértice y terminar en otro) si -y solamente si- solo tiene 2 vértices de los que sale un número impar de aristas.
Por cierto, al número de rayitas que sale de un punto (vértice) se le llama valencia o grado del vértice.
Si miramos el grafo asociado a los puentes de Könisberg y las valencias de los vértices, vemos que de todas son impares.
Por lo tanto, NO es euleriano (no se puede diseñar un circuito -empezando y terminando en el mismo vértice- sin repetir aristas.
Tampoco sería posible diseñar un recorrido euleriano (con principio y final distintos) porque, como hemos dicho, solo se puede si el número de vértices de valencia impar es 2.
Oye, ¿y si solo hay 1 vértice de valencia impar en el grafo? Les dejo que lo piensen un rato…
Dibujen un grafo (puntos y rayas) con un solo vértice de valencia impar y comprueben si lo pueden recorrer completo sin pasar dos veces por la misma arista.
Ops, perdonen. ¿No les sale ningún grafo con un único vértice impar? Claro. Es IMPOSIBLE :)
La suma total de las valencias de un grafo es siempre un número par. Al sumar todas las valencias están contando las aristas (las rayitas) dos veces; les saldrá el número de aristas multiplicado por 2.
Esta propiedad se conoce como "el lema del apretón de manos" :)
Pero, como he dicho, a Euler le debemos un montón de resultados matemáticos más en un montón de áreas de las matemáticas y la física.
Le debemos también la maravillosa y voluptuosa identidad de Euler :_)
También, fue el primero en observar que el ortocentro, circuncentro y baricentro de un triángulo siempre están alineados.
Otra de sus aportaciones es la Teorema de Euler que nos permite obtener la relación entre los vértices, caras y aristas de un poliedro.
C - A + V = 2
Texto obtenido del twitter de la Mátematica y Divulgadora Clara Grima.
No hay comentarios:
Publicar un comentario