Guia 6 - Conexión entre grafo

Vista previa del material en texto

CONEXIÓN ENTRE GRAFOS 
- 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
DESARROLLO 
 
1. Conexión en grafos: Es una sucesión de vértices y aristas que se desplaza de un vértice i a un 
Vértice j 
 
1.1 UNA RUTA: una ruta en un grafo G es una sucesión finita no nula 
 
R = V0A1V1A2V2…Ak-1 Vk-1 Ak Vk 
 
Cuyos términos son alternadamente vértices y aristas, tal que toda arista de R tiene como sus 
extremos el vértice precedente y el siguiente de la sucesión en estas condiciones diremos que R 
es una ruta de V0 A Vk, lo que denotamos por R –(V0, Vk) donde: 
 V0 se llama vértice inicial 
 Vk se llama vértice terminal de R 
 Los vértices V1 hasta Vk-1 se llama vértices intermedios 
 El número K se llama longitud de R y la denotamos por I (R) = K 
 
Ejemplo: Seleccionaremos la ruta de materia a Sincelejo R1-(V0, V11) 
 
 
R1 = (V0 – a1 – V1 – a15 – V15 – a22 – V22 – a23 – V23 – a24 – V7 – a8 – V8 – a9 – V9 – a25 - 
V19 – a19 – V18 – a18 – V17 – a17 – V16 – a16 - V15 – a20 – V20 – a21 – V21 – a26 – V18 – 
a19 – V19 – a25 – V9 – a10 – V10 – a11 – V11) L(R) = 19 
 
0= Montería 
1= Cereté 
7= Tuchin 
8= San Andres de 
Sotavento 
9= Chinú 
10= Sampues 
11= Sincelejo 
15= Ciénaga de Oro 
16= Aguas Vivas 
17= La Ye 
18= Sahagún 
19= Arrimadero 
20= No hay como dios 
21= La trampa 
22=El coco 
23 = chima 
 
1.2. UNA CADENA: una ruta R – (V0 – Vk) de un grafo G en el cual todas sus aristas son 
diferentes, se llama una cadena C – (V0 – Vk) de grafo G. 
 
 
 
Ejemplo: C – (V0, V7) 
 
 
 
C= (V0 – a1 – V1 – a15 – V15 – a20 – V20 – a21 – V21- a26 – V18 – a18 – V17 – a17 – V16 – 
a16 - V15 – a22 - V22 – a29 – V23 – a24 – V7) L(C) = 11 
 
 
 
 
 
 
 
 
 
 
 
 
 
0= Montería 
1= Cereté 
7= Tuchin 
15= Ciénaga de Oro 
16= Aguas Vivas 
17= La Ye 
18= Sahagún 
19= Arrimadero 
20= No hay como dios 
21= La trampa 
22=El coco 
23 = chima 
 
 
1.3 UNA CADENA SIMPLE: es una ruta donde sus vértices y las aristas son diferentes 
 
Ejemplo: CS – (V1, V9) 
 
 
 
 
 
CS= (V1 – a15 – V15 – a16 – V16 – a17 – V17 – a18 – V18 – a19 – V19 – a25 - V9) L(CS) = 6 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1= Cereté 
9= Chinú 
15= Ciénaga de Oro 
16= Aguas Vivas 
17= La Ye 
18= Sahagún 
19= Arrimadero 
 
 
1.4 UNA RUTA CERRADA: es cuando su vértice inicial y su vértice terminal coinciden V0 = Vn, 
se denomina RC. 
 
Ejemplo: RC – (V1, V1) 
 
V0 = Cerete 
Vk = Cerete 
V0 = Vk 
 
 
 
 
RC = (V1 – a15 – V15 – a22 - V22 – a23 – V23 – a24 – V7 – a8 – V8 – a9 – V9 – a25 - V19 – 
a19 – V18 - a26 – V21 – a21 – V20 – a20 - V15 – a22 - V22 – a23 – V23 – a24 – V7 – a7 - V6 – 
a6 – V5 – a5 – V4 – a4 – V3 – a3 – V2 – a2 - V1) L(RC) = 20 
 
 
 
 
 
 
 
 
1.5 UN CICLO: Cuando la ruta (camino) es cerrada y es una cadena se llama ciclo 
1= Cereté 
2= San Pelayo 
3= El Carito 
4= La Palma 
5= Lorica 
6= Purísima 
7= Tuchin 
8= San Andres de 
Sotavento 
9= Chinú 
15= Ciénaga de Oro 
16= Aguas Vivas 
17= La Ye 
18= Sahagún 
19= Arrimadero 
22=El coco 
23 = chima 
 
 
Ejemplo: 
 
 
 
 
 
 
CI = ( V1 – a15 – V15 – a20 – V20 – a21 – V21- a26 – V18 – a18 – V17 – a17 – V16 – a16 - V15 
– a22 - V22 – a23 – V23 – a24 – V7 – a7 - V6 – a6 – V5 – a5 – V4 – a4 – V3 – a3 – V2 – a2- V1) 
L(CI) = 16 
 
 
 
 
 
 
 
 
 
 
 
 
 
