Bordado euleriano

Angélica ha estado practicando el bordado en estos días, y estando en eso se topó con un problema interesante: había que marcar los trazos de cierta figura dos veces, pero sin cortar el hilo. El dibujo en cuestión es algo así.

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.