El camino de Euler. Teoría de Grafos y los Puentes de Könisberg

Aquí presento un nuevo reto, en la imagen anterior aparece un retángulo subdividio en cinco partes. Para solucionar el problema deberás unir todas las líneas rectas de una sola vez (sin levantar el lapiz del papel) y sin pasar por una misma recta dos veces. Por ejemplo, esta imagen de aquí sería un ejemplo fallido del problema:

euler-trail-3

Como se puede observar, esta respuesta sería incorrecta ya que ha pasado dos veces por el mismo segmento de linea recta.

Para obtener la respuesta a este problema no es necesario estresarse mucho, no existe solución. Sencillamente es imposible. Aquí es donde entra nuestro el famoso matemática Euler. Todo comenzó a principios del siglo XVIII cuando un matemático local de Könisberg, Carl Gottlieb Ehler propuso a Euler través de una carta el problema de los siete puentes. En ella explicaba que su pueblo estaba dividido por un río, y que en su interior se encontraban dos islas. Además todas estaban interconectadas por un total de siete puentes. El problema radicaba en que Ehler no conseguía demostrar de forma empírica, si era posible atravesar los siete puentes sin pasar dos veces por el mismo. En primera instancia, Euler no le hizo mucho casó ya que pensaba que no formaba parte de las matemáticas, sin embargo, tras echarle un vistazo consiguió resolverlo creando un nuevo campo en las matemáticas, la Teoría de Grafos.

Para solucionar el problema, comenzó por simplifacarlo, haciéndose un esquema de la situación:

euler-trail-4

En este esquema podía ver con claridad los cuatro puntos por los que se podía pasar y los siete puentes por los que tan solo podría pasar una vez. Con este esquema llegó a las siguientes conclusiones:

  1. De acuerdo con las reglas del problema, a cada trozo de tierra que entrase, debería entrar por un puente y salir por otro, lo que significa, que cada nodo (o trozo de tierra) debería tener un número par de puentes anexionados.
  2. La única excepción que se produciría a la afirmación anterior sería que el nodo escogido fuera el principio o final de la ruta, ya que solo sería necesario que saliera un solo puente de dicho nodo y tendría en consecuencia un número impar de puentes saliendo.
  3. Solo podrían existir dos nodos con un número impar de puentes ya que solo existen un principio y un final de la ruta.
  4. Además, se dio cuenta, que en caso de que la ruta no contará con dos nodos con un número impar de puentes, la única solución para que la ruta (o camino de Euler) pudiera cumplir los requisitos sería que todos los nodos tuvieran un número par de puentes anexionados.

En consecuencia, respondiendo al problema de Ehler, demostró que no existía solución debido a que todos los nodos tenían un número impar de puentes anexionados.

Haciendo referencia al problema del inicio, el esquema que podríamos realizar sería el siguiente:

euler-trail-2Como podemos observar, existen una gran cantidad de nodos (cada intersección entre segmentos), sin embargo, tan solo tenemos que fijarnos en las intersecciones centrales para descubrir la respuesta. Como la imagen muestra, los tres nodos centrales que forman un triángulo, tiene 5 caminos que salen de cada uno de ellos, lo que significa que existen tres nodos  con un número impar de caminos. Este hecho incumple las conclusiones de Euler, y ya que nuestro problema sigue las misma premisas que el suyo, podemos concluir que no existe ninguna solución posible y por tanto no es un camino de Euler.

Aquí dejo un video donde se explica a la perfección:

Anuncios

1 Comment

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s