1= Cereté 
2= San Pelayo 
3= El Carito 
4= La Palma 
5= Lorica 
6= Purísima 
7= Tuchin 
15= Ciénaga de Oro 
16= Aguas Vivas 
17= La Ye 
18= Sahagún 
19= Arrimadero 
20= No hay como dios 
21= La trampa 
22=El coco 
23 = chima 
 
1.6 UN CICLO SIMPLE: si la ruta cerrada es una cadena simple, a esto se le llama ciclo simple 
 
Ejemplo: 
 
 
 
 
CIS=( V1 – a2 – V2 – a3 – V3 – a4 – V4 - a5 – V5 – a6 – V6 – a7 – V7 – a8 - V8 – a9 – V9 – a25 – 
V19 – a19 – V18 –a18 – V17 – a17 – V16 – a16 – V15 – a15 -V1) I(RC) = 14 
 
 
 
 
 
 
 
 
 
 
 
 
 
1= Cereté 
2= San Pelayo 
3= El Carito 
4= La Palma 
5= Lorica 
6= Purísima 
7= Tuchin 
8= San Andres de Sotavento 
9= Chinú 
 
15= Ciénaga de 
Oro 
16= Aguas Vivas 
17= La Ye 
18= Sahagún 
19= Arrimadero 
2. Grafo conexo y no conexos: un grafo G se llama conexo si dados dos vértices cuales quiera Vi 
y Vj de G, existe una cadena C – (Vi – Vj). En el caso contrario el grafo se llama no conexo, Un 
grafo G no-conexo está formado por dos o más grafos conexos. Cada uno de estos grafos 
conexos se llama una COMPONENTE CONEXA del grafo G. 
 
Ejemplo: 
 
Grafo conexo del grafo G: 
 
 Grafo no conexo del grafo G: 
 
0=Montería 
1= Cereté 
2= San Pelayo 
3= El Carito 
4= La Palma 
5= Lorica 
6= Purísima 
7= Tuchin 
8= San Andres de Sotavento 
9= Chinú 
 
 
 
15= Ciénaga de 
Oro 
16= Aguas Vivas 
17= La Ye 
18= Sahagún 
19= Arrimadero 
 
0=Montería 
1= Cereté 
2= San Pelayo 
3= El Carito 
4= La Palma 
5= Lorica 
7= Tuchin 
8= San Andres de Sotavento 
9= Chinú 
10= Sampues 
11= Sincelejo 
 
 
19= Arrimadero 
 
3. DISTANCIA: En un grafo conexo G, la distancia d (V1 , Vj ) entre dos de sus vértices V1 y Vj 
es la longitud de la cadena simple más corta entre ellos, es decir, d ( V1 , Vj ) = min (CS) donde 
CS - ( V1 , Vj ). 
 
Ejemplo: 
 
 
 
CS1 = (V0 – a1 - V1 – a2 – V2 – a3 – V3 – a4 - V4 - a5 – V5 – a6 – V6 – a7 – V7 – a8 – V8 – a9 – 
V9 – a10 – V10 – a11 - V11), longitud = 11 
 
CS2 = (V0 – a1 - V1 – a2 – V2 – a3 – V3 – a4 - V4 - a5 – V5 – a12 – V12 – a13 – V13 – a14 – V14 
– a27 - V11), longitud = 9 
 
CS3 = (V0 – a1 - V1 – a15 – V15 – a16 – V16 – a17 – V17 – a18 – V18 – a19 – V19 – a25 - 9 – 
a10 – 10 – a11 - 11), longitud=9 
 
d (V0, V11) = 9; la distancia más corta seria CS2 y CS3 
 
0= Montería 
1= Cereté 
2= San Pelayo 
3= El Carito 
4= La Palma 
5= Lorica 
6= Purísima 
7= Tuchin 
8= San Andres de Sotavento 
9= Chinú 
10= Sampues 
11= Sincelejo 
12= San Antero 
13= Santiago de Tolú 
14= Tolú Viejo 
 
15= Ciénaga de 
Oro 
16= Aguas Vivas 
17= La Ye 
18= Sahagún 
19= Arrimadero 
 
