Adolfo Quirós, de la Real Sociedad Matemática Española, organismo que en 2011 cumple cien años, y profesor de la Universidad Autónoma de Madrid, plantea un problema a nuestros lectores. Quién sepa la respuesta puede escribir antes de las 00.00 del martes al correo participación@elpais.es. Entre los acertantes se sorteará la colección completa de libros de matemáticas cuyo primer volumen sale...
Si no recuerdo mal mis clases de la facultad es imposible. Se puede pasar a un grafo que se llama bipartito, es decir, que se pueden construir dos grupos de vértices (ciudades) que solo se relacionan con las del otro grupo, no con las del suyo. Eso hacia imposible que tenga solución. Esos dos grupos serian (1,9,10,6,7,5) y (8,11,3,2,4). Lo que no recuerdo es como demostrar que un grafo bipartito no tenia un camino hamiltoniano, que creo que se llamaban así.
Comentarios
1,11,5,8,7,4,10,3,9,2,6, no?
Si no recuerdo mal mis clases de la facultad es imposible. Se puede pasar a un grafo que se llama bipartito, es decir, que se pueden construir dos grupos de vértices (ciudades) que solo se relacionan con las del otro grupo, no con las del suyo. Eso hacia imposible que tenga solución. Esos dos grupos serian (1,9,10,6,7,5) y (8,11,3,2,4). Lo que no recuerdo es como demostrar que un grafo bipartito no tenia un camino hamiltoniano, que creo que se llamaban así.
ah! que tiene que ser Hamiltoniano, regresar al punto de partida. En el video no esta muy claro.
#1 tienes razon