Y después de la cabra, los (putos) puntos ...

[Metro-Freak]

El camino que pretendes hacer, es un camino hamiltoniano. (Unir todos los vertices con los caminos posibles, sin pasar por un vertice otra vez).

El camino no lo encontraras nunca. Me explico.

Todos los vertices (los puntos) tienen grado 4, excepto los superiores que tienen grado 2. Lo que pretendes és entrar en un vertice, salir de el , y no volver a entrar. Pero jamás encontrarás un camino, debido que al ser todos los vertices de grado par, no podras encontrar un camino que entre pero que no salga.

No sé si me he explicado (pero me da que no, pq voy un poco fumado)

El algorismo que te lo dice? Al ser un graf simetrico (sin sentido) puedes utilizar dos metodos.

1) Algorismo de Robert i Edmonds.

2) Algorismo de multiplicaciones latinas

Saludos.

despues de esta respuesta entendemos el porqué de tu nick xDDD

 

[pi]

pi, yo también pienso que no tiene solución.

Pero una duda:
¿porqué te centras en los caminos hamiltonianos? puede que no exista camino hamiltoniano, pero dAN1 no nos indica que el camino tenga que ser cerrado, dice que se puede repetir en caso necesario el último punto.

Es lo que explica Nofollador, que se trata de un camino de Hamilton (es simplemente su nombrecito).

La opción de acabar en el mismo punto es limitativa, pues entonces formaría un ciclo hamiltoniano (más difícil todavía).

El camino no lo encontraras nunca. Me explico.

Todos los vertices (los puntos) tienen grado 4, excepto los superiores que tienen grado 2. Lo que pretendes és entrar en un vertice, salir de el , y no volver a entrar. Pero jamás encontrarás un camino, debido que al ser todos los vertices de grado par, no podras encontrar un camino que entre pero que no salga.

Esto no es correcto.

De hecho, si comienzas por el primer punto, sí consigues formar un camino y los grados no cambian.

El planteamiento que haces es similar al teorema de Euler para los caminos eulerianos (los formados recorriendo las aristas), pero como puedes comprobar no sirve para este caso.

El asunto es mucho más fácil.

 

[Nofollador]

pi, yo también pienso que no tiene solución.

Pero una duda:
¿porqué te centras en los caminos hamiltonianos? puede que no exista camino hamiltoniano, pero dAN1 no nos indica que el camino tenga que ser cerrado, dice que se puede repetir en caso necesario el último punto.

Es lo que explica Nofollador, que se trata de un camino de Hamilton (es simplemente su nombrecito).

La opción de acabar en el mismo punto es limitativa, pues entonces formaría un ciclo hamiltoniano (más difícil todavía).

El camino no lo encontraras nunca. Me explico.

Todos los vertices (los puntos) tienen grado 4, excepto los superiores que tienen grado 2. Lo que pretendes és entrar en un vertice, salir de el , y no volver a entrar. Pero jamás encontrarás un camino, debido que al ser todos los vertices de grado par, no podras encontrar un camino que entre pero que no salga.

Esto no es correcto.

De hecho, si comienzas por el primer punto, sí consigues formar un camino y los grados no cambian.

El planteamiento que haces es similar al teorema de Euler para los caminos eulerianos (los formados recorriendo las aristas), pero como puedes comprobar no sirve para este caso.

El asunto es mucho más fácil.

Evidentemente. Los grados no cambian, pq son los que hay.

Estamos buscando un camino hamiltoniano. Nada de caminos eulerianos.

En todo caso, haz servir el algorismo de las multiplicaciones latinas o bien el de Robert y Edmonds. No encontraras un camino que cumpla las condiciones descritas al principio.

Os lo dejo facil, y lo probais en alguna pagina web. (el algorismo)

 

[tibetano]

Ejem..., he hallado una demostración general.

Iba a ponerla directamente pero quizá a alguien le apetezca averiguarlo.

