GRAFOS HAMILTONIANOS

Identifique si el grafo es Hamiltoniano o semihamiltoniano o ninguno:

GRAFO SEMIHAMILTONIANO GRAFO SEMIHAMILTONIANO

Grafos NO Hamiltonianos
Grafos Hamiltonianos

Grafos Hamiltonianos
Grafos Hamiltonianos

CONDICIONES PARA QUE UN GRAFO SEA HAMILTONIANO

1. CONDICIONES SUFICIENTES PARA QUE UN GRAFO SEA HAMILTONIANO

Ejemplo 3.
El grafo es Hamiltoniano, según la
condición de Dirac?
Al verificar si el grafo G3, cumple con la
condición podemos concluir? δ = 2 y n= 9
(9/2=4) entonces, podemos decir que el
grafo G3 es o no Hamiltoniano? Que se
debe hacer para verificar si es o no
Hamiltoniano?

b. CONDICION: SI UN GRAFO G1 NO ES HAMILTONIANO POR LA CONDICION DE DIRAC,

PERO SE PUEDE ARREGLAR PARA OBTENER EL GRAFO G2 Y ESTE LO ES, ENTONCES G1
TAMBIEN ES HAMILTONIANO.

Sean dos vértices no adyacentes u,v que pertenecen al conjunto de vértices del grafo
G1, la arista(u,v) que no pertenece al conjunto de aristas del grafo G1 y la suma de los
grados de los vértices u y v es mayor o igual que el número de vértices del grafo G1, se
puede obtener otro grafo G2 que sea Hamiltoniano, entonces G1 también lo es.

Ejemplo 1.
δ = 2 y n= 6 (6/2=3) Entonces no cumple
con la condición de Dirac. Pero podemos
decir que el grafo no es Hamiltoniano?
Vamos a aplicar entonces la condición 2.
Convertimos el grafo G en el grafo G2,
agregando una arista desde el vértice que
no tiene grado 3!(el que no deja cumplir la
condición de Dirac)

Y obtenemos el grafo G2 con δ = 3 y n=

 6:(6/2=3) Entonces ahora cumple con la
condición de Dirac. Por lo tanto G2 es
Hamiltoniano y la condición dice que si
G2 es Hamiltoniano, entonces G1
también lo es!
(Ojo Revisar si G1 es hamiltoniano!.)

Ejemplo, encontrar la clausura del siguiente grafo.

Se inserta la primera
arista entre 2 vértices
no adyacentes g(v2)=4
+ g(v6)=2 cuya suma
de grados sea mayor o
igual que 6.

Se inserta la Se inserta la tercera

segunda arista entre 2 vértices
arista entre no adyacentes
2 vértices g(v5)=4 + g(v3)=3
no cuya suma de grados
adyacentes sea mayor o igual que
g(v5)=3 + 6.
g(v6)=3
cuya suma
de grados
sea mayor o
igual que 6.
Se inserta la Se inserta la quinta
cuarta arista entre 2 vértices
arista entre no adyacentes
2 vértices g(v1)=3 + g(v4)=4
no cuya suma de grados
adyacentes sea mayor o igual que
g(v3)=4 + 6.
g(v1)=2
cuya suma
de grados
sea mayor o
igual que 6.
 Se inserta la sexta arista entre 2 vértices no adyacentes
g(v1)=4 + g(v6)=4 cuya suma de grados sea mayor o igual que
6. En este caso se obtiene el grafo completo K6, en la sexta
inserción de la arista, ya no es posible adicionar ninguna otra
arista que cumpla la condición.(Ya están todas las posibles
aristas)
Siempre llegamos al grafo completo? No necesariamente, veamos
el siguiente ejemplo.

Encontrar la clausura del grafo G.

En este caso n=5 y ningún par de vértices cumple con la condición
de tener la suma de grados mayor o igual que 5, por consiguiente
la clausura es el mismo grafo.
En este caso es la mínima, en el anterior caso fue la máxima, es
decir puede haber cualquier clausura entre el grafo inicial y el
grafo completo, eso depende del grafo.

2. CONDICIONES NECESARIAS PARA QUE UN GRAFO SEA HAMILTONIANO.

Ejemplo1. Es hamiltoniano el siguiente

