viernes, 17 de marzo de 2017

Teoría de grafos en el parque

Los parques zaragozanos lucen en la última señalización un logotipo que los matemáticos llaman grafo: Conjunto de puntos donde algunos de ellos están conectados por caminos (segmentos). Su observación me suscita un viejo problema topológico: ¿Es posible dar un paseo que recorra todos los caminos una sola vez?
Os propongo la pregunta...

4 comentarios:

  1. Todos tienen un número par de conexiones menos uno (el que está a media altura más a la derecha). Si empezamos en ése no es difícil hacer el recorrido.

    ResponderEliminar
  2. Gracias por tu rápida respuesta. Se razona en esa línea que dices, pero tu conclusión no es correcta... piensa quer si se empieza en un nodo impar no se puede terminar en un nodo par.
    Explicación para que no se pierdan quienes se acercan por vez primera a estas cuestiones: Un nodo (punto) que sea de inicio del paseo pero no de final tendrá 1 conexión (camino de salida); o 3 (salida, llegada y nueva salida); o 5; etc... siempre un número impar. Ocurre lo mismo con un nodo que no sea el inicio pero sí sea el final del paseo: tendrá 1 conexión (solo llegada); o 3 (llegada, salida y llegada); o 5; etc... también impar.
    Cuenta de nuevo los caminos, que hay dos nodos impares.
    Para completar el razonamiento aún hay que responder a estas cuestiones pendientes: ¿Y cuántos caminos tendrán los nodos que no sean ni de inicio ni de final del paseo? ¿Y qué ocurre si es un paseo en el que el punto de inicio coincida con el de final?

    ResponderEliminar
  3. Bueno, terminemos el razonamiento.
    Como dije, un nodo que sea solo de inicio o solo de final debe tener un número par de conexiones o caminos.
    Si un nodo es de paso (no es de inicio ni de final), tiene un número par de conexiones: se llega a él y se sale de él (2); o se llega, se sale, se regresa y se vuelve a salir (4); etc. Siempre un número par.
    Si un nodo es al mismo tiempo de inicio y de final, también tiene un número par de conexiones. El razonamiento es como el del caso anterior.
    Así que: O bien el paseo empieza en un nodo y termina en otro, en cuyo caso tendrá dos nodos impares y el resto pares; o bien el paseo empieza y termina en el mismo nodo, en cuyo caso todos los nodos son pares.
    Sabiendo lo anterior, ya solo hay que contar las conexiones que tienen los nodos del logotipo del parque, que son: 2, 5, 2, 4, 2, 4 y 3. Como hay dos nodos impares (5 y 3), el paseo propuesto es posible, empezando en uno de ellos y terminando en el otro.

    ResponderEliminar
  4. Este problema ha sido una adaptación de otro problema famoso, conocido como "Los puentes de Königsberg", que resolvió a comienzos del siglo XVIII el matemático suizo Leonhard Euler y que fue el origen de una rama de las matemáticas llamada topología. Tiene aplicación para carteros y repartidores, para la logística en general.

    ResponderEliminar