3.1 MÉTRICA: la distancia entre dos vértices de un grafo conexo G, puede ser considerada como 
una función que asigna a cada para de vértices del grafo G un numero entero no negativo. Esta 
función así definida satisface las condiciones 
1. La distancia entre Vi y Vj es mayor que cero, y distancia entre Vi y Vj es igual a cero si y 
solo si, Vi = Vj. 
2. Distancia entre Vi y Vj es igual a la distancia entre Vj y Vi 
3. Distancia entre Vi y Vj es igual a la distancia entre Vi y Vk mas Vk y Vj para algún vértice 
Vk 
La función que satisface estas tres propiedades se llama métrica, por tanto, la distancia entre los 
vértices de un grafo es una métrica 
 
Ejemplo: 
 
 
 
 
 
 
0= Montería 
1= Cereté 
2= San Pelayo 
3= El Carito 
4= La Palma 
5= Lorica 
6= Purísima 
7= Tuchin 
8= San Andres de Sotavento 
9= Chinú 
10= Sampues 
11= Sincelejo 
12= San Antero 
13= Santiago de Tolú 
14= Tolú Viejo 
 
15= Ciénaga de 
Oro 
16= Aguas Vivas 
17= La Ye 
18= Sahagún 
19= Arrimadero 
CS - ( V0 , V11 ) 
 
CS1 = (V0 – a1 - V1 – a2 – V2 – a3 – V3 – a4 - V4 – a5 – V5 – a12 – V12 – a13 – V13 – a14 – V14 
– a27 - V11), longitud = 9 
 
Distancia= 9; La distancia entre Vi y Vj es mayor que cero 
 
CS2 = (V11 – a27 – V14 – a14 – V13 – a13 – V12 – a12 – V5 – a5 – V4 – a4 – V3 – a3 – V2 – a2 
– V1 – a1 - V0), longitud=9 
 
Distancia = 9; Distancia entre Vi y Vj es igual a la distancia entre Vj y Vi 
 
Vk= V5 
 
CS3 = (V0 – a1 - V1 – a2 – V2 – a3 – V3 – a4 - V4 – a5 – V5) longitud = 5 
Distancia = 5 
 
CS4 = (V5 – a12 – V12 – a13 – V13 – a14 – V14 – a27 - V11), longitud = 4 
Distancia = 4 
 
Distancia (V0, V11) = Distancia (V0, V5) + Distancia(V5,V11) 
Distancia (V0, V11) = 5 + 4 
 
9=9 
La métrica = 9 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3.2 EXCENTRICIDAD: sea G un grafo conexo y v un vértice de G, la excentricidad de V, E (v) es 
la distancia que hay del vértice V al vértice más lejano del grafo 
 
E (v) = Max. D (V, VI) donde VI pertenece a V (G) 
 
Ejemplo: Del grafo anterior calcularemos la excentricidad en cada uno de sus vérticesE(V0); 
D (V0, V0) = 0 D (V0, V11) = 9 
D (V0, V1) = 1 D (V0, V12) = 6 
D (V0, V2) = 2 D (V0, V13) = 7 
D (V0, V3) = 3 D (V0, V14) = 8 
D (V0, V4) = 4 D (V0, V15) = 2 
D (V0, V5) = 5 D (V0, V16) = 3 
D (V0, V6) = 6 D (V0, V17) = 4 
D (V0, V7) = 7 D (V0, V18) = 5 
D (V0, V8) = 6 D (V0, V19) = 6 
D (V0, V9) = 7 E (V0) = 9 
D (V0, V10) = 8 
 
E(V1); 
D (V1, V0) = 1 D (V1, V11) = 8 
D (V1, V1) = 0 D (V1, V12) = 5 
D (V1, V2) = 1 D (V1, V13) = 6 
D (V1, V3) = 2 D (V1, V14) = 7 
D (V1, V4) = 3 D (V1, V15) = 1 
D (V1, V5) = 4 D (V1, V16) = 2 
D (V1, V6) = 5 D (V1, V17) = 3 
D (V1, V7) = 6 D (V1, V18) = 4 
D (V1, V8) = 7 D (V1, V19) = 5 
D (V1, V9) = 6 E (V1) = 8 
D (V1, V10) = 7 
 
 
 
 
 
 
 
 
 
 
E(V2); 
D (V2, V0) = 2 D (V2, V11) = 7 
D (V2, V1) = 1 D (V2, V12) = 4 
D (V2, V2) = 0 D (V2, V13) = 5 
D (V2, V3) = 2 D (V2, V14) = 6 
D (V2, V4) = 3 D (V2, V15) = 2 
D (V2, V5) = 4 D (V2, V16) = 3 
D (V2, V6) = 5 D (V2, V17) = 4 
D (V2, V7) = 6 D (V2, V18) = 5 
D (V2, V8) = 7 D (V2, V19) = 6 
D (V2, V9) = 8 E (v2) = 8 
D (V2, V10) = 8 
 
