Caminos y Ciclos Hamiltonianos en Grafos

Clase 20 de 40 • Curso de Matemáticas Discretas

Resumen

A diferencia de los caminos y ciclos eulerianos, 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.

Jose Rodriguez

student•

si hay un camino pero no hay un ciclo entonces no es un grafico hamiltoniano
si hay vertices grado 1 no hay grafico hamiltoniano

Sergio Orduz

teacher•

Genial tu resuén barinet 😄

Wilson Fernando Antury Torres

student•

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

Luis Fernando Úbeda Camacho

student•

Apuntes de clase

La diferencia principal de los caminos y ciclos hamiltonianos respecto a los eulerianos es que para los hamiltonianos la prioridad principal es la de recorrer todos los vértices una vez sin importar el número de veces que pasemos por las conexiones, incluso habrá conexiones que ni utilizaremos.
Siempre teniendo en cuanta las diferencias entre camino y ciclo

Maria Guadalupe Diaz Escobar

student•

Gracias

Sara Yaneth Contreras Elías

student•

Percival Ernesto Amezola Rivera

student•

Por alun motivo no puedo ver tus imágenes.

Miguel Andres Rendon Reyes

student•

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

Miguel Andres Rendon Reyes

student•

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

Miguel Andres Rendon Reyes

student•

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.

Robert Junior Buleje del Carpio

student•

pero, un camino eureliano no contradice la definición inicial de camino. ? no sería mejor llamarlo cadena eureliana ??

William Wilfredo Moran Torres

student•

En el ejemplo de 3 vertices si puede ser un camino hamiltoniano pero no puede ser un ciclo hamiltoniano?

Milton Martinez

student•

En los 3 ejemplos de grafos no hamiltonianos hay camino pero no ciclo.

Percival Ernesto Amezola Rivera

student•

Hola 👋 Platzinautas 🚀 ¿Para que servirá este ciclo hamiltoniano en programación?

Daniel Cueto

student•

Hola no entiendo la condición. Tiene que ser todos o por lo menos un par que haga que se cumpla la condición? ![](

Por ejemplo en ese gráfico, si sumamos δc=2 δd=1, es 3, y 3 no es mayor o igual a 5, sin embargo sí existe un camino hamiltoniano ;-;

Milton Martinez

student•

Lo que dice es que si cumple, es seguro que haya camino. Pero si no cumple, puede o no existir.

ERNESTO HAMILTON SALMÁN

student•

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.

Kevin Isaac

student•

¿Por qué lo menciona?

Max Andy Diaz Neyra

student•

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

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

Elian Paniagua

student•

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.

Percival Ernesto Amezola Rivera

student•

¿Qué condición hay para que sea un ciclo hamiltoniano?

JUAN CAMILO CAMPO TANGARIFE

student•

Aplica pra amgos, que son grafos hamiltonianos, los ciclos y los caminos.

Nora Azua

student•

Percival Ernesto Amezola Rivera

student•

Claudio Caniullan Calfin

student•

Observaciones:

Un grafo es Hamiltoniano si contiene un ciclo Hamiltoniano
por lo tanto, si un grafo no contiene un ciclo Hamiltoniano entonces no es un grafo Hamiltoniano
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.
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)

Gabriela Maria Marin Zelaya

student•

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.

JOSE MANRIQUE

student•

En la parte donde suma el Grado(c) y Grado(f), por qué considera esos??

Milton Martinez

student•

En realidad se debe cumplir para para todo par de vértices no adyacentes, seguramente toma esos porque son los más chicos.

Lucia Amparo Osorio Hernandez

student•

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

Emanuel Mendoza

student•

Tu resumen tiene muchos errores, dejame darte un par de correcciones. Un camino hamiltoniano es un recorrido dentro de un grafo que pasa por todos los vértices exactamente una vez, sin repetir ninguno.

Un ciclo hamiltoniano es un camino hamiltoniano que además regresa al vértice de inicio, formando un ciclo.

Una condición suficiente (pero no necesaria) para la existencia de un camino hamiltoniano en un grafo es que para cada par de vértices no adyacentes u y v, se cumpla la desigualdad:

grado(u)+grado(v)≥n−1

Si esta condición se cumple para todos los pares de vértices no conectados, el grafo seguro tiene un camino hamiltoniano. Si no se cumple, aún podría existir uno.

Un grafo hamiltoniano es aquel que contiene al menos un ciclo hamiltoniano.