Estoy leyendo el libro de Peralta, el tema de Grafos y Caminos/Ciclos de Hamilton. Primero dice que no hay condiciones para que un grafo tenga un camino (ciclo) de Hamilton, y después da dos condiciones para que el grafo tenga un ciclo de Hamilton y sea Hamiltoniano. En qué quedamos?

Y otra cosa, un grafo es Hamiltoniano cuando tiene un ciclo de Hamilton?

Gracias!

Camino no es lo mismo que Ciclo.
El ciclo de Hamilton pasa por todos los vertices sin repetir y vuelve al mismo (el ciclo termina donde se empezo, se repite el primer vertice nomas), el camino no necesariamente vuelve al mismo vertice.

Gracias Sergio.
Igualmente, la diferencia entre camino y ciclo la tengo clara, mi problema es que no sé si hay alguna condición que deba cumplir un grafo para tener ciclos o caminos de Hamilton. ¿Se entiende?

Por ej, un grafo que tenga todos los vértices con grado par tiene ciclos de Euler. Además, un grafo que tenga cero o dos vértices con grado impar, tiene camino de Euler. ¿Hay alguna condición de este estilo pero para los caminos/ciclos de Hamilton?

Nop, para Hamilton no hay teorema. La definicion es la misma que el de Euler pero con vertices, pero no hay una regla o algo que te ayude a saber cuando puede haber o no camino/ciclo de Hamilton.

Eso quería saber, muchas gracias!

Si tenés un grafo completo de más de 2 vertices, si o si tiene ciclo de Hamilton

Cita:Nop, para Hamilton no hay teorema. La definicion es la misma que el de Euler pero con vertices, pero no hay una regla o algo que te ayude a saber cuando puede haber o no camino/ciclo de Hamilton

Si que hay teorema. Que no te lo enseñen es otra cosa :p

Dem0 escribió:Si tenés un grafo completo de más de 2 vertices, si o si tiene ciclo de Hamilton

Cita:Nop, para Hamilton no hay teorema. La definicion es la misma que el de Euler pero con vertices, pero no hay una regla o algo que te ayude a saber cuando puede haber o no camino/ciclo de Hamilton

Si que hay teorema. Que no te lo enseñen es otra cosa

jaja es que precisamente nos dijeron que NO HAY TEOREMA jajaja pero bue, algo debe haber...

Sergio escribió:

Dem0 escribió:Si tenés un grafo completo de más de 2 vertices, si o si tiene ciclo de Hamilton

Cita:Nop, para Hamilton no hay teorema. La definicion es la misma que el de Euler pero con vertices, pero no hay una regla o algo que te ayude a saber cuando puede haber o no camino/ciclo de Hamilton

Si que hay teorema. Que no te lo enseñen es otra cosa :p

jaja es que precisamente nos dijeron que NO HAY TEOREMA :P jajaja pero bue, algo debe haber...

Jajajaja seee es muy raro todo, por eso preguntaba. En la misma página del libro peralta dice que no hay y que sí hay condición (a menos que haya leído/interpretado mal :wall: ).

Recién leí de nuevo el mensaje de Dem0, me había salteado la palabra "completo" :P

Ese teorema sí está en el libro, lo que yo preguntaba era una condición suficiente para cualquier grafo. Eso es lo que no encuentro.