S6.10- Teoremas de Dirac y Ore | 22/49 | UPV

Título: S6.10- Teoremas de Dirac y Ore
Descripción automática: En este video, se abordan los teoremas de Dirac y Ore, que permiten establecer la existencia de caminos y ciclos hamiltonianos en grafos, y se aplican para resolver problemas sobre la disposición de personas en eventos sociales. Los teoremas establecen condiciones bajo las cuales se pueden encontrar ciclos o caminos que incluyen todos los vértices de un grafo una única vez, denominados hamiltonianos.
Se presenta el teorema de Dirac, que requiere que en un grafo no dirigido y simple con al menos tres vértices, cada vértice tenga un grado mayor o igual a la mitad del número total de vértices para garantizar un ciclo hamiltoniano. El teorema de Ore extiende esta idea estableciendo que en un grafo con al menos tres vértices, si la suma de los grados de cada par de vértices no adyacentes es mayor o igual al número total de vértices, entonces el grafo es hamiltoniano.
En el video se aplican estos teoremas a escenarios cotidianos. Primeramente, se examina la posibilidad de sentar personas en una cena de modo que cada una conozca a sus vecinos, verificándose que es posible cuando cada persona conoce al menos a tres otras. Luego, se determina que es factible ordenar un grupo de personas en la entrada de un cine para que personas consecutivas en la cola se conozcan usando una variación del teorema de Dirac para caminos hamiltonianos.
Finalmente, se destaca que las condiciones de los teoremas son suficientes para afirmar la existencia de ciclos o caminos hamiltonianos pero no necesariamente requeridas, como ilustran los ejemplos dados. Los teoremas ofrecen soluciones efectivas a los problemas planteados relacionados con la teoría de grafos y las interacciones sociales.
Autor/a: Conejero Casares José Alberto
Curso: Este vídeo es el 22/49 del curso MOOC Aplicaciones de la Teoría de Grafos a la vida real II | Universitat Politècnica de València (UPV). • MOOC Aplicaciones de l...
+ Universitat Politècnica de València UPV: www.upv.es
+ Más vídeos en: / valenciaupv
+ Accede a nuestros MOOC: upvx.es
#matemáticas #grafos #eulerianos #grafos #hamiltonianos #dirac #ore #teorema #matemáticas

[@wilsonfernandez1161]

en el teorema de ore cuando no se puede mejorar la hipótesis, se puede ver un error ya que los vértices A y B no son adyacentes pero la suma de sus grados es '6' no 4

[@pmasche]

Seguramente sea una confusión y quiso decir 'c' y 'd' o 'd' y 'e', donde la suma de grados si es 4

[@jordyalexiscamacchipana3509]

Exactamente jajajaja justo paso a ver los comentarios para ver si lo mencionaban, se equivoco de vertices

[@alexsaiztalavera9191]

@@pmasche Muy buena observación

[@mariafernandalopezfernande4306]

Muchas gracias me sirvió muchísimo el vídeo muy bien explicado :) :) :) :) :) :)

[@johnalexandermendozasanche1405]

muy bueno el vídeo, mil gracias

[@lucastolosa2193]

Genio gracias!

[@nigelboada]

10 años tarde, pero en 6:12 menciona que las condiciones son necesarias pero no suficientes. Es al revés, tal y como se especifica en la diapositiva. Las condiciones son suficientes pero NO necesarias.