Siete puentes, hoy desaparecidos, unían entre sí las partes divididas por el río. Seguramente el filósofo, en sus paseos diarios, atravesaba algunos de ellos. ¿Pudo Kant dar un paseo en que atravesara todos los puentes una sola vez?
Será más fácil abordar el problema si prescindimos de la distribución real de los puentes sobre el territorio de la ciudad. Cuando las distancias y direcciones reales no importan, las relaciones se entienden tanto mejor cuanto más sencillo es el esquema.
Cualquiera de los esquemas que siguen refleja las conexiones que establecían los puentes de Koenisberg y es válido para trabajar sobre él.
Reflexionando sobre los ejemplos de figuras de un solo trazo que vimos aquí, se observa que en el sobre sencillo no coinciden el punto de partida (1) y el de llegada (9), que sí lo hacen (1 y 25) en el sobre de Lewis Carroll.
La imposibilidad de regreso al origen en el primer caso es fácil de comprender, si analizamos el número de lados que concurren en cada vértice. Salvo para el inicial y el final, cada vez que se entra en uno hay que salir para proseguir la marcha, y como no se puede volver a pasar por el mismo, cada paso por un vértice elimina dos trayectos. El vértice de partida y el de llegada deben tener un número impar de aristas concurrentes; los demás deben tener un número par. De los cinco vértices del sobre mágico uno tiene dos aristas, otros dos cuatro y los dos restantes, de tres aristas, deben ser necesariamente los terminales.
Diferente es el caso del sobre mágico. Aquí, en doce vértices concurren dos lados, y en seis, cuatro. Todas las entradas encuentran así salida, y la inicial debe ser también final, completando un ciclo. Si el punto de partida no lo fuera también de llegada, en ambos quedaría algún lado sin recorrer. O habría que pasar dos veces por algún tramo, contra la hipótesis considerada.
Se comprende entonces la imposibilidad del paseo propuesto para los puentes de Koenisberg. Hay tres vértices con tres puentes y uno con cinco; en todos es impar el número de lados. Antes de completar el recorrido llegaremos a un punto por el que ya hemos pasado un número par de veces, entrando y saliendo, y no podremos salir de allí sin repetir puente.
Conclusión: el recorrido es imposible si todos los vértices tienen un número impar de lados.
El problema, sin embargo, se puede resolver en todos los casos si admitimos cruzar los puentes dos veces, pero en sentido contrario. Este doble paseo siempre es posible. Todo grafo conexo (se excluye así la posibilidad de considerar que es un grafo lo que serían varios independientes) admite el doble paseo, aunque hemos de ser muy cuidadosos si queremos evitar entrar prematuramente en un bucle que nos impida salir sin repetir tramo y sentido.
Lo que hacemos así equivale a duplicar las rutas: incluso la llegada a un callejón sin salida nos permite regresar por donde vinimos.
He aquí una solución con este doble recorrido de los puentes. Los vértices se recorrerán en orden numérico. Los puentes, en orden alfabético:
El caso del dodecaedro maldito es diferente, porque podemos, y debemos, dejar aristas sin recorrer. Aquí lo importante es evitar un bucle prematuro, como el que se ocasionaría, por ejemplo, rodeando menos de seis caras en línea, o con un ciclo que aloje en su interior uno o más vértices a los que ya no podrá llegarse.
No hay comentarios:
Publicar un comentario