grafo?
El grafo tiene vértices con grados:
g(V1) = g(V3) = g(V5) =2
V5
g(V2) =g(v4)=3
Es decir todos sus vértices son de grado 2
o más pero el grafo no es Hamiltoniano.
Ejemplo 2. Es hamiltoniano el siguiente
grafo?
Grado de los vértices del grafo:
g(V2) = g(V3) = g(V4) = g(V5) =3
g(V1) =2 y g(v6)=4
Es decir todos sus vértices son de grado 2
o más entonces el grafo es Hamiltoniano.

Ejemplo 3. Es hamiltoniano el siguiente

grafo?
Al ver el grafo se observa que hay un
vértice , el v6 cuyo grado es 1, por
consiguiente de una vez podemos afirmar
que el grafo no es hamiltoniano, al no
cumplir con la condición de tener todos
sus vértices grado igual o mayor a 2.

a) Si un grafo es hamiltoniano y es bipartito entonces el número de vértices del

conjunto A debe ser igual al número de vértices del conjunto B de G.

Ejemplo1. Es hamiltoniano el siguiente

grafo?
El grafo es bipartito, se puede ver a simple
vista y el número de vértices de X es igual
al número de vértices de Y, entonces es
Hamiltoniano por la condición b, (3=3)
Ejemplo1. Es hamiltoniano el siguiente grafo?
El grafo es bipartito, se puede ver a simple
vista pero el número de vértices de X no es
igual al número de vértices de Y, entonces no
es Hamiltoniano por la condición b, (3 ≠5)

Ejercicio 1. Es hamiltoniano el siguiente

grafo?
Primero debemos verificar si el grafo es
bipartito, porque no se puede ver a simple
vista, para lo cual podemos usar el teorema
de etiquetas.(Es bipartito y X = Y, es decir
cumple con la condición b, pero ojo porque
hay dos vértices de grado 1 con lo cual no
cumple con la primera condición! Por lo
tanto NO es hamiltoniano!)

METODO PARA SABER SI UN GRAFO ES O NO HAMILTONIANO.

 Grafos hamiltonianos con vértice de grado 2
Ejemplo. Dado el siguiente grafo, determine si es hamiltoniano usando el método de
vértices de grado 2.

Siempre vamos a suponer que existe un ciclo Hamiltoniano

1.Oservamos cuales son los vertices de
grado 2.
En este caso el vertice v5 tiene grado 2,
entonces las aristas incidentes en el
(v2,v5) y (v5,v8) deben pertenecer al
ciclo que se esta re-construyendo.

El otro vertice de grado 2 es v7, por

consiguiente sus aristas incidentes deben
tambien formar parte del ciclo.
Ya no hay mas, entonces veamos si hay
que eliminar aristas y cuales serian y
porque.

Ahora obtenemos el siguiente grafo,

porque eliminamos las aristas (v1,v2),
(v2,v3) (v2,v8) del vertice v2.

Observemos que el vertice v1 y el v8

quedan con grado 2(al eliminar las aristas
que ya no se consideran) estos vertices
entonces deben formar parte del ciclo
hamiltoniano y las incorporamos a la
solucion, con lo cual obtenemos el nuevo
grafo.
 Ahora obtenemos el siguiente grafo, el
cual es evidentemente Hamiltoniano, ya
que se recorren todos los vertices sin que
se repitan y el vertice inicial es el mismo
que el vertice final.

Ejercicio. Muestre si el grafo G es hamiltoniano usando el método de vértices de grado 2.

1.Observamos cuales son los vertices de
grado 2.
En este caso el vertice v1 tiene grado 2,
entonces las aristas incidentes en el
(v1,v5) y (v1,v2) deben pertenecer al ciclo
que se esta re-construyendo.

El otro vertice de grado 2 es v4, por

consiguiente sus aristas incidentes (v2,v4)
y (v4,v7) deben tambien formar parte del
ciclo.

Y el otro vertice de grado 2 es v6, sus

aristas incidentes(v6,v5) y (v6,v7) deben
tambien formar parte del ciclo.
Hemos obtenido un subciclo, el cual tiene
necesariamente que hacer parte del ciclo
hamiltoniano mas grande. Entonces que
podemos concluir? El grafo G es
hamiltoniano o no y porque?
Ejercicios:
Determine si los siguientes grafos son o no hamiltonianos usando el método de los
vértices de grado dos (2).

