Caminos y circuitos eulerianos – los siete puentes de Königsberg

Qué muestra

En 1736 Leonhard Euler se preguntó si un paseo por Königsberg podía cruzar cada uno de sus siete puentes exactamente una vez. Al convertir las zonas de tierra en vértices y los puentes en aristas, demostró que la respuesta depende solo de los grados. Un grafo conexo tiene un circuito euleriano cuando todos los vértices tienen grado par, y un camino euleriano cuando exactamente dos vértices tienen grado impar; el camino empieza en un vértice impar y termina en el otro. La simulación admite varias aristas entre los mismos dos vértices, pero no lazos, y el mapa de Königsberg está simplificado.

Cómo usarla

Empieza con Siete puentes de Königsberg y lee los grados y la conclusión. Cambia el Modo a Recorrer a mano y toca aristas para intentar cruzar cada puente una vez. En el modo Dibujar / mover añade o une vértices hasta que cambie la conclusión; luego elige Fleury (evitar puentes) o Hierholzer (empalmar circuitos) y pulsa Paso o Ejecutar para ver cómo se construye el recorrido.

Parámetros que puedes cambiar

• Grafo inicial Siete puentes de Königsberg, Sobre (dibujar sin levantar el lápiz), Dos triángulos con un vértice común, Grafo completo de 5 vértices (K5), Página en blanco – dibuja el tuyo
• Algoritmo Fleury (evitar puentes), Hierholzer (empalmar circuitos)
• Velocidad de animación 0,5–4 aristas/s

Preguntas para explorar

1. ¿Por qué es imposible cruzar cada uno de los siete puentes de Königsberg exactamente una vez?
2. ¿Cuántos puentes como mínimo debes añadir para obtener un camino euleriano, y dónde?
3. ¿Por qué un camino euleriano debe empezar en un vértice impar y terminar en el otro?