E(V3); 
D (V3, V0) = 3 D (V3, V11) = 6 
D (V3, V1) = 2 D (V3, V12) = 3 
D (V3, V2) = 1 D (V3, V13) = 4 
D (V3, V3) = 0 D (V3, V14) = 5 
D (V3, V4) = 1 D (V3, V15) = 3 
D (V3, V5) = 2 D (V3, V16) = 4 
D (V3, V6) = 3 D (V3, V17) = 5 
D (V3, V7) = 4 D (V3, V18) = 6 
D (V3, V8) = 5 D (V3, V19) = 7 
D (V3, V9) = 6 E (v3) = 7 
D (V3, V10) = 7 
 
E(V4); 
D (V4, V0) = 4 D (V4, V11) = 5 
D (V4, V1) = 3 D (V4, V12) = 2 
D (V4, V2) = 2 D (V4, V13) = 3 
D (V4, V3) = 1 D (V4, V14) = 4 
D (V4, V4) = 0 D (V4, V15) = 4 
D (V4, V5) = 1 D (V4, V16) = 5 
D (V4, V6) = 2 D (V4, V17) = 6 
D (V4, V7) = 3 D (V4, V18) = 7 
D (V4, V8) = 4 D (V4, V19) = 6 
D (V4, V9) = 5 E (v4) = 6 
D (V4, V10) = 6 
 
 
 
 
E(V5); 
D (V5, V0) = 5 D (V5, V11) = 4 
D (V5, V1) = 4 D (V5, V12) = 1 
D (V5, V2) = 3 D (V5, V13) = 2 
D (V5, V3) = 2 D (V5, V14) = 3 
D (V5, V4) = 1 D (V5, V15) = 5 
D (V5, V5) = 0 D (V5, V16) = 6 
D (V5, V6) = 1 D (V5, V17) = 7 
D (V5, V7) = 2 D (V5, V18) = 6 
D (V5, V8) = 3 D (V5, V19) = 7 
D (V5, V9) = 4 E (v5) = 7 
D (V5, V10) = 5 
 
E(V6); 
D (V6, V0) = 6 D (V6, V11) = 5 
D (V6, V1) = 5 D (V6, V12) = 2 
D (V6, V2) = 4 D (V6, V13) = 3 
D (V6, V3) = 3 D (V6, V14) = 4 
D (V6, V4) = 2 D (V6, V15) = 6 
D (V6, V5) = 1 D (V6, V16) = 7 
D (V6, V6) = 0 D (V6, V17) = 6 
D (V6, V7) = 1 D (V6, V18) = 5 
D (V6, V8) = 2 D (V6, V19) = 4 
D (V6, V9) = 3 E (v6) = 7 
D (V6, V10) = 4 
 
E(V7); 
D (V7, V0) = 7 D (V7, V11) = 4 
D (V7, V1) = 6 D (V7, V12) = 3 
D (V7, V2) = 5 D (V7, V13) = 4 
D (V7, V3) = 4 D (V7, V14) = 5 
D (V7, V4) = 3 D (V7, V15) = 7 
D (V7, V5) = 2 D (V7, V16) = 6 
D (V7, V6) = 1 D (V7, V17) = 5 
D (V7, V7) = 0 D (V7, V18) = 4 
D (V7, V8) = 1 D (V7, V19) = 3 
D (V7, V9) = 2 E (v7) = 7 
D (V7, V10) = 3 
 
 
 
 
 
E(V8); 
D (V8, V0) = 6 D (V8, V11) = 3 
D (V8, V1) = 7 D (V8, V12) = 4 
D (V8, V2) = 6 D (V8, V13) = 5 
D (V8, V3) = 5 D (V8, V14) = 4 
D (V8, V4) = 4 D (V8, V15) = 6 
D (V8, V5) = 3 D (V8, V16) = 5 
D (V8, V6) = 2 D (V8, V17) = 4 
D (V8, V7) = 1 D (V8, V18) = 3 
D (V8, V8) = 0 D (V8, V19) = 2 
D (V8, V9) = 1 E (v8) = 7 
D (V8, V10) = 2 
 
E(V9); 
D (V9, V0) = 7 D (V9, V11) = 2 
D (V9, V1) = 6 D (V9, V12) = 5 
D (V9, V2) = 7 D (V9, V13) = 4 
D (V9, V3) = 6 D (V9, V14) = 3 
D (V9, V4) = 5 D (V9, V15) = 5 
D (V9, V5) = 4 D (V9, V16) = 4 
D (V9, V6) = 3 D (V9, V17) = 3 
D (V9, V7) = 2 D (V9, V18) = 2 
D (V9, V8) = 1 D (V9, V19) = 1 
D (V9, V9) = 0 E (v9) = 7 
D (V9, V10) = 1 
 
