Naturalmente que esto se reduce a encontrar un circuito euleriano. Claro, no en un grafo que resulta de interpretar tal cual este dibujo (pues tendría vértices de grado impar, lo que haría imposible el circuito), sino en uno donde cada arista se duplica. En otras palabras, se trata de un multigrafo tal que todos sus vértices son de grado par, por lo que es posible visitar todas sus aristas sin repetirlas y regresando al punto de partida según el teorema de Euler-Hierholzer. El multigrafo que surge y una solución (que no es única, sin duda, pero es la que usó Ange) se muestra a continuación.
Es obvio que este problema (y sus variantes hamiltonianas) se ha considerado con mayor seriedad y se han resuelto hasta donde permite el conocimiento actual. Hay un artículo de Arkin, Kim, Kostitsyna, Mitchell y Sabhnani al respecto, y otro de Joshua Holden que también es muy interesante, a los cuales refiero al lector interesado.
No hay comentarios.:
Publicar un comentario