Presentación Económica

Presentación del tema:

• 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

Teorema de Dirac

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

¿G?

¿n?

Ejemplos

Ejercicio!!!

¿cual es su origen?

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.

Propiedades del teorema de ore:

1) Un grafo debe de tener 3 o mas vertices.

2) La suma de los vertices no adyacentes deben dar igual al número de vertices total

Ejemplos:

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

Los criterios suficientes para que un grafo sea hamiltoniano:

• Teorema de Dirac
• Teorema de Ore
• Grafo completo

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.

Grafo completo:

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.

Gracias

Kahoot:

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 𝐺