E(V10); 
D (V10, V0) = 8 D (V10, V11) = 1 
D (V10, V1) = 7 D (V10, V12) = 4 
D (V10, V2) = 8 D (V10, V13) = 3 
D (V10, V3) = 7 D (V10, V14) = 2 
D (V10, V4) = 6 D (V10, V15) = 6 
D (V10, V5) = 5 D (V10, V16) = 5 
D (V10, V6) = 4 D (V10, V17) = 4 
D (V10, V7) = 3 D (V10, V18) = 3 
D (V10, V8) = 2 D (V10, V19) = 2 
D (V10, V9) = 1 E (V10) = 8 
D (V10, V10) = 0 
 
 
 
 
 
E(V11); 
D (V11, V0) = 9 D (V11, V11) = 0 
D (V11, V1) = 8 D (V11, V12) = 3 
D (V11, V2) = 8 D (V11, V13) = 2 
D (V11, V3) = 6 D (V11, V14) = 1 
D (V11, V4) = 5 D (V11, V15)= 7 
D (V11, V5) = 4 D (V11, V16) = 6 
D (V11, V6) = 5 D (V11, V17) = 5 
D (V11, V7) = 4 D (V11, V18) = 4 
D (V11, V8) = 3 D (V11, V19) = 3 
D (V11, V9) = 2 E (V11) = 9 
D (V11, V10) = 1 
 
E(V12); 
D (V12, V0) = 6 D (V12, V11) = 3 
D (V12, V1) = 5 D (V12, V12) = 0 
D (V12, V2) = 4 D (V12, V13) = 1 
D (V12, V3) = 3 D (V12, V14) = 2 
D (V12, V4) = 2 D (V12, V15) = 6 
D (V12, V5) = 1 D (V12, V16) = 7 
D (V12, V6) = 2 D (V12, V17) = 8 
D (V12, V7) = 3 D (V12, V18) = 7 
D (V12, V8) = 4 D (V12, V19) = 6 
D (V12, V9) = 5 E (V12) = 8 
D (V12, V10) = 4 
 
E(V13); 
D (V13, V0) = 7 D (V13, V11) = 2 
D (V13, V1) = 6 D (V13, V12) = 1 
D (V13, V2) = 5 D (V13, V13) = 0 
D (V13, V3) = 4 D (V13, V14) = 1 
D (V13, V4) = 3 D (V13, V15) = 7 
D (V13, V5) = 2 D (V13, V16) = 8 
D (V13, V6) = 3 D (V13, V17) = 7 
D (V13, V7) = 4 D (V13, V18) = 6 
D (V13, V8) = 5 D (V13, V19) = 5 
D (V13, V9) = 4 E (V13) = 8 
D (V13, V10) = 3 
 
 
 
 
 
E(V14); 
D (V14, V0) = 8 D (V14, V11) = 1 
D (V14, V1) = 7 D (V14, V12) = 2 
D (V14, V2) = 6 D (V14, V13) = 1 
D (V14, V3) = 5 D (V14, V14) = 0 
D (V14, V4) = 4 D (V14, V15) = 8 
D (V14, V5) = 3 D (V14, V16) = 7 
D (V14, V6) = 4 D (V14, V17) = 6 
D (V14, V7) = 5 D (V14, V18) = 5 
D (V14, V8) = 4 D (V14, V19) = 4 
D (V14, V9) = 3 E (V14) = 8 
D (V14, V10) = 2 
 
E(V15); 
D (V15, V0) = 2 D (V15, V11) = 7 
D (V15, V1) = 1 D (V15, V12) = 6 
D (V15, V2) = 2 D (V15, V13) = 7 
D (V15, V3) = 3 D (V15, V14) = 8 
D (V15, V4) = 4 D (V15, V15) = 0 
D (V15, V5) = 5 D (V15, V16) = 1 
D (V15, V6) = 6 D (V15, V17) = 2 
D (V15, V7) = 7 D (V15, V18) = 3 
D (V15, V8) = 6 D (V15, V19) = 4 
D (V15, V9) = 5 E (V1) = 8 
D (V15, V10) = 6 
 
E(V16); 
D (V16, V0) = 3 D (V16, V11) = 6 
D (V16, V1) = 2 D (V16, V12) = 7 
D (V16, V2) = 3 D (V16, V13) = 8 
D (V16, V3) = 4 D (V16, V14) = 7 
D (V16, V4) = 5 D (V16, V15) = 1 
D (V16, V5) = 6 D (V16, V16) = 0 
D (V16, V6) = 7 D (V16, V17) = 1 
D (V16, V7) = 6 D (V16, V18) = 2 
D (V16, V8) = 5 D (V16, V19) = 3 
D (V16, V9) = 4 E (V16) = 8 
D (V16, V10) = 5 
 
 
 
 
 