En cualquier caso el teorema sí se puede exponer:

Para cualquier grafo formado por una matriz cuadrada simétrica de orden n impar con aristas ortogonales, no se podrán formar caminos hamiltonianos desde los puntos situados en las diagonales que no tengan intersección con los puntos de la diagonal principal.

Es decir, para dibujitos formados por puntitos con el mismo numero de filas y columnas, siendo éstas impares, es imposible hacer el recorrido completo por todos los puntos y sin repetir ningún punto, si se comienza por los puntos pares (como en el dibujo de Dan).

Demostrarlo es relativamente sencillo, de hecho, al intentarlo, nos damos cuenta de por qué no nos sale el camino. Pues bien, basta con explicar ese por qué de tal manera que la explicación resulte evidente incluso para un número ilimitado de puntitos.

No se necesitan conocimientos matemáticos (bueno, los de primero de primaria).

no tienes ni puta idea listo..

 

[NomadS0ul]

De pequeño me contaban historias sobre gente que se pasaba horas y horas hablando del mismo tema pero que en realidad no aportaban nada......

 

[pi]

pi, yo también pienso que no tiene solución.

Pero una duda:
¿porqué te centras en los caminos hamiltonianos? puede que no exista camino hamiltoniano, pero dAN1 no nos indica que el camino tenga que ser cerrado, dice que se puede repetir en caso necesario el último punto.

Es lo que explica Nofollador, que se trata de un camino de Hamilton (es simplemente su nombrecito).

La opción de acabar en el mismo punto es limitativa, pues entonces formaría un ciclo hamiltoniano (más difícil todavía).

El camino no lo encontraras nunca. Me explico.

Todos los vertices (los puntos) tienen grado 4, excepto los superiores que tienen grado 2. Lo que pretendes és entrar en un vertice, salir de el , y no volver a entrar. Pero jamás encontrarás un camino, debido que al ser todos los vertices de grado par, no podras encontrar un camino que entre pero que no salga.

Esto no es correcto.

De hecho, si comienzas por el primer punto, sí consigues formar un camino y los grados no cambian.

El planteamiento que haces es similar al teorema de Euler para los caminos eulerianos (los formados recorriendo las aristas), pero como puedes comprobar no sirve para este caso.

El asunto es mucho más fácil.

Evidentemente. Los grados no cambian, pq son los que hay.

Estamos buscando un camino hamiltoniano. Nada de caminos eulerianos.

En todo caso, haz servir el algorismo de las multiplicaciones latinas o bien el de Robert y Edmonds. No encontraras un camino que cumpla las condiciones descritas al principio.

Os lo dejo facil, y lo probais en alguna pagina web. (el algorismo)

Ya se sabe que son caminos de Hamilton.

Pero no has entendido el error de tu argumento. Si la explicación fuera el número de aristas, entonces no se podría formar el camino desde cualquier punto del grafo, pero sí se pueden realizar caminos desde varios puntos (concretamente desde 13).

Además sí hay vértices con grado impar, todos los laterales salvo las esquinas.

Puede que hayas pensado una cosa y que hayas escrito otra,...suele pasar.

Si lo que quieres decir es que la imposibilidad de formar el camino depende de la secuencia de los vértices y del número de aristas de estos... Pues no sé. Vamos, que sí conozco algunas combinaciones cuyo inicio no forma camino (la 3-2) por ejemplo, pero hay combinaciones (4-4-4) que pueden formar camino o no formarlo. Por lo tanto no vale ese sistema. De hecho, para averiguar si dichas combinaciones forman camino o no, empleo el teorema expuesto más arriba.

En cualquier caso, puede que se me haya pasado algo y como tampoco conozco los algoritmos que citas... (Ponlos.)

Por mi parte, pongo el grafo que demuestra el teorema (es mi nuevo avatar), observándolo, la explicación del teorema es asequible incluso para Tibetano.