CAMINOS Y CICLOS
EURELIANOS Y
HAMILTONIANOS
MATEMÁTICA DISCRETA
1
1
1
CAMINO Y CICLO DE HAMILTON
CAMINO DE HAMILTON . Es un camino que pasa por todos los vértices del grafo
exactamente una vez. Si el camino es cerrado es un CICLO DE HAMILTON.
a5 a6
a1 a2
a4
a5
a3
a4 a3
a2
a1
a1, a2, a5,a3, a4 a1, a3, a2, a6, a4, a5, a1
G. SEMIHAMILTONIANO G.HAMILTONIANO
a1
a2
a3 a5
a6
a4
NO ES HAMILTONIANO
NO ES SEMIHAMILTONIANO
TEOREMAS
El estudio de las propiedades de Hamilton es más compleja que
las propiedades de Euler.
TEOREMA DE DIRAC
TEOREMA DE ORE
TEOREMA DE RÉDEI
Teorema de DIRAC Si n ≥3 y gr(v) ≥ para cada vértice v ,entonces el grafo
contiene un ciclo hamiltoniano. Pero el teorema de Dirac no es necesaria
a b 1 2
c
6 3
f
d 4
e 5
.
¿COMO IDENTIFICAR UN GRAFO DE
HAMILTON?
Teorema de Rédei
(Lászio Rédei-Hungria-1900)
“Un grafo es hamiltoniano si la suma de grados de dos vértices
es siempre mayor o igual a (n-1)”
n: Número de vértices , donde n≥ 2
G(v):Grado del vértice “v”
https://www.youtube.com/watch?v=YG2BiYKVeXk
EJERCICIO 02
• Identifique si el gráfico es tiene un ciclo hamiltoniano:
E
A C
D
SOLUCIÓN
SEGÚN EL TEOREMA DE RÉDEI
1. n=5;cumple que n≥ 2 B
2. Entonces: n-1=4
3. Donde:G(V1)+G(v2) ≥ 4
Escogemos los grados más
bajos para la verificación: E
A C
4. G(B)+G(D) ≥ 4
5. 3+3≥ 4 6≥ 4
Cumple el teorema, culmina en
el punto inicial.
El gráfico si e un ciclo ce D
Hamilton
SOLUCIÓN
CAMINO Y CICLO EURELIANO
CAMINO DE EULER . Es un camino que pasa por todas las aristas del grafo exactamente una
vez. Tomando en cuenta que no importa la repetición de vértices mientras que no se repitan las
aristas. Si el camino es cerrado es un CICLO DE EULER
1 7 5
6 1
2
6
3 4 5 2 3 4
CAMINO DE EULER CICLO DE EULER
TEOREMA 1
Un grafo es euleriano si y solo si es conexa y todos sus vértices es de grado
par.
INICIA FINALIZA
En cualquier punto En el punto que inicio
TEOREMA 02
Un grafo admite un camino aeureliano si y solo si es conexa y tiene a lo más 2 vértices de
grado impar.
INICIA FINALIZA
En cualquier punto En el otro impar
impar
TEOREMA 03
• Un grafo no admite un camino Euleriano si tiene más de dos vértices de grado
impar
Si la cantidad de vértices de grado impar es mayor a dos, ya no se puede hacer el
grafo de un de un solo trazo.(El grafo no es Euleriano )
Nota: En cualquier grafo cantidad de vértices de grado impar es par
Los 7 Puentes de Konisberg
Los 7 Puentes de Konisberg
• Se puede pasar por todos los puentes sin repetir ninguno
TEORIA DEL RECORRIDO MÍNIMO
¿Cuál es la mínima distancia?
4
4
4
4
4
5
TEORIA DEL RECORRIDO MÍNIMO
¿Cuál es la mínima distancia?
6 6
4 6
2 o 2
¿Cuál es la mínima distancia?
2
Nota: Los trazos a repetir van de impar a impar y deben ser
en lo posible los de menor distancia
2
n ° de vertices de grado impar −2
M í nimo n ° de trazos a repetir =
2
8 8
6
Determina la mínima distancia inicia en A y termina
en A
B 5 A
C D
4 F G
E
H
https://www.youtube.com/watch?v=Dx_JC0qJEK0
• https://www.youtube.com/watch?v=TEzSB1h4bHc
https://www.youtube.com/watch?v=BZxs5wouh8g
El s
https://www.youtube.com/watch?v=BZxs5wouh8g
Problemas
Dado el grafo
1.¿Admite un recorrido eureliano?.
2.¿Cual es la mínima cantidad de arista que hay agregar para que G sea eureliano? .
El grafo obtenido muestra un circuito eureliano
3. ¿El grafo G es hamiltoniano?
V1 V2 V3
V4 V5 V6
V7
V8 V9
V1 V2 V3
V4
• gr(V1)=2 V5 V6
• gr(V2)=4
• gr(V3)=3 V7
V8 V9
• gr(V4)=4
Dado el grafo G
• gr(V5)=6 1.¿Admite un recorrido eureliano?
El grafo G si admite un recorrido eureliano 75874 568963524123
• gr(V6)=4
• gr(V7)=3
• gr(V8)=4
• gr(V9)=9
Dado el grafo G
2.¿Cual es la mínima cantidad de arista que hay agregar para que G sea eureliano? .
El grafo obtenido muestra un circuito eureliano.
Si agregamos una arista entre V3 y V7
el gr(V3)=4 gr(V7)=4 G1 es par →G1 es eureliano.
142547369875865321
V1 V2 V3
V4 V5 V6
V7
V8 V9
Problemas
Dado el grafo
¿El grafo G es hamiltoniano?
Hay un ciclo hamiltoniano
1457896321 → G es hamiltoniano.
V1 V2 V3
V4 V5 V6
V7
V8 V9
¿El grafo G es euleriano?
a b
d c
f
G dabcdecfd (circuito eureliano) ∴ G es un grafo euleriano
2
5 6
10
1 3
8 7