E(V17); 
D (V17, V0) = 4 D (V17, V11) = 5 
D (V17, V1) = 3 D (V17, V12) = 8 
D (V17, V2) = 4 D (V17, V13) = 7 
D (V17, V3) = 5 D (V17, V14) = 6 
D (V17, V4) = 6 D (V17, V15) = 2 
D (V17, V5) = 7 D (V17, V16) = 1 
D (V17, V6) = 6 D (V17, V17) = 0 
D (V17, V7) = 5 D (V17, V18) = 1 
D (V17, V8) = 4 D (V17, V19) = 2 
D (V17, V9) = 3 E (V17) = 8 
D (V17, V10) = 4 
 
E(V18); 
D (V18, V0) = 5 D (V18, V11) = 4 
D (V18, V1) = 4 D (V18, V12) = 7 
D (V18, V2) = 5 D (V18, V13) = 6 
D (V18, V3) = 6 D (V18, V14) = 5 
D (V18, V4) = 7 D (V18, V15) = 3 
D (V18, V5) = 6 D (V18, V16) = 2 
D (V18, V6) = 5 D (V18, V17) = 1 
D (V18, V7) = 4 D (V18, V18) = 0 
D (V18, V8) = 3 D (V18, V19) = 1 
D (V18, V9) = 2 E (V18) = 7 
D (V18, V10) = 3 
 
E(V19); 
D (V19, V0) = 6 D (V19, V11) = 3 
D (V19, V1) = 5 D (V19, V12) = 6 
D (V19, V2) = 6 D (V19, V13) = 5 
D (V19, V3) = 7 D (V19, V14) = 4 
D (V19, V4) = 6 D (V19, V15) = 4 
D (V19, V5) = 7 D (V19, V16) = 3 
D (V19, V6) = 4 D (V19, V17) = 2 
D (V19, V7) = 3 D (V19, V18) = 1 
D (V19, V8) = 2 D (V19, V19) = 0 
D (V19, V9) = 1 E (V19) = 7 
D (V19, V10) = 2 
 
La excentricidad del grafo está en el vértice V1 y V11, el cual es de 11 
 
 
 
 
3.3 CENTRO: El centro de G es un Subgrafo inducido por los vértices de mínima excentricidad 
 
Ejemplo: 
 
E(v3)=E(v4)=E(v5)=E(v6)=E(v7)=E(v8)=E(v9)=E(v18)=E(v19)=7 
 
V Excentricidad 
v0 9 
v1 8 
v2 8 
v3 7 
v4 7 
v5 7 
v6 7 
v7 7 
v8 7 
v9 7 
v10 8 
v11 9 
v12 8 
v13 8 
v14 8 
v15 8 
v16 8 
v17 8 
v18 7 
v19 7 
Centro = (V3- a4 - V4 – a5 - V5 – a6 - V6 - a7 - V7 – a8 - V8 – a9 - V9 - a25 - V19 – a19 - V18) 
 
 
 
 
 
 
 
 
3.4 RADIO: en un grafo conexo G, la excentricidad de un centro se llama radio de G. 
 
Ejemplo: Del grafo anterios calcularemos el radio. 
 
Centro = E(v3)=E(v4)=E(v5)=E(v6)=E(v7)=E(v8)=E(v9)=E(v18)=E(v19)=7 
Radio = 7 
 
 
DIÁMETRO: El diámetro D de un grafo conexo G, es la máxima distancia entre dos pares de 
vértices de G. 
Ejemplo: 
En nuestro grafo la distancia más alta es D (V0, V11) y D (V11, V0) cuyo valor es de 9, lo cual 
nos dice que el diámetro del presente grafo es de 9. 
V Excentricidad 
v0 9 
v1 8 
v2 8 
v3 7 
v4 7 
v5 7 
v6 7 
v7 7 
v8 7 
v9 7 
v10 8 
v11 9 
v12 8 
v13 8 
v14 8 
v15 8 
v16 8 
v17 8 
v18 7 
v19 7 
 
 
4. Cadena mínima: Dado un grafo G (V, A, fG) a cada arista a ∈ A(G), se le puede asociar un 
número real, denotado p(a). al que llamamos el peso de la arista a. El grafo G se llama 
entonces un grafo pesado. 
 
Si el grafo G representa una red de carretera entre varias ciudades como las que trabajamos 
en los ejemplos anteriores, el peso de cada arista se puede representar en km, el costo del 
viaje o el tiempo del viaje entre dos vértices (ciudades) 
 
Si S es un subgrafo de un grafo pesado G el peso de S, denotado por p(S) se define como la 
suma de los pesos de las aristas de S, es decir, 
 
p(S) = ∑ 𝑝(𝑎)𝑎 ∈ A (1) 
 
muchos problemas de optimización piden encontrar un grafo pesadoG, un subgrafo S de 
cierto tipo con mínimo o máximo peso. 
 
