Caminos y Ciclos Hamiltonianos en Grafos

• Los caminos y ciclos hamiltonianos se caracterizan por pasar solo una vez por cada vértice, no importan las conexiones.
• Para los caminos: grado vértice inicial + grado vértice final >= cantidad_vertices -1. Si se cumple puedo decir que si hay camino hamiltoniano, si no se cumple no se puede saber si hay o no el camino.
• Cuando uno de los vértices es igual a 1, podemos asegurar que no hay gráfico hamiltoniano.
• Si hay ciclo pero no camino, entonces no es grafo hamiltoniano

El camino hamiltoniano, es uno de los problemas todavía sin resolver en el mundo de las matemáticas.

Los vértices con grado uno, nos dicen que un grafo, ya no es hamiltoneano.

Los caminos hamiltonianos, buscan los vértices no los caminos y cada uno de los vértices se tiene que recorrer sin repetición alguna, excepto por los ciclos, en dónde necesitamos llegar al nodo al que llegamos.

Un profesor completamente confundido e ignorante de este tema. La plataforma debería tener un profesor revisor de cada curso, que pudiera evitar subir este tipo de contenido. La crítica es para que sustituyan la lección por una que sea correcta.

Resumen
los caminos y ciclos hamiltonianos buscaran recorrer los nodos una sola vez sin importar el camino que utilicemos.

Para afirmar que hay un camino hamiltoniano se debe cumplir la condición donde la suma del grado de dos vértices es mayor o igual al número de vértices menos uno, de otra forma puede que exista el camino hamiltoniano, pero no se podrá afirmar.

Si hay un camino hamiltoniano, pero no un ciclo, entonces el grafo no es hamiltoniano. Si hay un nodo de grado 1 entonces no hay ciclo hamiltoniano

Caminos y ciclos Hamiltonianos
Para que un grafo se considere hamiltoniano, este debe tener camino y ciclo. Por tanto el grado mínimo de cada vértice o nodo debe ser 2 o más.

• Si hay Camino hamiltoniano y Si hay ciclo hamiltoniano = Es grafo hamiltoniano

• Si hay camino hamiltoniano y No hay ciclo hamiltoniano = NO es grafo hamiltoniano

Los caminos hamiltonianos buscan pasar solo 1 vez por los vértices, sin importar la cantidad de veces que repitamos un camino o dejemos de pasar por alguno.

Los ciclos hamiltonianos, tienen el mismo principio que los caminos, con la diferencia que se debe cerrar el ciclo, es decir, se debe iniciar y terminar en el mismo vértice.

Condicionales adicionales: Se puede determinar si un grafo es hamiltoniano si la suma de dos vértices cualquiera, son >= que la cantidad de vértices existentes. Sin embargo, si no se cumple esta condición, no significa que el grafo no sea hamiltoniano. La condición solo te asegura que el grafo es hamiltoniano, pero no lo niega.

Observaciones:

1. Un grafo es Hamiltoniano si contiene un ciclo Hamiltoniano

2. por lo tanto, si un grafo no contiene un ciclo Hamiltoniano entonces no es un grafo Hamiltoniano

3. En consecuencia, un grafo Hamiltoniano no puede tener un vértice de grado 1 ya que este último necesita de otra arista que incida desde otro vértice.

4. De acuerdo al los ejemplos gráficos del minuto 5:28 podemos tener un camino Hamiltoniano pero sin tener un ciclo Hamiltoniano (y por tanto un grafo Hamiltoniano)

Condiciones para verificar que es un camino o ciclo hamiltoniano
Cuando yo identifique los grados de los vértices seleccionados siempre tienen que ser mayor o igual a n-1 y la n representa el número de vértices que yo tengo en el gráfico.

los caminos hamiltonianos buscan recorrer un nodo al menos una vez sin importar el numero deveces que pasemos por el camino o si no pasa por el.
El camino debe cumplir una condicion que es que la sumatoria del grado de los nodos debe ser mayor o igual al numero de nodos menos uno, si esta condicion se cumple podemos afirmar que hay un camino hamiltoniano, si no se cumple, puede que haya o no un camino.
ciclo hamiltoniano: inicia y termina en el mis punto.
Para que haya un grafo hamiltoniano los nodos deben tener mas de un grado, si solo tiene 1 no es un grafo, ademas si hay camino pero no ciclo tampoco es un grafo hamiltoniano

Debería decir “aristas” en lugar de “caminos” para no generar confusión.

Mis apuntes
https://www.remnote.io/a/caminos-y-ciclos-hamiltonianos-/6390fdef19eda1e1600c89ed

Les recomiendo esta playlist de la UPV donde se presenta una excelente introducción a la teoría de grafos.
https://www.youtube.com/playlist?list=PL5098BF5A01819B3B

Camnios y ciclos hamiltonianos:
Buscar recorrer todos los vertices una vez, pero los caminos se pueden recorrer dos veces.

Caminos y Ciclos Hamiltonianos:
En este caso buscamos pasar por los vertices una sola vez. En el camino no es necesario iniciar y terminar en el mismo punto pero en el ciclo sí.
Ecuación para saber si un grafo tiene un ciclo Hamiltoniano:
Si la suma de los grados de dos vertices (los menores) es mayor o igual que el número de vertices (n) menos uno, podemos afirmar que hay un ciclo hamiltoniano.
Grado(a) + Grado(b) >= n-1
Nota:
Esta no es condición necesaria para que haya un ciclo hamiltoniano, puede darse el caso que la relación no se cumpla y exista un ciclo hamiltoniano

Grafos no hamiltonianos:
Son grafos que no tienen un ciclo hamiltoniano.

si no hay cliclo hamiltomiano no es un grafo hamiltoniano

cominos hamiltoniano donde se recorren los vertices solo una vez

Ya había escuchado de este tipo de gráficos. pero no sabia que así se representaban.
Muy buena clase.

camino hamiltoniano, pasar por TODOS LOS VÉRTICES O NODOS UNA SOLA VEZ, sin importar los caminos que utilicemos.

Entiendo que podemos dar como consejo, que para verificar debemos observar que la cantidad de unos por columna sea menor o igual a dos.

Hay algún artículo, foro, etc… Que se hable de este tema donde se encuentren definiendo la condición para saber si hay un camino hamiltoniano o no?

Que es un camino simple, o como lo puedo determinar?

Estuvo genial.

Excelente.

Interesante, con solo unas condiciones descartamos, si hay vértices grado uno o si hay un camino pero no un ciclo entonces el grafo no es hamiltoniano.

Analizando el grafo del ciclo, la cantidad de vértices son 7, por lo tanto la desigualdad debería tener el miembro de la derecha el valor de 6, no de 5.

Buena clase

• Caminos y ciclos hamiltonianos, recorren todos los nodos una sola vez pasando por cualquier enlace.

• Hay un camino hamiltoniano si la suma del grado de dos vértices es mayor o igual al número de vértices menos uno, de otra forma puede que exista el camino hamiltoniano, pero no se podrá afirmar.

• Si hay un camino hamiltoniano, pero no un ciclo, entonces el grafo no es hamiltoniano.

Interesante contenido

Es más, sea G=(V,E) un grafo simple tal que |V|=n y para cualquier par de nodos no adyacentes u,v. Si se cumple que
grado(u)+grado(v) >= n+1
Entonces G siempre es conexo