¿Qué es un grafo hamiltoniano? | 37/42 | UPV
HTML-код
- Опубликовано: 18 ноя 2024
- Título: ¿Qué es un grafo hamiltoniano?
Descripción: Introducción de conceptos relativos a los grafos hamiltonianos Jordan Lluch, C. (2010). ¿Qué es un grafo hamiltoniano?. hdl.handle.net/...
Descripción automática: En este video se explica el concepto de grafo hamiltoniano, la clausura de un grafo y su relación con los grafos eulerianos. Se define que un grafo hamiltoniano es aquel que contiene un ciclo que visita todos los vértices sin repetir ninguno, y se aclara que un grafo con un camino hamiltoniano (sin formar un ciclo) no es necesariamente hamiltoniano.
Se detalla el proceso de clausura de un grafo, consistente en unir vértices no adyacentes cuya suma de grados sea mayor o igual al número de vértices, de manera recursiva hasta que no se pueda continuar. Se menciona que la clausura es única para cada grafo y puede o no ser el grafo completo.
Por último, se distingue entre grafos hamiltonianos y eulerianos. Mientras que un grafo euleriano es aquel que permite un recorrido que pasa por todas las aristas una única vez y vuelve al punto de inicio, no se halla una relación directa con los hamiltonianos. Se concluye que a pesar de las aparentes similitudes de estos dos tipos de grafos, sus propiedades y métodos de estudio son independientes.
Autor/a: Jordan Lluch Cristina
Curso: Este vídeo es el 37/42 del curso Curso Teoría básica de grafos y análisis de 4 conocidos problemas | Universitat Politècnica de València (UPV). • Curso Teoría básica de...
Universitat Politècnica de València UPV: www.upv.es
Más vídeos en: / valenciaupv
Accede a nuestros MOOC: upvx.es
#Euleriano #Clausura #Camino hamiltoniano #Ciclo hamiltoniano #Hamiltoniano #MATEMATICA APLICADA
Excelente explicacion, gracias profesora
¡A ti!
Saludos
Cristina
Hola! Me gustaría conocer alguna bibliografía relacionada con los grafos hamiltonianos, sobre todo aquella en la que aparezca el concepto de clausura. Gracias de antemano!
Muy buena explicación
creo que te equivocas al definir un grafo euleriano ya que un grafo es euleriano si se pueden recorrer todas las aristas sin repetir ninguna, pero no importa si pasas varias veces por el mismo vértice, además que el teorema de Euler dice que un grafo es euleriano si y solo si, todos sus vértices son de grado par o tiene 2 vértices de grado impar, en cuyo caso habría que empezar a recorrer el grafo por alguno de los vértices de grado impar
Cómo se el grado de cada vertice ? se me quedó esa duda
ya entendí !!!!!! ajaja
me ayudan con esto por favor un grafo con 10 vértices y 9 aristas, en donde ningún vértice impar podrá mantener una conexión consecutiva (1->3->5)
O sea el grafo clausura es la unión de todos los G1...G6? O solo G6
Hola,
el grafo clausura es G6. Los Gi con i=1,2,3,4,5 son subgrafos de G6.
Saludos
Cristina
Un grafo completo siempre sera hamiltoniano?
La profesora comenta:"Sí, los grafos completos son hamiltonianos. Si los vértices son {v1,v2,...,vn}, siempre puedes escoger el ciclo hamiltoniano (entre otros) v1 -v 2 -...-v(n-1 )- vn - v1, dado que, por ser completo, existe una arista entre cualquier par de vértices distintos.
Saludos
Cristina
".
Por que dan mal la definición al principio, deben de decir que no se debn de repetir los vertices.
cállate el osico weon has tu propio vídeo si to no te agrada
@@crosvidable JAJAJAJAJAJAJA
Eso se sobreentiende con la definición de ciclo