Uno de estos problemas es conocido como el problema de la cadena mínima, que consiste 
en que dado un grafo conexo G pesado se debe hallar la cadena de mínimo peso o cadena 
mínima que conecte dos vértices específicos V1, V2 de V(G). 
Este problema es resuelto de manera óptima mediante un algoritmo descubierto por dijkstra 
en 1959, el cual no solo halla la cadena de mínimo peso entre dos vértices V1, V2, sino que 
también encuentra todas las cadenas mínimas desde un vértice V1 al resto de los vértices del 
grafo G. 
 
4.1 Algoritmo de Dijkstra: sea G (V, A, fG) un grafo simple, conexo y pesado con |V(G)|=n. 
Sea V´ ∈ V con V´ ≠ φ. Sea V´ el complemento de V´ con respecto a V, es decir, V~ = V – V´. 
 
Sea V1 el vértice de V(G) a partir del cual queremos hallar las cadenas mínimas al resto de 
vértices de G. 
Hacemos V1 = u1, V1 = {u1}, y construiremos una sucesión creciente V1, V2 ..., Vn de 
subconjunto de V, de tal manera que al final de la iteración K, se hayan obtenido las 
cadenas mínimas desde u1 a todos los vértices de Vk 
 
La distancia entre u1 y �̅�K, denotada d(u1, �̅�K) se define mediante la siguiente expresión: 
 
d ( u1, �̅�K ) = min { d ( u1, u) + p(u, v)} (2) 
u ∈ Vk 
v ∈ �̅�K 
Esta expresión es la base del algoritmo. 
 
PRIMERA ITERACION 
 
Sea V1 = {u1} 
Utilizando (2) calculamos d (u1, �̅�1) 
d (u1, �̅�1) = min {d(u1, u1) + p(u1, v)} = min {p(u1, v)} (3) 
 v ∈ �̅�1 v ∈ �̅�1 
 
ya que dV(u1, u1) = 0 
 
el vértice v ∈ �̅�1 que satisface (3) lo llamaremos u2. Hemos obtenido así la cadena mínima 
C1=u1u2. 
 
SEGUNDA ITERACION 
 
Sea V2 = {u1, u2} y C1 = u1, u2. 
Utilizando (2) calculamos d (u1, �̅�2) 
d (u1, �̅�2) = min {d(u1, u) + p(u, v)} (4) 
 v ∈ �̅�2 
El vértice v ∈ �̅�2 que satisface (4) lo llamaremos u3. 
Obtendremos así la cadena mínima C2, que en esta iteración puede ser o C2 = u1u2u3 o 
C2 = u1u3 
 
K-ESIMA ITERACION 
 
Sea Vk = {u1, u2 . . ., uk} y K ≤ n-1 y C1, C2, . . . . , Ck-1 las correspondientes cadena mínima. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Ejemplo: Aplicar el al Algoritmo de Dijkstra al siguiente grafo de V1 -> V8 
 
 
 
 
 
PRIMERA ITERACION 
Sea V1 = u1, V1 = {u1}, �̅�1 = {V2, V3, V4, V5, V6, V7, V8} y d (u1, u1) = 0 
d (u1, �̅�1) = min {p(u1, v)} 
 v ∈ �̅�1 
 
=min{p(u1, v2), p(u1, v3), p(u1, v4), p(u1, v5), p(u1, v6), p(u1, v7), p(u1, v8)} 
 
=min {1, 3, ∞, ∞, ∞, ∞, ∞} 
= 1 
 
Hacemos V2 = u2 
La cadena mínima C –(u1, u2) obtenida es C1=u1u2 y d(u1, u2) = 1 
 
SEGUNDA ITERACION 
Sea V2 = {u1, u2}, �̅�2 = {V3, V4, V5, V6, V7, V8} 
d (u1, �̅�2) = min {d(u1, u) + p(u, v) } 
 v ∈ �̅�2 
 v ∈ V2 
=min {p(u1, v), 1 + p(u2, v)} 
 v ∈ �̅�2 
=min {p(u1, v3), 1 + p(u2, v5) , 1 + p(u2, v6)} 
=min {3, 3, 6} 
=3 
 
Observemos que en esta iteración tenemos dos posibilidades para seleccionar el vértice 
u3: v3= u3 ó v5=u3 
Hacemos V3 = u3 
La cadena mínima C –(u1, u3) obtenida es C2=u1u3 y d (u1, u3) = 3 
 
TERCERA ITERACION 
 
Sea V3 = {u1, u2, u3}, �̅�3 = { V4, V5, V6, V7, V8} 
d (u1, �̅�3) = min {d(u1, u) + p(u, v) } 
 v ∈ �̅�3 
 v ∈ V3 
