Menéame: comentarios [1204460]

#3 Un problema de ciudades y carreteras

rtomas — Sat, 19 Mar 2011 11:40:37 +0000

ah! que tiene que ser Hamiltoniano, regresar al punto de partida. En el video no esta muy claro.
#1 tienes razon

» autor: rtomas

#2 Un problema de ciudades y carreteras

rtomas — Sat, 19 Mar 2011 11:24:38 +0000

1,11,5,8,7,4,10,3,9,2,6, no?

» autor: rtomas

#1 Un problema de ciudades y carreteras

KaisserSozze — Fri, 18 Mar 2011 17:50:18 +0000

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í.

» autor: KaisserSozze