No existen más vértices de

grado 2 , no hay más vértices
que eliminar por lo tanto
grafo no hamiltoniano

No es un grafo hamiltoniano
Ya que existen 2 subciclos
APLICACIONES DE LOS GRAFOS HAMILTONIANOS.
El problema del viajero, de peso minimo.
En el Problema del Agente Viajero - TSP (Travelling Salesman Problem), el objetivo es
encontrar un recorrido completo que conecte todos los nodos de una red, visitándolos tan
solo una vez y volviendo al punto de partida, y que además minimice la distancia total de
la ruta.
Este tipo de problemas tiene gran aplicación en el ámbito de la logística y distribución. El
problema del agente viajero tiene una variación importante, y esta depende de que las
distancias entre un nodo y otro sean simétricas o no, es decir, que la distancia entre A y B
sea igual a la distancia entre B y A. En la práctica es muy poco probable que así sea.

La cantidad de rutas posibles en una red(Es decir que todos los puntos están conectados)
está determinada por la ecuación:
(n-1)!

Es decir que en una red de 5 nodos la cantidad de rutas probables es igual a (5-1)! = 24, y
a medida que el número de nodos aumente la cantidad de rutas posibles crece
factorialmente. En el caso de que el problema sea simétrico la cantidad de rutas posibles
se reduce a la mitad, es decir:
( (n-1)! ) / 2

Suponga que hay un vendedor que desea

visitar los municipios representados en el
siguiente grafo.
1. Inicia el recorrido en el Tambo y debe
terminar el el Tambo.
2. Escogemos la población más cercana al
tambo, en este caso cajibio(18), las demás
están más lejos.
3.Formamos el ciclo Tambo-Cajibio-Tambo.
TCT=TC+CT  ciclo de longitud 2 con costo
k1 de k1=18+18=36
4. Como hay más poblaciones (Purace,
Timbio,La Sierra), debemos escoger cual es la
población mas cercana a Cajibio, que es
Purace.

Debemos insertar Purace en el ciclo, en

este caso no interesa si va antes o después
de Cajibio porque son solo dos poblaciones,
con lo cual el ciclo nos asi:

Tambo- Cajibio- Purace-Tambo o asi:

Tambo- Purace- Cajibio –Tambo.
Al ciclo de longitud 2 con costo de 36, le
debemos incrementar el costo de INCLUIR
entre T y C la nueva población asi: TPC =
TP-PC-TC=30+13-18=25(k2) o
CPT=CP+PT-CT=13+30-18=25.(k2)
Al costo k1 le sumamos el costo de k2:
K=k1+k2=36+25=61
Nuevamente debemos escoger una
población más cercana a Purace, en este
caso La sierra(15)
Debemos insertar La Sierra en el ciclo, en
este caso sí nos interesa, si va antes o
después de alguna otra población, con lo
cual al ciclo que llevamos T-C-P-T debemos
ver donde se le inserta la nueva población,
quedando así las posibles inserciones:

a) T-LS-C=TLS+LSC-TC=28+25-18=35

b) C-LS-P=CLS+LSP-CP=25+15-13=27

c) P-LS-T=PLS+LST-PT=15+28-30=13
(k3=menor costo incremental-se escoge)
Al ciclo de longitud 3 con costo de 61, le
debemos incrementar el menor costo de
incluir entre P y T la nueva población asi:
Al costo k2 le sumamos el costo de k3, asi:
K=k2+k3=61+13=74
Quedando el ciclo: T-C-P-LS-T
Nuevamente debemos escoger una
población más cercana a Purace, en este
caso Timbio(11), la última que queda.

Debemos ver donde insertar Timbio en el

ciclo, T-C-P-LS-T, quedando así las
posibles inserciones:

 T-Ti-C=TTi+TiC-TC=24+23-18=29

 C-Ti -P=CTi + TiP - CP=23+18-

13=28

 P-Ti-LS=PTi+TiLS-PLS=18+11-
15=14

 LS-Ti-T=LSTi+TiT-LSTi=11+24-