=min { 1+ p(u2, v), 3 + p(u3, v)} 
 v ∈ �̅�3 
=min { 1 + p(u2, v5) , 1 + p(u2, v6) , 3 + p(u3, v4), 3 + p(u3, v5)} 
=min {3, 6, 8, 4} 
=3 
 
Hacemos V5 = u4 
La cadena mínima C –(u1, u4) obtenida es C3=u1u2u4 y d (u1, u4) = 3 
 
CUARTA ITERACION 
 
Sea V4 = {u1, u2, u3, u4}, �̅�4 = { V4, V6, V7, V8} 
d (u1, �̅�4) = min {d(u1, u) + p(u, v) } 
 v ∈ �̅�4 
 v ∈ V4 
=min { 1+ p(u2, v), 3 + p(u3, v) , 3 + p(u4, v)} 
 v ∈ �̅�4 
=min { 1 + p(u2, v6) , 3 + p(u3, v4), 3 + p(u4, v6) , 3 + p(u4, v7)} 
=min {6, 8, 5, 7} 
=5 
 
Hacemos V6 = u5 
La cadena mínima C –(u1, u5) obtenida es C4=u1u2u4u5 y d (u1, u5) = 5 
 
QUINTA ITERACION 
 
Sea V5 = {u1, u2, u3, u4, u5}, �̅�5 = { V4, V7, V8} 
d (u1, �̅�5) = min {d(u1, u) + p(u, v) } 
 v ∈ �̅�5 
 v ∈ V5 
=min { 3 + p(u3, v) , 3 + p(u4, v) , 5 + p(u5, v)} 
 v ∈ �̅�5 
 
 
=min {3 + p(u3, v4), 3 + p(u4, v7), 5 + p(u5, v8)} 
=min {8, 7, 8} 
=7 
 
Hacemos V7 = u6 
La cadena mínima C –(u1, u6) obtenida es C5=u1u2u4u6 y d (u1, u6) = 7 
 
SEXTA ITERACION 
 
Sea V6 = {u1, u2, u3, u4, u5, u6}, �̅�6 = { V4, V8} 
d (u1, �̅�6) = min {d(u1, u) + p(u, v) } 
 v ∈ �̅�6 
 v ∈ V6 
=min { 3 + p(u3, v) , 5 + p(u5, v), 7 + p(u6, v)} 
 v ∈ �̅�6 
=min {3 + p(u3, v4), 5 + p(u5, v8), 7 + p(u6, v4) , 7 + p(u6, v8)} 
=min {8, 8, 9, 8} 
=8 
Observemos que tenemos 3 mínimos para seleccionar, pero descartamos u3 ya que no 
nos lleva al destino establecido. Ahora nos queda 2 mínimos que nos llevan al destino 
final con el mismo peso(costo) V8=u7, lo que nos quiere decir que existe dos caminos 
que nos lleva al destino final con el mínimo peso, los cuales son: 
 
C6=u1u2u4u5u7 ó C6=u1u2u4u6u7 y d (u1, u7) = 8 
 
 
 
 
 
4.1 Corrección del algoritmo de Dijkstra 
Cuando un grafo conexo simple, con un peso positivo para cada arista es la entrada al algoritmo 
de Dijkstra con vértice inicial a y vértice final z, la salida es la longitud de una trayectoria más 
corta de a a z. 
 
 
 
 
 
 
 
 
 
EJERCICIOS/ACTIVIDADES 
 
 
Taller 6 
Mediante un grafo del taller 4 dado calcular las conexiones, distancia ( Métrica, 
excentricidad, centro, radio) y aplicar el algoritmo de Dijkstra. 
BIBLIOGRAFIA 
 
 
 Viloria, J. (s.f.). Scrib. Obtenido de Scrib: https://es.scribd.com/doc/209571060/Operaciones-
Entre-Grafos 
 Epp, S. (2012). Matemáticas discretas con aplicaciones (4a. ed.). 1st ed. México, D.F.: 
CENGAGE Learning, pp.625-641. 
 Jiménez Murillo, J. and Rodríguez Cruz, F. (2014). Matemáticas para la computación. 1st ed. 
México: Alfaomega Grupo Editor, pp.287-288. 
 Comellas Padró, F. (2002). Matemática discreta. 1st ed. México, D.F.: Alfaomega, pp.103-
105. 
 Wikiwand. (2017). Grafo | Wikiwand. [online] Available at: 
http://www.wikiwand.com/es/Grafo [Accessed 5 Jul. 2017]. 
 Wilson, R. and Garciá Camarero, E. (1983). Introducción a la teoriá de grafos. Madrid: 
Alianza, pp.20-50. 
 Ore, O. (1995). Grafos y sus aplicaciones. Madrid: DLS-EULER, pp.70-98.