15-10-2008, 17:48
Hace años que me dijeron que intentara hacer este dibujo,comenzando desde cualquier lado y sin levantar el lapiz del papel y sin pasar dos veces por la misma linea,pero nada no lo he logrado nunca,no se si soy muy torpe,que seria lo normalo que no tiene solucion,aqui os lo dejo para que lo intenten,no se si me he explicado bien,espero que si
,
saludos.
Según el test de paridad ... no se puede
http://www.oma.org.ar/omanet/misc/01-04.htm
Salu2
Keep on Rollin'
Buenas! Más concretamente, no tiene solución, por lo siguiente:
Considera la figura como un grafo, en el que cada vértice es un nodo y cada lado es una arista del grafo. Ahora bien: "Un grafo euleriano es aquel que tiene todos los vértices pares", es decir, cada nodo del grafo posee 2*n aristas.
La condición de dibujar el grafo sin levantar el lápiz del papel, viene a decir que por cada vez que llegas a un nodo tiene que existir al menos otra arista en ese nodo por la que poder salir de él. Por tanto para poder realizarlo, debemos tener arista de llegada + arista de salida = 2 aristas (número par). O dicho de otro modo, si poseemos 123 aristas de entrada, deben existir 123 aristas de salida: (123 de entrada + 123 de salida = 246 (número par). Evidentemente podemos pensar que nos podemos permitir dibujar el grafo sin levantar el lápiz del papel, si tenemos dos nodos impares (2n-1 aristas; n>0), correspondientes al nodo inicial y nodo final del recorrido, es decir, si un grafo posee todos los nodos pares y dos impares, entonces para poder realizar el problema, debemos empezar en uno de los impares y acabar en el otro impar.
Por tanto, la conclusión es la siguiente: Si un grafo es euleriano (posee todos los nodos con número de arista par), entonces podemos dibujarlo sin problemas, empezando en cualquier nodo y acabando en ese mismo nodo (hacemos un camino cerrado). Si por contra posee vértices impares, entonces la condición es que ese número de vértices impares sea dos, y por tanto podemos dibujarlo empezando en uno de los impares, y acabando en el otro impar (camino abierto).
En ese ejemplo, tenemos un grafo NO EULERIANO, porque posee vértices impares, y además no podemos dibujarlo sin levantar el lápiz porque el número de vértices impares es mayor que dos. Si vemos el número de aristas que posee cada nodo, empezando por el nodo superior y siguiendo el sentido de las agujas del reloj tenemos que el primer vértice posee 2 aristas (vértice par), el segundo 5 (vértice impar), el tercero 2 (vértice par), el cuarto 5 (impar), el quinto 2 (par), el sexto 5 (impar), el séptimo 2 (par), y el octavo 5 (impar). Por tanto, no es euleriano, y además posee más de 2 vértices impares, lo que implica que NO SE PUEDE DIBUJAR SIN LEVANTAR EL LAPIZ DEL PAPEL.
Si no lo entiendes bien, piensa el siguiente ejemplo: imagina un póligono cerrado cualquiera, por ejemplo un rectángulo. Cada nodo de ese grafo (cada vértice del rectángulo), posee 2 aristas. Por tanto, es euleriano, con lo cual puedes empezar en cualquier vértice y además acabar en el vértice de partida. Ahora imagina ese mismo rectángulo con una diagonal cualquiera. Tenemos dos vértices impares (de 3 aristas) y dos pares (de 2 aristas). No es euleriano, pero posee dos vértices impares. Para dibujarlo sin levantar el lápiz del papel, debes empezar en uno impar, y además acabarás en el otro impar. Si empezaras en uno par, no encontrarías solución (haz la prueba).
Si tienes en cuenta las condiciones que he explicado, SIEMPRE podrás encontrar el camino que contenga todas las aristas, sin temor a equivocarte.
¿Ok?
Un saludo.
Última edición por hystd; 15-10-2008 a las 21:06
¡Y que lleve yo años intentandolo!
Si si, yo hoy he estado un ratejo... y cada vez estaba mas seguro de que lo iba a conseguir "ésta ésta! esta va bien" jajaja
Gracias hystd, sabiendo que no s epuede ya duermo tranquilo
Marcadores