prepare to be emazed

Creating your website,

it will only take a few seconds!

Polygon

1823010673
Caminos Eulerianos y Hamiltonianos 
Integrantes :
* Huancas Leuyac Anselmo Junior
* Flores Herrera Julio Christian
* Mendoza Rodriguez Ruth Jazmin
* Serna Malca Luis Alejandro
Contenido
Caminos Eulerianos
Caminos Hamiltonianos 
Diferencias 
Problemas de Flujo Máximo  
Algoritmo de Ford Fulkerson
1
2
3
4
5

Caminos Eulerianos
Un camino euleriano es un grafo o multigrafo en la cual se puede recorrer cada arista una y solo una vez.
Postulados de Euler
1° POSTULADO
Toda figura admite un recorrido euleriano, si todos sus puntos son pares empezando en cualquier punto; pero terminando en el mismo punto.
Toda figura admite un recorrido euleriano, si presenta a lo más dos puntos impares, debiendo empezar en uno de los puntos impares y terminando en otro
2° POSTULADO
3° POSTULADO
Si una figura presenta más de 2 puntos impares, entonces jamás se podrá realizar de un solo trazo.
Ejemplo
Determine si en los grafos (a) y (b) se puede realizar el recorrido Euleriano.
En el grafo (a): Vemos cuántas aristas tiene cada vértice. Cada vértice tiene 4 aristas. Entonces en el grafo (a) se puede realizar un recorrido Euleriano
En el grafo (b): Vemos cuántas aristas tiene cada vértice. Tenemos 2 vértices que tienen 3 aristas y tenemos 4 vértices que tienen 4 aristas. Entonces en el grafo (b) se puede realizar un recorrido Euleriano
Caminos 
Hamiltonianos
Vi
Vf
Vi
Vf
Un camino hamiltoniano en un grafo es un camino
que visita todos los vértices del grafo una sola vez
Dado un grafo G = < N , A > simple con “n” nodos, con un número de nodos |N| ≥ 3. Si para todo v que pertenece a N se verifica que g(v) ≥ n / 2 , entonces existe al menos un circuito hamiltoniano.
Dado un grafo G = < N , A > simple con “n” nodos, cuyo número de nodos sea |N| ≥ 3. Si se verifica que g(v) + g(w) ≥ n ,Para todo  v, w que pertenece a N con v ≠ w y no adyacentes, entonces el grafo tiene, al menos, un circuito hamiltoniano.
¿Cómo identificar un grafo hamiltoniano?

Aunque no se conocen condiciones necesarias y suficientes útiles para la existencia de circuitos hamiltonianos, se han encontrado bastantes condiciones suficientes además de ciertas propiedades que se puede utilizar para demostrar que un grafo no contiene ningún circuito hamiltoniano.

Teorema 
de Dirac
Teorema 
de Ore
1. Todo grafo G completo con n >= 3 posee un circuito hamiltoniano. 

2. Todo grafo con un punto de corte no es hamiltoniano. 

3. Si G no es conexo no posee ningún circuito hamiltoniano. 

4. Un camino hamiltoniano contiene “n-1” arcos.
 5. Un circuito hamiltoniano contiene n arcos.

6. Si G posee un circuito hamiltoniano todo nodo del grafo debe tener un Grado >= 2. 


; ;

emaze