No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Adquiere por un a帽o todos los cursos, escuelas y certificados por un precio especial.

Antes: $249

Currency
$219/a帽o

Paga en 4 cuotas sin intereses

Paga en 4 cuotas sin intereses
Comprar ahora

Termina en:

0D
22H
49M
24S

Caminos y ciclos hamiltonianos

20/40
Recursos

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.

Aportes 34

Preguntas 6

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

  • 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

Hola. (^u^)/
Duda en la condici贸n de la suma de grados de los v茅rtices, 驴Se suman los grados de los vertices inicial y final, es decir, donde voy a empezar y terminar mi camino, o se suman los dos v茅rtices con menor grado, o es igual, puedo sumar los grados de dos nodos cualesquiera?

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.

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.

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.

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.

Deber铆a decir 鈥渁ristas鈥 en lugar de 鈥渃aminos鈥 para no generar confusi贸n.

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

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