Want to make creations as awesome as this one?

Transcript

    • Yasuan Smith Caicedoma Martinez
    • Fabian Stiven Murillo Duarte
    • Hansel Alfonso Mendoza Cordoba
  • Teorema de dirac
  • Teorema de Ore
  • Criterios suficientes para que un grafo sea hamiltoniano

Presentación del tema:

¿n?

¿G?

Si 𝐺 es un grafo simple con 𝑛 vértices ( 𝑛 ≥ 3) y el grado de cada vértice es al menos , entonces 𝐺 contiene un ciclo hamiltoniano.

Teorema de Dirac

Ejercicio!!!

Ejemplos

el teorema de ore fue creado en el año 1960 por el matematico noruego Øystein Ore.Es un sistema que proporciona una condicion, para probar si un grafo sea hamiltoniano.

¿cual es su origen?

2) La suma de los vertices no adyacentes deben dar igual al número de vertices total
1) Un grafo debe de tener 3 o mas vertices.

Propiedades del teorema de ore:

Ejemplos:

Importancia: Determinar si un grafo es hamiltoniano es un problema complejo en teoría de grafos. Existen ciertos criterios que, si se cumplen, garantizan que el grafo tiene un ciclo hamiltoniano.

  • Teorema de Dirac
  • Teorema de Ore
  • Grafo completo

Los criterios suficientes para que un grafo sea hamiltoniano:

Un grafo hamiltoniano se define como un grafo que incluye un ciclo hamiltoniano. Este ciclo es aquel que visita cada vértice del grafo una única vez y retorna al punto de inicio.

Criterios para que un grafo sea hamiltoniano

Un grafo completo es un grafo en el que todos los vértices están conectados entre sí por una arista. Notación: Se representa como 𝐾 𝑛 donde 𝑛 es el número de vértices.

Grafo completo:

Kahoot:

Gracias

El texto representa el número total de vértices en el grafo G. Por ejemplo, si se tiene un grafo con 6 vértices, entonces n = 6.

La expresión mencionada representa la mitad del número total de vértices en el grafo G. En el contexto del Teorema de Dirac, esta formulación establece un límite para el grado de cada vértice, es decir, determina la cantidad de aristas que debe poseer cada vértice.

Es el grafo del que estamos hablando. En teoría de grafos, solemos denotar a un grafo con una letra como 𝐺