28=7 (k4=menor costo incremental-se
escoge) Al ciclo de longitud 4 con costo de
74, le debemos incrementar el costo de
INCLUIR entre LS y T, la nueva población
asi:
Al costo k3 le sumamos el costo de k4, asi:
K=k3+k4=74+7=81
Quedando el ciclo: T-C-P-LS-Ti-T, lo que
nos da un costo total de:
 18+13+15+11+24=81, que es el mismo
que obtuvimos al calcular los costos
incrementales.

Así obtenemos finalmente el ciclo Hamiltoniano , con menor costo total, para el
problema del viajero. Es p posible que existiera otra ruta de menor costo, pero esta es
una buena opción.
( Verificar mediante el método de fuerza bruta, ( n - 1)! todos los caminos Hamiltonianos
posibles para conocer si existe una mejor solución.) (5-1)! =4!=24 Caminos
=
(FASDASAD

Ejercicios:
Resolver mediante el método del vecino más cercano los siguientes ejercicios. Use
el método de fuerza bruta en los ejercicios (a) y (b)
 b)Vértice Inicial A
(5-1)! = 4! = 24 caminos existentes

a) Encontrar la ruta con el menor

costo.
ACA =AC +CA K1 = 1+1 = 2
Vértice Inicial A.
(4-1)! = 3! = 6 caminos existentes

ACA = AEC O CEA

 AE +EC -AC =25 +2-1 =26K2
ACA = AC+CA =  CE +EA -CA = 2+25-1 =26K2
K1 =7+7 = 14

ACEBA = >ABC *CBE *EBA

 ABC =AB+BC-AC=2+18-1=19
ACA => ADC O CDA
 CBE =CB+BE-CE =18+5-2 =21
 ADC = AD +DC -AD= 8 +4 -7
 EBA =EB+BA-EA =5+2(-25)=-18K3
=5K2
 CDA = CD +DA -CA = 4+8-7 = K=K2+K3= 26+(-18)=8
5K2
K = K1 + K2 = 14+5 =19

ACEBA = > ADC CDE EDB BDA

 ADC= AD +DC -AC=10+20-1=19
ACDA => ABC 0 CBD O DBA
 CDE= CD+DE-CE =20+8-2=26
 ABC = AB + BC -AC = 9 +10-7
 EDB=ED+DB-EB =8+5-5=8 K4
=12K3
 BDA=BD+DA-BA =5+10-2=13
 CBD = CB +BD -CD =10+15-
K=K3+K4=8+8=16
4=21
 DBA = DB +BA -DA =15+9-
8=16
K =K2 +K3 =19+12 =31
Costo Total Mínimo =31
c)Vértice inicial B  Vértice inicial 1
(5-1)! = 4! = 24 caminos existentes (5-1)! = 4! = 24 caminos existentes

131 = 13+31=238+238 =476k1

BFB = BF+FB =7+7=14K1

131= 153 351

 153 = 15+53-13=266+240-
238=268K2
 351 = 35+51-31=240+266-
BFB = BAF 0 FAB 238=268K2
 BAF = BA+AF-BF=8+4-7=5 K2 K=K1+K2=476+268 = 744
 FAB = FA+AB-FB=4+8-7=5 K2
K=K1+K2=14+5=19
 1351 = 143 345 541
 143= 14+43-13=304+348-238=414K3
 345= 34+45-35=348+398-240=506
BFAB = BJF FJA AJB  541= 54+41-51=398+304-266=436
 BJF= BJ+JF-BF =9+10-7=12 K3 K =K2 +K3=744+414=1158
 FJA= FJ+JA-FA =10+15-4=21
 AJB= AJ+JB-AB=15+9-8=16
K= K2+K3 =19+16=35

13541 = 123 325 524 421

 123=12+23-13=370+242-238=374
 325=32+25-35=242+400-240=402
 524=52+24-54=100+300-398=2K4
 421=42+21-41=300+370-304=366
K=K3+K4=1158+2 =1160
BFAJB = BEF FEA AEJ JEB
Costo Total Mínimo =1160
 BEF = BE+EF-BF=20+11-7=24
 FEA = FE+EA-FA=11+17-4=24
 JEB = JE+EB-JB =5+20-9=
16K4
K=K3+K4=35+16=51
Costo Total Mínimo =51