El concurso durará 30 semanas y podéis ver en qué consiste y el primer problema en
http://www.elpais.com/videos/sociedad/problema/ciudades/carreteras/elpepusoc/20110318elpepusoc_1/Ves/
Sólo tenéis que entrar y votar el vídeo.
Todos los viernes habrá un nuevo vídeo y os haremos llegar el link de cada problema.
Alumnos de 3B, 4A-B y 1C, podéis colgar vuestras soluciones en forma de comentario.
Alumnos de 3B, 4A-B y 1C, podéis colgar vuestras soluciones en forma de comentario.
Este comentario ha sido eliminado por el autor.
ResponderEliminarEl problema se reduce a encontrar, lo que en teoría de grafos, se llama ciclo o camino euleriano. (En realidad un ciclo o camino euleriano tiene que terminar y empezar en el mismo vértice).
ResponderEliminarHay dos expresiones que se puede demostrar que son equivalentes.
1- G es un grafo euleriano (posee ciclo euleriano)
2- Cada vértice del grafo tiene valencia >= 2, y esa valencia es par. (la valencia es el número de aristas que inciden en un vértice).
Si nos centramos en esta segunda expresión vemos que hay vértices que no tienen valencia par, por tanto el problema no tiene solución.
Fdo: Alejandro Quirós
¿Podrías especificar qué vértices tienen valencia par?
ResponderEliminarPodemos detectar un grafo no hamiltoniano si dicho grafo contiene un número impar de vértices y algunos son de valencia impar.
ResponderEliminarFdo: Alejandro Quirós
Mirant el dibuix que es fa al vídeo, podem distingir entre dos tipus de 'pobles'. Per exemple, pintem un dels grups (2-3-4-8-11) de roig i l'altre grup (1-5-6-7-9-10) de verd. I observem que quan tracem la trajectòria sempre aniràs d'un poble verd a un roig i d'un roig a un verd.
ResponderEliminarCom que hi ha 5 verds i 6 roigs, demostrem que és impossible solucionar el problema que ens plantejaven. Si comencem per un poble roig l'últim seria també roig i no quedaria ningun verd per a tornar al poble roig de l'inici; i si comencem per un de verd al final ens sobraria un roig. Així que no es pot passar per tots els pobles sense repetir ningún i tornar al poble de l'inici, encara que si no haguerem de tornar si que podriem realitzar-ho si comencem per un poble roig.
Sara Verdú.