Introducción al curso

1

Matemáticas Discretas: Lógica, Conjuntos y Teoría de Gráficas

Lógica

2

Lógica Proposicional: Conceptos y Aplicaciones Básicas

3

Tablas de verdad y conectores lógicos: conjunción, disyunción y más

4

Construcción de Tablas de Verdad para Proposiciones Compuestas

5

Construcción de Tablas de Verdad para Proposiciones Lógicas

6

Tablas de Verdad y Análisis de Proposiciones Lógicas

7

Circuitos Lógicos: Representación y Función en Electrónica

8

Circuitos Lógicos para Proposiciones Compuestas

9

Tablas y Circuitos Lógicos: Ejercicios Prácticos

Teoría de conjuntos

10

Conjuntos: Definición, Pertenencia y Representación Matemática

11

Conjuntos: Nulo, Unitario y Universal y Operaciones Básicas

12

Representación Gráfica de Operaciones entre Conjuntos

13

Propiedades de los Conjuntos: Leyes de De Morgan y Representación Gráfica

14

Representación gráfica de las leyes de De Morgan

15

Operaciones y Propiedades de Conjuntos: Ejercicio Práctico Resuelto

16

Operaciones Básicas con Conjuntos y Problemas de Conjuntos

Teoría de grafos

17

Teoría de Gráficas: Conceptos y Aplicaciones Prácticas

18

Grado de Vértices y Conexiones en Gráficas Simples

19

Caminos y ciclos eulerianos en grafos: teoría y aplicación

20

Caminos y Ciclos Hamiltonianos en Grafos

21

Construcción de Matrices de Adyacencia para Representar Grafos

22

Representación de Grafos con Matriz de Incidencia

23

Matrices de Adyacencia en Grafos Dirigidos

24

Análisis de Caminos y Ciclos Eulerianos en Grafos

Árboles

25

Árboles y Tipos de Árboles en Matemáticas Discretas

26

Estructuras de Árboles en Programación y Jerarquías de Datos

27

Conceptos Básicos de Estructuras de Árboles en Informática

28

Árbol de Expansión Mínima: Conexión Óptima de Nodos

29

Tipos de Árboles Binarios y sus Características

30

Recorridos de Árboles: Preorden, Inorden y Posorden

31

Árboles Binarios para Expresiones Aritméticas

32

Transformación de Expresiones Aritméticas en Árboles Binarios

33

Árboles: Altura, Niveles y Recorridos Ordenados

Algoritmos

34

Algoritmo de Prim: Árbol de Expansión Mínimo en Grafos

35

Algoritmo de Dijkstra: Ruta Óptima y Coste Mínimo

36

Algoritmo de Kruskal

37

Algoritmo de Flury: Encontrar Ciclos Eulerianos en Grafos

38

Algoritmo de Flujo Máximo en Redes Dirigidas

39

Algoritmos de Grafos: Prim, Dijkstra, Kruskal y Fleury

Conclusiones

40

Repaso Final de Matemáticas Discretas: Lógica, Conjuntos y Algoritmos

No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Caminos y Ciclos Hamiltonianos en Grafos

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 33

Preguntas 5

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

  • 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.

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