Dan, has planteado un problema concreto, cuya solución concreta es que no tiene solución.
Ahora pides una demostración de la solución: demostrar por qué no tiene solución.
Las demostraciones en matemáticas están basadas en la evidencia. Total, que al final estamos en las mismas. Lo que es evidente para unos, no lo es para otros. Por ejemplo, los algoritmos que he propuesto, para mí son evidentes por inducción, que es un procedimiento de prueba bastante aceptado. Pero en fin..., reconozco que hay métodos de prueba mejores.
Creo que no existe en la ciencia matemática un teorema para hallar caminos hamiltonianos, similar al que expuso Euler para las aristas y los llamados desde entonces caminos eulerianos.
Es un asunto muy curioso porque, en principio, el problema sería de una dificultad semejante y la aplicación mucho más interesante, a fin de cuentas, los caminos eulerianos servirían para optimizar el trabajo de una agencia de transportes, pero los hamiltonianos servirían para crear carreteras perfectas para resolver todos los problemas de todas las agencias de transportes y del resto de usuarios en general.
Creo que hasta hay dificultades para hallar algoritmos que sirvan para solucionar los problemas hamiltonianos, es decir, no ya un teorema general, sino una simple aplicación práctica para casos especiales, por ejemplo los de programación. Los algoritmos hallados son de una lentitud pasmosa.
Pero volviendo al problema. La demostración que pides debería entenderse como una demostración al problema concreto (Como parece que se está haciendo con los problemas hamiltonianos).
Se me ocurre que con una analítica combinatoria es fácil obtener todos los resultados, pues aunque las combinaciones son muchas incluso con un número de puntos tan pequeño, habría que considerar las simetrías que se producen que simplifican bastante el problema.
Ahí tendrías la solución indiscutible. Lo que ocurre es que no merece la pena. Resulta tan fácil hallar el camino desde los puntos en los que se puede hallar, que analizar todas las combinaciones parece un trabajo perdido.
En cualquier caso, lo bonito sería encontrar una demostración general aunque sólo sea para este tipo de matrices, que sirviera para definir los puntos que pueden formar un camino de Hamilton sea cual sea el número de puntos del grafo. Es decir, de ser ciertas las informaciones que tengo, estás reclamando un avance científico en las ciencias matemáticas. Casi nada.
Clásico
Novato de mierda
Asiduo
Freak
Veterano
