Resolución del problema

La resolución de Euler

En resumen

De las páginas 1 y 2 de la resolución podemos concluir que:
  1. Cuando una gráfica tiene sólo vértices pares (vértices con un número par de aristas), el recorrido es un ciclo euleriano, pues sin importar en qué vértice se inicie el recorrido, al hacerlo sin levantar el lápiz del papel y pasando sólo una vez por cada vértice, regresamos al vértice del que partimos.

  2. Cuando la gráfica tiene dos vértices impares (vértices con un número impar de aristas), el recorrido no es un ciclo euleriano, sino un camino euleriano, pues los puntos de partida y de terminación son distintos.

  3. Y finalmente, en una gráfica con dos vértices impares, no se puede obtener un camino euleriano si se parte de un vértice par.

A continuación se ofrece un espacio interactivo en el que se muestra la gráfica a partir de la que Euler resolvió el problema de los siete puentes de Königsberg. Traza diversos caminos y toma en cuenta las siguientes preguntas, te pueden guiar hacia la solución.

Preguntas
  1. Observa cuántas aristas tiene cada vértice de la gráfica. ¿Es posible salir y entrar a algún vértice sólo una vez?

  2. Observa que la gráfica es simétrica con respecto a una línea longitudinal. Supongamos que el camino se inicia en un lecho del río; puede ser el punto A o B, ya que la gráfica es simétrica. Este punto tiene tres puentes que lo unen a las dos islas. Si una persona recorre los tres puentes, ¿puede regresar al punto del que partió? Si no, ¿qué se necesita para que pueda regresar al punto de partida (A o B)?
Coloca el control gráfico en uno de los puntos de la gráfica y pulsa el botón "Iniciar". Para cambiar de punto de inicio pulsa el botón "Cambiar posición" y luego pulsa "Iniciar". Pulsa sobre el botón "Limpiar" para borrar los caminos que hayas trazado si así lo requieres.

Euler demostró que era imposible caminar por la ciudad de Königsberg cruzando cada puente sólo una vez. En la gráfica de Euler esto significaría que no es posible trazar un camino que pase sobre cada arista sólo una vez y pasando sobre todos los vértices. ¿Cómo dedujo esto? Veamos.

Antes de continuar, recuerda lo siguiente: cuando un vértice tiene un número impar de aristas, es un vértice impar. De manera análoga, para que un vértice sea par, debe tener un número par de aristas.

Tarea

A continuación se ofrece un espacio interactivo en el que se muestran vértices. El objetivo es que traces gráficas de 2, 3 o 4 vértices como se indica a continuación.
  • Traza un ciclo euleriano y un camino euleriano con dos vértices. ¿Hay más de una posibilidad para cada uno?
  • Traza ciclos eulerianos distintos con tres vértices. En todos los casos, ¿cómo son los vértices, pares o impares?
  • Traza caminos euleriano distintos con tres vértices, es decir que los puntos de inicio y de término sean distintos. ¿Cómo son los vértices, pares o impares?
  • Traza ciclos eulerianos distintos con cuatro vértices. En todos los casos, ¿cómo son los vértices, pares o impares?
  • Traza caminos eulerianos distintos con cuatro vértices, es decir que los puntos de inicio y de término sean distintos. ¿Hay vértices pares?, ¿hay vértices impares?, ¿cuántos?

  • Además en cada caso:
  • Intenta trazar un ciclo euleriano con un solo vértice impar. ¿Es posible?
  • Intenta trazar un ciclo euleriano con dos vértices impares. ¿Es posible?
  • Intenta trazar un camino euleriano con todos sus vértices pares. ¿Es posible?
  • Intenta trazar un camino euleriano con todos sus vértices impares. ¿Es posible?
Coloca el control gráfico en un vértice y pulsa el botón "Iniciar". Para cambiar el punto de inicio pulsa el botón "Cambiar posición" y luego pulsa "Iniciar". Pulsa sobre el botón "Limpiar" para borrar los caminos que hayas trazado si así lo requieres.

La resolución de Euler

Concretando, en la gráfica de Euler hay cuatro puntos y siete aristas. Puedes ver que tres aristas, es decir tres puentes, se unen al lecho del río A, y tres se unen al lecho del río B. Cinco puentes se unen a la isla C, y tres a la isla D. Esto quiere decir que todos los vértices tienen un número impar de aristas.

Ya vimos que para que la gráfica tenga un vértice impar se tendría que empezar o terminar el trayecto en ese vértice. Como sólo puede haber un inicio y un final del trayecto, sólo puede haber dos vértices impares si se quiere que sea posible trazar un camino sobre cada arista sólo una vez. Como el problema de los puentes tiene cuatro vértices impares, es simplemente imposible hacerlo.