Este es un problema clásico de teoría de grafos. Sin embargo hay que refinar la pregunta definiendo a lo que te refieres con un solo trazo. Si sólo te refieres a no levantar el lápiz una vez que empiezas el dibujo, la respuesta es que si se puede, sólo tendrías que pasar tu lápiz alrededor del cuadrado, trazar una diagonal, ir a otra esquina pasando por un lado ya dibujado y cruzar la última diagonal.
Sin embargo, al real problema denominado La Firma del Diablo, le agregas la condición de no poder trazar una línea dos veces. Este problema no tiene solución. Es decir
<><><> No puedes hacer dicho garabato. <><><>
Entonces a tu pregunta de ¿Cómo? La cambiaré por ¿Por qué?
La razón por la cual no existe solución para hacer dicho grafo con las restricciones descritas, es por que tu gráfica no es euleriana. Una gráfica es euleriana, si y sólo si a cada uno de sus vértices llega un número par de aristas. Y sólo en las gráficas eulerianas, se puede completar la trayectoria.
En el caso de la Firma del Diablo, tienes cuatro vértices y en cada vértice llegan 3 aristas.
Ahora veamos un poco de teoría de grafos para rematar tu respuesta. El tipo de recorrido como el que pides, con las restricciones de no levantar el lápiz y no recorrer dos veces la misma arista se conoce como recorrido euleriano y se debe a Leonard Euler, el cual en 1736 logra resolver un acertijo famoso de su época llamado el problema de los puentes de Königsberg. El problema básicamente es muy similar, es una ciudad por la cual cruzaba el Río Pregel, y dentro del río tenía dos islas y siete puentes que conectaban las islas y la ribera. No se pueden hacer dibujos aquí, pero te puedes dar una vuelta en los links para ver las figuras.
Euler va un poco más adelante y demuestra que no se puede realizar un recorrido como el que se pide si la grafica no es euleriana. La demostración, básicamente es que para cada vértice necesitarás una entrada y una salida por lo cual las aristas deben de venir en pares.
Espero que te sea útil y cualquier duda no dudes en contactarme.
Answers & Comments
Verified answer
Este es un problema clásico de teoría de grafos. Sin embargo hay que refinar la pregunta definiendo a lo que te refieres con un solo trazo. Si sólo te refieres a no levantar el lápiz una vez que empiezas el dibujo, la respuesta es que si se puede, sólo tendrías que pasar tu lápiz alrededor del cuadrado, trazar una diagonal, ir a otra esquina pasando por un lado ya dibujado y cruzar la última diagonal.
Sin embargo, al real problema denominado La Firma del Diablo, le agregas la condición de no poder trazar una línea dos veces. Este problema no tiene solución. Es decir
<><><> No puedes hacer dicho garabato. <><><>
Entonces a tu pregunta de ¿Cómo? La cambiaré por ¿Por qué?
La razón por la cual no existe solución para hacer dicho grafo con las restricciones descritas, es por que tu gráfica no es euleriana. Una gráfica es euleriana, si y sólo si a cada uno de sus vértices llega un número par de aristas. Y sólo en las gráficas eulerianas, se puede completar la trayectoria.
En el caso de la Firma del Diablo, tienes cuatro vértices y en cada vértice llegan 3 aristas.
Ahora veamos un poco de teoría de grafos para rematar tu respuesta. El tipo de recorrido como el que pides, con las restricciones de no levantar el lápiz y no recorrer dos veces la misma arista se conoce como recorrido euleriano y se debe a Leonard Euler, el cual en 1736 logra resolver un acertijo famoso de su época llamado el problema de los puentes de Königsberg. El problema básicamente es muy similar, es una ciudad por la cual cruzaba el Río Pregel, y dentro del río tenía dos islas y siete puentes que conectaban las islas y la ribera. No se pueden hacer dibujos aquí, pero te puedes dar una vuelta en los links para ver las figuras.
Euler va un poco más adelante y demuestra que no se puede realizar un recorrido como el que se pide si la grafica no es euleriana. La demostración, básicamente es que para cada vértice necesitarás una entrada y una salida por lo cual las aristas deben de venir en pares.
Espero que te sea útil y cualquier duda no dudes en contactarme.