Alfredo Caicedo Barrero

Graciela Wagner de Garca

Rosa Mara Mndez Parra
Docentes Universidad del Quindo
 INTRODUCCIN A LA

TEORA DE GRAFOS
Primera Edicin

c
Derechos reservados
Reproducido y editado por Ediciones Elizcom
Primera edicin, diciembre del 2010
200 ejemplares
ISBN: 978-958-99325-7-5
[Link]
ventas@[Link]
Cel: 3113340748
Armenia, Quindo
 Contenido

PRLOGO iii

1. GRAFOS 1
1.1. Conceptos Bsicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Representacin de un Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3. Matriz de Adyacencias de un Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4. Lista de Adyacencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5. Coeficiente de estabilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2. RELACIONES Y GRAFOS 17
2.1. Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2. Matriz de una Relacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3. Grfica de una Relacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4. Propiedades de una Relacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5. Operaciones entre Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.6. Producto Lgico de Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.7. Trayectorias y Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.8. Algoritmo de Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3. CONEXIDAD 39
3.1. Grafo Conexo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2. Algoritmo para Conexidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3. Algoritmo para Grafos no Dirigidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4. CIRCUITO EULERIANO 45
4.1. Circuito de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.1.1. Puentes de Knigsberg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2. Algoritmo de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5. CICLO HAMILTONIANO 53
5.1. Ciclo de Hamilton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.2. Algoritmo Hamiciclo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3. Problema del Agente Viajero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.4. Algoritmo del Vecino ms Cercano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

6. LA TRAYECTORIA MS CORTA 61
6.1. Trayectoria Mnima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.2. Algoritmo del Camino Mnimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.3. Trayectoria del Valor Mnimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.4. Algoritmo de DIJKSTRA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.5. Algoritmo de Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.6. Algoritmo Matricial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.7. La Trayectoria ptima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
i
ii CONTENIDO

7. RBOLES 83
7.1. Conceptos Bsicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
7.2. Subrboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7.3. rbol Binario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.4. rboles Etiquetados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.5. rbol Posicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.6. Otras Formas de rboles Ordenados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.7. Representacin Matricial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.8. Representacin Secuencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.9. Representacin Enlazada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.10. Conversin de un rbol General a Binario . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7.11. Recorrido de un rbol Binario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.12. Notacin Polaca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.13. Bsqueda y Ordenamiento con rboles Binarios . . . . . . . . . . . . . . . . . . . . . . . . 101

8. RBOLES NO DIRIGIDOS 107

8.1. rbol No Dirigido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
8.2. rbol Generado de Relaciones Conexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
8.3. rbol Generador de Mnimo Peso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
8.4. Algoritmo de Prim (Robert C. Prim, 1957) . . . . . . . . . . . . . . . . . . . . . . . . . . 110
8.5. Algoritmo de Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
8.6. rbol Generador de Mnima Distancia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
8.7. Algoritmo de Dijkstra (rbol de mnima distancia) . . . . . . . . . . . . . . . . . . . . . . 113

A. Caicedo B., G. Wagner de G., R. M. Mndez

 PRLOGO

La Matemtica Discreta y una de sus reas principales como es la teora de grafos ocupan hoy en da
un lugar muy importante entre los conocimientos bsicos que deben adquirir las personas que se dedican
al estudio de las ciencias de la computacin, las matemticas aplicadas, la teora de la optimizacin, la
planeacin estratgica, etc. Adems la Teora de Grafos puede servir para el modelamiento de sistemas,
la simulacin, la estructuracin de datos y el anlisis y diseo de algoritmos.

Este libro pretende ser una gua introductoria para un segundo curso de matemticas discretas, con
una duracin de un semestre y en efecto se ha elaborado con base al programa curricular de Matemticas
Discretas II (Teora de Grafos) de la carrera de Ingeniera de Sistemas de la Universidad del Quindo. Se
ha experimentado durante varios semestres con los estudiantes de dicha disciplina y se ha complementado
con las notas de clase de estos cursos.

El tema central del libro es una introduccin a la teora de grafos, considerando los grafos y los r-
boles como una estructura dinmica que puede aplicarse en la solucin de problemas prcticos y a la
creacin de algoritmos aplicables a la estructuracin de datos.

Aunque el curso cubre varios temas, se ha limitado mucho el contenido de cada captulo y su pro-
fundidad se ha moderado para que sea apenas un curso introductorio a nivel de pregrado. Se han omitido
las pruebas y demostraciones de teoremas para agilizar ms el aprendizaje.

El material de cada captulo se ha complementado con suficientes ejemplos y grficas para aclarar un
poco el carcter abstracto de la teora. Al final de cada captulo se incluye un grupo de ejercicios que
ayudarn a reforzar los conocimientos adquiridos.

Los Autores, Diciembre de 2010.

iii
iv PRLOGO

A. Caicedo B., G. Wagner de G., R. M. Mndez

 ulo
pt
Ca

1 GRAFOS

Los grafos se presentan con frecuencia en la vida real, tal es el caso de una red de carreteras
que enlace un cierto grupo de ciudades; aqu los nodos de la red o ciudades representan los
vrtices del grafo, las carreteras que unen las ciudades representan los arcos o aristas; as
a cada arco se asocia una informacin tal como la distancia entre ciudades, consumo de
gasolina, costo de mantenimiento, etc.

b b b
Los grafos son una estructura de datos no lineal, la cual se
b puede usar para modelar diversas aplicaciones. Es una parte
b b
b b
importante de la Teora Combinatoria en Matemticas, lo
que le da un carcter bastante amplio y complejo. En esta
b
b unidad slo se har una introduccin a los conceptos bsicos
b
de la teora de grafos y a los algoritmos que permiten su
aplicacin a problemas prcticos.

1.1 Conceptos Bsicos

Definicin 1.1 Grafo

Un grafo G consta de un conjunto de vrtices o nodos V y un conjunto de arcos A, cada uno de
los cuales une un vrtice con otro.
G = (V, A) = (N, A)

Los arcos que unen los nodos tambin se llaman aristas del grafo y se representan por medio de un par
de elementos, (vi , vj ), donde los elementos son los nodos que une el arco.

Definicin 1.2 Grafo Dirigido

Si en un grafo los arcos tienen una direccin, el grafo se llama grafo dirigido u orientado.

En un grafo orientado cada arco se representa por medio de un par ordenado (vi , vj ) donde el primer
elemento es el nodo origen o fuente y el segundo es el nodo destino de ese arco, por lo tanto se puede
decir que el arco va desde vi hasta vj y que vj es adyacente a vi . Un grafo orientado tambin se llama un
digrafo. Si los arcos del grafo no indican una direccin, el grafo es no dirigido y en l cada arco se puede
representar nombrando los nodos que lo forman sin importar el orden es decir:

(vi , vj ) = (vj , vi )

1
2 GRAFOS

Ejemplo 1
La figura 2. muestra dos grafos, el primero no dirigido y el segundo un digrafo, ambos, de 4 nodos y
5 arcos. b b b b

b b b b

Figura 2. Grafo dirigido y no dirigido

Los nodos de un grafo se pueden usar para representar los objetos y los arcos para representar relaciones
entre esos objetos. En el ejemplo anterior los nodos podran ser ciudades y los arcos las rutas areas entre
esas ciudades. A los nodos y arcos de un grafo se pueden asignar nombres o valores (etiquetas), crendose
as lo que se llama un grafo etiquetado.

Definicin 1.3 Orden de un Grafo

El nmero de nodos de un grafo se llama orden del grafo y se denota como:

ord(g) = |N (G)| = N
El nmero de aristas o arcos es |A(g)| = A =talla de G = e(G)
Otra notacin: Gn =grafo de orden n. G(n, m) =grafo de orden n y talla m

Definicin 1.4 Grado de un Vrtice

El grado de un vrtice x es el nmero de vrtices adyacentes a l, esto es, el nmero de arcos
incidentes a x y se denota grad(x).

Ejemplo 2

v1 v2 v3

grad(v1 ) = 2 grad(v2 ) = 0 grad(v3 ) = 4

A continuacin enunciaremos un teorema que relaciona el nmero de aristas de un grafo con el orden de
los vrtices de este; adems se da uno de los conceptos ms importantes en el estudio de los grafos como
es el de la trayectoria.

Teorema 1

Si N (G) = x1 , x2 , ..., xn ; entonces,

grad(x1 ) + . . . + grad(xn ) = 2A.
Donde A es el nmero de aristas incidentes

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Conceptos Bsicos 3

Definicin 1.5 Trayectoria

Una trayectoria T en un grafo es una secuencia de nodos v1 , v2 , . . . , vn tal que (v1 , v2 ) ,
(v2 , v3 ) , . . . , (vn1 , vn ) son arcos.

Cuando el grafo no tiene valores asociadas a sus arcos, la longitud de la trayectoria es el nmero de arcos
que la componen.

Ejemplo 3
En la figura 3 la secuencia 1 2 4 es una trayectoria de longitud 2, y la secuencia 1 3 5 2 4
es una trayectoria de longitud 4.
1 2

3 4

Figura 3. Trayectoria de un grafo

Cuando los vrtices de una trayectoria son todos distintos, excepto posiblemente el primero y el ltimo,
la trayectoria se define como una trayectoria simple. Una trayectoria que comienza y termina en el mismo
nodo se llama un ciclo o circuito. Los ciclos de longitud 1 se llaman bucles o lazos porque salen de un
nodo e inciden en el mismo nodo sin pasar por ningn otro.

Ejemplo 4
a
e1
e3 e7
e6
b e4 d e

e2
e5

c
Figura 4. Digrafo etiquetado

El grafo de la figura 4 es un digrafo etiquetado. La trayectoria b c d b es un ciclo y a la vez una

trayectoria simple. Este ciclo tambin se puede nombrar usando las etiquetas de los arcos: e2 , e5 , e3 o
por medio de las parejas de nodos que forman los arcos: (b, c) , (c, d) , (d, b) . El arco e7 es un bucle.
Los arcos e3 y e4 se llaman paralelos.

Definicin 1.6 Grafo Acclico

Un grafo G es acclico si no contiene ciclos.

Los digrafos acclicos son usados para modelar situaciones de conjuntos de tareas que necesitan tener una
secuencia particular y donde es importante que no existan ciclos puesto que una tarea en un ciclo estara
precedida de s misma, es decir, que se repetira.
A. Caicedo B., G. Wagner de G., R. M. Mndez
4 GRAFOS

Ejemplo 5
La siguiente tabla es una lista parcial de tareas para construir una casa. Para cada tarea T , la segun-
da columna muestra aquellas arcos que deben ser completadas antes que T pueda ser comenzada.
Construir un digrafo para mostrar la relacin entre las tareas.

Tareas Prerrequisitos
1. Hacer cimientos Ninguno
2. Adicionar piso base 1
3. Hacer columnas 1
4. Levantar paredes y techo 2y3
5. Adicionar cielo raso 4
6. Instalar plomera 4
7. Instalar redes elctricas 4y5
8. Pegar piso 4y6
9. Instalar puertas 4y8
10. Pintar paredes interiores 4, 7, 8 y 9
11. Pulir piso 10

1 2 3 5 7

4 6 8

9 10 11

Figura 5. Digrafo acclico de tareas

El grafo resultante se muestra en la figura 5.

Determinar si un digrafo es acclico es equivalente a encontrar un etiquetamiento consistente para el

digrafo. Un etiquetamiento consistente es una forma de numerar los nodos en forma tal que cada nodo
tenga un nmero ms bajo que cualquier nodo que l preceda.

Definicin 1.7 Etiquetamiento consistente

Sea G = (N, A) un digrafo. Sea {n1 , n2 , . . . , nn } un etiquetamiento de los nodos. El etiquetamiento
es consistente si (ni , nj ) A i < j.

Un digrafo puede tener varios etiquetamientos consistentes diferentes.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Conceptos Bsicos 5

Teorema 2

Sea G = (N, A) un digrafo. G tiene un etiquetamiento consistente si y solo si G es acclico.

Prueba

La demostracin en el primer sentido se puede hacer en la siguiente forma: supngase que el

digrafo G tiene un etiquetamiento consistente n1 , n2 , . . . , nn . Si existe un ciclo ni1 , ni2 , ..., nik
se debe tener que i1 = ik y que i1 < i2 < . . . < ik , pero esto es una contradiccin, entonces G
no puede tener un ciclo.

Para la demostracin en el otro sentido se parte del supuesto de que el digrafo es accli-
co y se usar un algoritmo llamado algoritmo del Ordenamiento Topolgico para construir
el etiquetamiento consistente. El algoritmo parte del hecho de que un digrafo debe tener
una fuente; la metodologa del algoritmo consiste en etiquetar el conjunto de fuentes y luego
removerlas de su consideracin, luego ser etiquetado el siguiente nivel de fuentes y as
sucesivamente. Eventualmente se presentar una de las siguientes situaciones: o todos los nodos
han sido etiquetados sucesivamente o permanecen nodos sin etiquetar que no son fuentes,
implicando que el digrafo contiene un ciclo, lo cual contradice el supuesto.

Algoritmo de Etiquetamiento Topolgico

Hacer A(n) conjunto de antecedentes de n. Hacer S conjunto de nodos no etiquetados cuyos conjuntos
de antecedentes sea vaco.

begin
Para n N hacer
computar A(n)
etiqueta = O
Mientras S 6= hacer
begin
etiqueta = etiqueta +1
n = nodo con A(n) =
asignar la etiqueta a n y sacarlo de consideracin. Establecer a S
Para cada nodo no etiquetado u N , hacer
A(u) = A(u) {n}
end
Si todos los nodos no estn etiquetados entonces
reportar: "hay un ciclo en el digrafo".
end.

A. Caicedo B., G. Wagner de G., R. M. Mndez

6 GRAFOS

Ejemplo 6
Aplicar el algoritmo del ordenamlento topolgico al siguiente digrafo para obtener un etiquetamiento
consistente.

2 3

1 4

6 5

Figura 6.

Solucin

1. Computar los conjuntos de antecedentes A(n) para cada n N A(1) = , A(2) = {1}, A(3) =
{2, 4}, A(4) = {1, 2, 6}, A(5) = {4, 6}, A(6) = {1}. Etiqueta = 0. S = {1}, S 6= .

2. Desarrollar el bucle principal:

a) n = 1. Etiquetar 1 con E(1) y sacarlo de consideracin. S = {2, 6}. Computar nuevo

conjunto de antecedentes: para todo u no etiquetado hacer A(u) = A(u) {n} A(2) =
, A(3) = {2, 4}, A(4) = {2, 6}, A(5) = {4, 6}, A(6) =
b) n = 6 Etiquetar 6 con E(2) y sacarlo de consideracin. S = {2}. Computar nuevo conjunto
de antecedentes: A(2) = , A(3) = {2, 4}, A(4) = {2}, A(5) = {4}
c) n = 2 Etiquetar 2 con E(3) y sacarlo de consideracin. S = {4}. Computar nuevo conjunto
de antecedentes: A(3) = {4}, A(4) = , A(5) = {4}.
d ) n = 4 Etiquetar 4 con E(4) y sacarlo de consideracin. S = {3, 5}. Computar nuevo
conjunto de antecedentes: A(3) = , A(5) = .
e) n = 3 Etiquetar 3 con E(5) y sacarlo de consideracin. S = {5}. Computar nuevo conjunto
de antecedentes: A(5) =
f ) n = 5 Etiquetar 5 con E(6) y sacarlo de consideracin. S =

3. Todos los nodos estn etiquetados. Parar.

Definicin 1.8 Grafo Simple

Un grafo G se denomina simple o sencillo si cumple:

1. No tiene lazos.

2. No existe ms que que un arco para cada par de nodos j

Un grafo que no es sencillo se le llama grafo mltiple o multigrafo.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Conceptos Bsicos 7

b b

b b b

b b

Figura 7. a) Grafo Simple b) Grafo Mltiple

Definicin 1.9 Grafo Completo

Es aquel en el que cada par de nodos distintos estn unidos por un arco o cualquier nodo est unido
a todos los otros.

Un grafo completo con r nodos es llamado un r-grafo y se acostumbra notarlo con Kr .

Ejercicio 1
Graficar los siguientes grafos: K1 , K2 , K3 , K4 , K5 y K6

Teorema 3

r(r 1)
Un r-grafo no dirigido contiene exactamente arcos.
2

Prueba

En Kr cada nodo tiene grado r 1. Luego la suma de los grados es:

grad(x1 ) + ... + grad(xr ) = r(r 1) = a un nmero par

r(r 1)
Por el teorema 1, esta suma tambin es igual a 2A. Por lo tanto 2A = r(r 1) y A =
2

Corolario
Para cada grafo Kr no dirigido se cumple que:
N (N 1)
A
2

Definicin 1.10 Grafo Regular

Un grafo en el cual cada nodo tiene grado r se llama regular de grado r o r-regular.

A. Caicedo B., G. Wagner de G., R. M. Mndez

8 GRAFOS

Ejercicio 2
1. Trazar dos grafos 3-regular con 6 nodos

2. Trazar los siguientes grafos:

a) 0-regular
b) 1-regular
c) 2-regular

Teorema 4

Un grafo regular debe tener un nmero par de nodos

Prueba

Sea S=suma de los grados del grafo r-regular con n nodos,

S = grad(x1 ) + grad(x2 ) + + grad(xn ) = n r = #par
nr = #par si r es impar, n es par

Teorema 5

En un grafo no dirigido de n nodos, el nmero de nodos de grado impar es par

Ejemplo 7
b b b

b b b

1.2 Representacin de un Grafo

Existen diversas formas de representar un grafo dirigido o no-dirigido, pero entre ellas las ms usadas
y fciles de implementar por computador son: la matriz de adyacencias y la lista de adyacencias. Esta
ltima es la ms conveniente para efectos de computacin puesto que opera ms rpido y ocupa menos
memoria.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Matriz de Adyacencias de un Grafo 9

1.3 Matriz de Adyacencias de un Grafo

Sea G = (N, A) un grafo de n nodos. La Matriz de Adyacencias M para G es una matriz Mnxn de valores
booleanos, donde M (i, j) es verdad si y solo si existe un arco desde el nodo i al nodo j.
(
1, si existe el arco (i, j)
M (i, j) =
0, en caso contrario

Las filas y las columnas de la matriz representan los nodos del grafo.
Cuando el grafo no es dirigido la matriz de adyacencias es simtrica.
La matriz de adyacencias es la misma matriz de la relacin A de N en N porque indica cuales nodos
estn relacionados (unidos por un arco)

Ejemplo 8
La siguiente es la matriz de adyacencias del grafo orientado que se muestra en la figura 8.

a b c d b

a 0 1 1 0
b 0 0 1 1 a d
M (i, j) =
c 1 0 0 1
d 1 0 0 0
c
Figura 8.

Nota: Para un digrafo, la matriz de adyacencias depende del orden de los nodos. Para distintos rdenes
en los nodos se obtienen distintas matrices de adyacencias de un mismo grafo G

Ejemplo 9
Grafo orientado con su correspondiente matriz de adyacencias (matriz de pesos o valores)
120

2 3
1 2 3 4 5
100
1 0 100 0 0 0 1 110
20 0 120 0 0 200
M (i, j) = 3
0 0 0 200 0
4 0 110 0 0 80 4
5 0 0 0 0 0
80
5
Figura 9.

A. Caicedo B., G. Wagner de G., R. M. Mndez

10 GRAFOS

Ejemplo 10
Considere el esquema de Von Newmann, para un computador que consta de los siguientes dispositivos:
V = (a, b, c, d, e) donde a es un dispositivo de entrada, b es una unidad aritmtica, c es una unidad
de mando, d es una unidad de memoria y e es un dispositivo de salida. Las relaciones entre unidades
y dispositivos se representan en el grafo de la figura 10.

b c d

Figura 10.

Si con un 1 se indica que hay un paso de informacin (relacin) desde el componente vi al componente
vj , la matriz que representa al grafo es:
a b c d e

a 0 1 1 1 0
b0 0 1 1 1

M (i, j) = c
1 1 0 1 1

d0 1 1 0 1
e 0 0 1 0 0

Ejemplo 11
Un mensajero debe visitar los seis puntos mostrados en la figura 11a) partiendo del punto a y
terminando en el punto f. El conoce la distancia que separa a cada par de puntos y desea establecer
el recorrido que debe seguir para recorrer la mnima distancia y ahorrar tiempo.

4
a b a b
11 6 19

15
c f 16 c f
5 8
4
3
d e d e

a) b)
Figura 11.
Con las distancias entre los puntos se construye el grafo no dirigido etiquetado:
Para hallar el recorrido de mnima distancia se podrian listar todas las posibles trayectorias desde a
hasta f y escoger la menor. Una de tales trayectorias es : a b c d e f de longitud 22.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Lista de Adyacencias 11

De hecho este no es el mejor mtodo para resolver el problema. Se han desarrollado algoritmos muy
eficientes que con la ayuda del computador pueden producir una solucin muy ptima en un tiempo
bastante corto. Uno de estos algoritmos es el propuesto por DIJKST RA y que se estudiar ms adelante.

1.4 Lista de Adyacencias

Sea G = (N, A) un grafo. La lista de adyacencias para un nodo i es una lista, en cualquier orden, de
todos los nodos adyacentes a i.

En esta representacin el grafo incluye dos partes: un directorio y un conjunto de listas enlazadas. Hay
una entrada al directorio por cada nodo del grafo.

Ejemplo 12
La figura 12 muestra un grafo dirigido y su correspondiente representacin en lista de adyacencias.

1 2 1 b
2 b
3 b

2 b
4 b

3 b
2 b

3 4 4 b
3 b

Figura 12.
La entrada en el directorio del nodo i apunta a una lista enlazada que representa los nodos que
son conectados al nodo i. Cada registro de la lista enlazada tiene dos campos: el primero es un
identificador de nodo y el otro es un enlace al siguiente elemento de la lista j. La lista enlazada
representa arcos.

Ejemplo 13
La figura 13 muestra un grafo con su correspondiente lista de adyacencias.

1 b
2 b

6
2 b
2 b
3 b

2 3 5 3 b
5 b
6 b

4 b
3 b

1 5 b b

4
6 b b

Figura 13.

Si este grafo no fuera orientado, la lista de adyacencias sera la que se muestra en la figura 14.

A. Caicedo B., G. Wagner de G., R. M. Mndez

12 GRAFOS

1 b
2 b

2 b
1 b
2 b
3 b

3 b
2 b
4 b
5 b
6 b

4 b
3 b

5 b
3 b

6 b
3 b

Figura 14.

Ejemplo 14
Otra forma de presentar la lista de adyacencias

A B C Lista de adyacencias
A : B, P
B : A, C, P, Q
C: B
P : A, B
P Q Q: B

G = [A : B, P ; B : A, C, P, Q; C : B; P : A, B; Q : B]

Representacin enlazada de G

1.5 Coeficiente de estabilidad

Un concepto muy aplicable de la teora de grafos es el coeficiente de estabilidad interna y externa que
sirve para resolver problemas referentes a modelos de comunicacin.

Definicin 1.11
Sea G (N, A) y S N (S subconjunto de nodos de G) . Se dice que S es interiormente estable si
no contiene ninguna pareja de nodos adyacentes.

Recurdese que dos nodos ni y nj son adyacentes si son distintos y al menos existe un arco (ni , nj ) o
(nj , ni ) .

Definicin 1.12 Coeficiente de estabilidad interna

El coeficiente de estabilidad interna (G) de G es igual a:

(G) = max {S}

Es decir (G) es el nmero de elementos que contiene el mayor subconjunto S interiormente estable.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Coeficiente de estabilidad 13

Ejemplo 15 1 3 2

6 4

8 7
Figura 15.

En el grafo de la figura 15, los conjuntos de nodos {1, 2, 7} ; {6, 7, 1} ; {5, 4, 3} y {8, 4, 3} son conjuntos
interiormente estables. El coeficiente de estabilidad interno de G es (G) = max {S} = 5 con S =
{1, 2, 6, 7, 5}

Ejemplo 16
Capacidad de un Conjunto de Seales
Considrese un transmisor que puede emitir cinco seales diferentes {a, b, c, d, e} . Estas seales se
reciben en un receptor de tal forma que cada una puede dar lugar a dos interpretaciones diferentes:
a puede dar p o q, b puede dar q o r, c : r o s, d : s o t, y e : t o p. Esta informacin se puede
representar en el grafo de la figura 16.a.
a p b

b q

c r a c

d s

e t e d

a) Figura 16. b)

Cul es el nmero mximo de seales que pueden emitirse simultneamente en forma tal que no
exista posibilidad de confusin en la recepcin?
El problema equivale a buscar un conjunto interiormente estable y mximo, del grafo de la figura
16a en donde dos nodos son adyacentes si representan dos seales que puedan confundirse. Se llega
as a construir un nuevo grafo, ver f ig. 16 b donde:
a se une con b porque ellas pueden producir q
b se une con c porque ellas pueden producir r
c se une con d porque ellas pueden producir s
d se une con e porque ellas pueden producir t
e se une con a porque ellas pueden producir p
El grafo obtenido tiene los siguientes conjuntos interiormente estables:
{a, c}, {a, d}, {b, d}, {b, e} y {c, e}
donde (G) = 2. Luego, el nmero mximo de seales que se puede emitir sin crear confusin es 2.

A. Caicedo B., G. Wagner de G., R. M. Mndez

14 GRAFOS

A continuacin definiremos el Coeficiente de estabilidad externa

Definicin 1.13 Coeficiente de estabilidad externa

Un subconjunto T de nodos de un grafo G es exteriormente estable si todo nodo ni
/ T est ligado
al menos a un nodo de T por un arco cuyo extremo inicial es ni .

Definicin 1.14
El coeficiente de estabilidad externa (G) de G es igual (G) = min{T }, lo que significa que es
igual al nmero de elementos del menor conjunto exteriormente estable.

Ejemplo 17
En el grafo de la figura 17 los siguientes conjuntos son exteriormente estables:
{c, d, e, f, h}, {c, e, h} y {c, e, f, h}
a b c

El coeficiente de estabilidad externa es:

e d (G) = min{T } = 3, T = {c, e, h}
f

h
g
Figura 17.

Ejemplo 18
Redes de Comunicacin
Considrese un conjunto de subestaciones telefnicas con sus respectivas redes, como lo indica El
grafo de la figura 18.
1 4 B

11
A 2 5 8
10
3 6 9

7
Figura 18.

Cul es el nmero mnimo de subestaciones que deben fallar para que las centrales A y B no
pueden intercomunicarse?. El problema se reduce a encontrar un conjunto mnimo de articulaciones
que divida al grafo G en dos subgrafos disyuntos, conteniendo uno a A y el otro a B. Sea T = {4, 5, 9}.
T es un subconjunto de nodos exteriormente estable porque todos los nodos que no pertenecen a T
estn ligados al menos a uno de los nodos de T por un arco que se inicia en ellos. Adems T es el
mnimo de los subconjuntos exteriormente estables que se pueden obtener de G. El coeficiente de
estabilidad externa para G es (G) = min{T } = 3. Se concluye que si fallan las subestaciones 4, 5 y
9, las centrales A y B no pueden comunicarse.
A. Caicedo B., G. Wagner de G., R. M. Mndez
 Coeficiente de estabilidad 15

Ejercicios Captulo 1

1. Sea N = {1, 2, 3, 4} un conjunto de nodos y A = {(1, 3), (2, 4), (4, 3)} un conjunto de arcos, dibujar
el grafo correspondiente.
2. Dados los dos grafos de la figura 19, establecer el conjunto de nodos N y el conjunto de arcos A.
a f 1

b d g 2 3 4
7

c e 5 6

Figura 19.
3. En los grafos del ejercicio anterior determinar el orden y el nmero de arcos de cada uno. Usar la
notacin correspondiente.
4. En el grafo de la figura 20, determinar el grado de cada uno de sus nodos.
a d

b e

Figura 20.

5. Hallar dos trayectorias entre los nodos b y e del grafo de la figura 20.
6. Para los grafos de la figura 21 encontrar una trayectoria que vaya desde a hasta a y que pase por
cada arco una sola vez.
a b c b c

d e a d

f f e

Figura 21.

7. Examinar los siguientes grafos y determinar cules son simples y cules no, justificar la respuesta.

a b a b 1 2 1 2

3
c d c d 3

Figura 22.

A. Caicedo B., G. Wagner de G., R. M. Mndez

16 GRAFOS

8. Trazar un grafo completo de 5 nodos.

9. Trazar un K6 grafo.

10. Probar que un K7 grafo tiene 21 arcos. Dibujarlo.

11. Trazar un grafo regular de grado 4.

12. Establecer la matriz de adyacencias para cada uno de los grafos de la figura 23.

a b a d e
g
b c
c
c d f h
a
i
d e e f b

a 12 1
b 20
5
20 12 e 2 8 5
10
4 6
14
c d 3 4
Figura 23.

13. Establecer la lista de adyacencias para cada uno de los grafos del ejercicio nmero 12.

14. Para el grafo de la figura 24 establecer los coeficientes de estabilidad interna y externa.

1
4
B

A 2 5

7
3 6

Figura 24.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 ulo
pt
Ca

2 RELACIONES Y GRAFOS

El concepto fundamental de las Matemticas Discretas es el de Relacin, por ello en esta seccin
se hace una breve introduccin a las relaciones y se utilizarn para designar la correspondencia
entre los objetos o nociones tales como los nodos de un grafo.

2.1 Relaciones

Definicin 2.1 Relacin

Sean A y B conjuntos no vacos. Una relacin binaria de A en B es un subconjunto de A B

Si A B y (a, b) , se dice que a est relacionado con b por y se escribe

ab.

Ejemplo 1
Sean A = {3, 7, 9} y B = {x, y} entonces = {{3, x), (9, y)} es una relacin de A en B.

Cuando los conjuntos A y B son iguales se dice que A A es una relacin en A en lugar de una
relacin de A en A.

Si el conjunto de referencia para la relacin es el conjunto N de puntos (nodos) y la relacin binaria

es N 2 , entonces la coleccin formada por N y se denomina un grafo G. Algunos autores llaman a
N el portador del grafo y a la signatura del grafo.

Si A B es una relacin de A en B, existen dos conjuntos asociados a :

1. El dominio de que se escribe Dom(), es el conjunto de elementos de A que estn relacionados

con algn elemento de B, por lo tanto Dom() A.

2. El codominio de que se escribe Cod() es el conjunto de elementos de B que estn relacionados

con algn elemento de A, por lo tanto Cod() B.

17
18 RELACIONES Y GRAFOS

Ejemplo 2
Sean A = {1, 3, 5} y B = {0, 1, 2, 4, 7}. Se define la siguiente relacin de A en B:

AB a < b

Entonces: = {(1, 2), (1, 4), (1, 7), (3, 4), (3, 7), (5, 7)}; Dom() = {1, 3, 5} y Cod() = {2, 4, 7}.

2.2 Matriz de una Relacin

Definicin 2.2 Matriz de una Relacin

Si es una relacin de A en B, es posible representar a como una matriz M = [mij ] con
elementos de la forma:
1, si (a , b )
i j
mij =
0, si (a , b )
i j /

Ejemplo 3
Sean A = {0, 7, 5, 9} y B = {1, 3, 10} y la relacin dada por:

AB a > b
7

1 3 10
3

0 0 0 0
0 5 71 1 0
M =
1 51 1 0
9 1 1 0
9 10
Figura 1.

Entonces: = {(5, 1), (5, 3), (7, 1), (7, 3), (9, 1), (9, 3)}. La matriz de se ve en la figura 1:

Nota: En un grafo no dirigido M = M de adyacencias

Ejemplo 4
Sean X = {3, 9, 1} e Y = {a, b} . Luego = {(3, a), (9, b), (1, a), (1, b)}.

a b

3 1 0
M = 9 0 1
1 1 1

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Grfica de una Relacin 19

2.3 Grfica de una Relacin

Si A es un conjunto finito y es una relacin en A, los elementos de A se pueden representar como

puntos del plano, unidos por arcos dirigidos si ai aj . La grfica resultante para esta relacin se llama un
grafo dirigido.

Ejemplo 5
Sean A = {a, d, c, m} y = {(a, d), (a, c), (d, c), (c, d), (c, m), (m, m)}. El grafo dirigido de es el de
la figura 2.
d

a m

c
Figura 2.

Ejemplo 6
Determinar la relacin representada por el grafo de la figura 3.
2

1 4 5

Figura 3.

Puesto que ai aj si y solo si existe el arco de ai a aj se tiene:

= {(1, 2), (1, 4), (2, 1), (3, 1), (3, 5), (3, 3), (4, 4), (4, 5)}.

2.4 Propiedades de una Relacin

Reflexiva
Una relacin en un conjunto A es reflexiva si (a, a) , es decir, aa, a . es reflexiva si cada
elemento a A est relacionado consigo mismo.
A. Caicedo B., G. Wagner de G., R. M. Mndez
20 RELACIONES Y GRAFOS

Definicin 2.3 Irreflexiva

es irreflexiva si algn elemento no est relacionado consigo mismo.

La matriz de una relacin reflexiva tiene unos en toda su diagonal principal. La matriz de una relacin
irreflexiva tiene al menos un cero en la diagonal principal.

Ejemplo 7
El siguiente grafo muestra una relacin reflexiva.

a b

c d

Figura 4.

Simtrica
Una relacin en un conjunto A es simtrica si cuando ab ba a, b

Definicin 2.4 Antisimtrica

es asimtrica si ab entonces ba , es antisimtrica si cuando ab y ba a = b, a y b

Ejemplo 8
Sea = {(a, b) A A |a < b }. Luego:

1. Si a < b b a no es simtrica, es asimtrica.

2. Si a 6= b a b b a es antisimtrica.

Teorema 1

La matriz M = [mij ] de una relacin simtrica satisface:

1. Si mij = 1 mji = 1.
2. Si mji = 0 mij = 0. Luego M = (M )T entonces M es simtrica.

Ejemplo 9

1 1 0 1 1 0
Si M = 1 0 1 , entonces MT = 1 0 1
0 1 0 0 1 0

Teorema 2

La matriz M de una relacin asimtrica satisface:

1. Si mij = 1 mji = 0.
2. mij = 0 para i = j.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Propiedades de una Relacin 21

Teorema 3

La matriz M de una relacin antisimtrica satisface que si i 6= j mij = 0 mji = 0

De los anteriores teoremas se pueden concluir las siguientes afirmaciones:

1. Si es una relacin asimtrica, entonces el grafo dirigido no puede tener simultneamente un arco
desde el nodo i al nodo j y un arco desde el nodo j al nodo i. No puede haber ciclos de longitud 1.

2. Si es antisimtrica, entonces para i 6= j no puede haber un arco desde i a j y un arco desde j a

i. Pueden existir ciclos de longitud 1.

3. Si es simtrica, entonces, si existe el arco de i a j, tambin existe el arco desde j a i.

Definicin 2.5 Relacin Conexa

Una relacin simtrica en A se llama conexa si existe una trayectoria desde cualquier elemento
de A a cualquier otro elemento de A, es decir, el grafo es completo

Ejemplo 10
El grafo de la figura 5 representa una relacin conexa.

a b c

Figura 5.

Transitiva
Una relacin en un conjunto A es transitiva si cuando ab y bc entonces ac.
En una relacin transitiva se tiene: si mij = 1 y mjk = 1 mik = 1.
En un grafo dirigido las condiciones ab y bc ocurrirn si y solo si existe una trayectoria de longitud
dos desde a hasta c. es decir, que a2 c implica que ac. 2 , siendo un subconjunto de A A.
Cualquier par de nodos conectados por un arco deben estar conectados por una trayectoria de longitud
2.
Con base al concepto anterior se puede establecer la siguiente definicin de transitividad.

Definicin 2.6 Transitividad

es transitiva si y solo si n n 2. es transitiva si 2 =

Ejemplo 11
2
1 2 3 (MR ) = MR R es transitiva

1 1 1 1 2
Sea A = {1, 2, 3} y MR = 2 0 0 1
3 0 0 1
1 3

A. Caicedo B., G. Wagner de G., R. M. Mndez

22 RELACIONES Y GRAFOS

Ejemplo 12
a b 1 2
0 1 0 1

1 0 1 1
5



0 1 0 0
c d e 3 4
1 1 0 0
Transitiva Antisimtrica Irreflexiva
Transitiva Simtrica
No transitiva

Definicin 2.7 Relacin de Equivalencia

Una relacin sobre un conjunto A se llama relacin de equivalencia si cumple que es reflexiva,
simtrica y transitiva.

Ejemplo 13

1 0 0 1 0 1


0 1 1 0 1 0

0 1 1 1 0 1
Relacin de equivalencia Reflexiva, simtrica, no transitiva

2.5 Operaciones entre Relaciones

As como es posible manipular nmeros y frmulas usando las reglas del lgebra, tambin es posible
definir operaciones que permitan manipular relaciones. Una vez definidas ciertas operaciones se puede
operar con ellas sobre relaciones existentes para obtener otras relaciones.

Algunas de las operaciones que se pueden definir sobre relaciones son:

Relacin Complementaria

Sean A y B dos conjuntos finitos y una relacin de A en B. Se define la relacin complemen-

taria como:
ab ab

Nota: A B

Ejemplo 14
Sean A = {3, 4, 5}, B = {a, b, c} y = {(3, a)(3, b)(4, c)(5, c)}. = {(3, c)(4, a)(4, b)(5, a)(5, b)}.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Operaciones entre Relaciones 23

Interseccin de Relaciones
Sean A y B dos conjuntos finitos, y S relaciones definidas de A en B. Se define la interseccin
de las dos relaciones como:
a( S)b ab y aSb

Nota: (a, b) ( S), si est en y tambin est en S

Unin de Relaciones
Sean A y B dos conjuntos finitos, y S relaciones definidas de A en B. Se define la unin de
las dos relaciones como:
a( S)b ab aSb

Nota: (a, b) ( S), si est en o est en S

Relacin Inversa

Sean A y B dos conjuntos finitos, R una relacin de A en B. Se define la relacin inversa 1

como una relacin de B en A tal que:
b1 a ab

Nota: (b, a) (1 ), si (a, b)

Ejemplo 15
Sean
A = {1, 5, 7, 9}, B = {x, y},
S = {(1, y)(5, x)(7, y)(9, x)} y
= {(1, x)(1, y)(5, y)(7, x)(7, y)(9, x)}.

Calcular 1. , 2. S, 3. S y 4. 1

Solucin

1. Para hallar el complemento se compara la relacin dada con A B, donde,

A B = {(1, x), (1, y), (5, x), (5, 7), (7, x), (7, y), (9, x), (9, y)}

as, el complemento de es: = {(5, x), (9, y)}.

2. La interseccin S se forma con el conjunto de parejas en comn entre y S, as,

S = {(7, y), (9, x)(1, y)}.

3. La unin S se forma juntando las parejas de con las de S sin repetir parejas, por lo que
S = {(1, x), (1, y), (5, x), (5; y), (7, x), (7, y), (9, x)}.
4. 1 se forma tomando las parejas de e invirtiendo el orden de los elementos, as la relacin
inversa est dada por 1 = {(x, 1), (y, 1), (y, 5), (x, 7), (y, 7), (x, 9)}.

A. Caicedo B., G. Wagner de G., R. M. Mndez

24 RELACIONES Y GRAFOS

Composicin de Relaciones

Se pueden crear nuevas relaciones a partir de otras existentes, una forma de hacer esto es
mediante la composicin de relaciones.

Sea una relacin entre A y B y sea S una relacin entre B y C luego, la composi-
cin y S es la relacin entre A y C y se nota S y est dada por:
S = {(x, z) : x A, z C y existe y B tal que xy y ySz.

Grficamente se tiene:
S

b b
y z

b b

u w

A B C
Figura 6. S

De la figura anterior se deduce que la composicin de relaciones consiste en relacionar elementos de A

con elementos de C, usando elementos de B como intermediarios.

Ejemplo 16
Si se tiene en la figura 7 una composicin de relaciones, entonces
S = {(1, 2), (3, 2), (2, 2), (3, 3), (4, 2)}.
S
1
1 b b

2 2
2 b b b

3 3
3 b b b

4
4 b b

A B C
Figura 7.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Producto Lgico de Matrices 25

2.6 Producto Lgico de Matrices

Ahora se quiere definir una operacion matricial que combine la representacion matricial de dos relaciones
para obtener una representacin matricial de la composicin de relaciones.

Sea A = {a1 , a2 , ..., am }, B = {b1 , b2 , ..., bn } y C = {c1 , c2 , ..., cp }. Sea una relacin de A en B y
sea S una relacin de B en C. se representa por una matriz M1mn ; S se representa por la matriz
M2np , entonces la relacin compuesta S se representa por la matriz M3mp .

La operacin matricial que se busca para representar la composicin, se denota con el smbolo lo
cual permite escribir:
M3 = M1 M2
Para determinar ms fcilmente como est definida esta operacin, se puede considerar el esquema de las
dos relaciones dadas (ver figura 8).

Para cada i {1, ..., m} y j {1, ..., p}, M3 (i, j) = verdad si y solo si ai Scj lo cual es cierto si
y solo si k {1, ..., n} tal que ai bj y bk Scj .

Usando las definiciones de las operaciones lgicas y (and y or)1 se puede obtener la frmula co-
mo sigue:
M3 (i, j) = [M1 (i, 1) M2 (1, j)] [M1 (i, 2) M2 (2, j)] ... [m1 (i, n) M2 (n, j)]
La matriz M3 obtenida en esta forma se llama el producto lgico o booleano de las matrices M1 y M2 .

S
a1 b1 c1

a2 b2 c2

.. .. ..
. . .

ai bk cj

.. .. ..
. . .

am bn cp
Figura 8.

1
+/ 0 1 / 0 1
0 0 1 0 0 0
1 1 1 1 0 1

A. Caicedo B., G. Wagner de G., R. M. Mndez

26 RELACIONES Y GRAFOS

Definicin 2.8

Si Amp y Bpn son matrices booleanas se define: A B = [eij ] como el producto booleano de A y B,
donde
eij = (ai1 b1j ) (ai2 b2j ) ... (aip bpj )

Este producto booleano es similar al producto ordinario de matrices pero aplicando las operaciones booleanas
y .

Ejemplo 17
Sea A = {a, b}, B = {a, b, c} y C = {a, b, c, d}. es una relacin de A en B. = {(a, a), (a, b), (b, b)}. S una
relacin de B en C. S = {(a, a), (a, c), (a, d), (b, a), (c, b), (c, d)}, por lo tanto:

  1 0 1 1
1 1 0
M = , MS = 1 0 0 0
0 1 0
0 1 0 1
Entonces S = {(a, a), (a, c), (a, d), (b, a)} como se ve en el esquema de la figura 9
En forma matricial se tiene
  1 0 1 1
1 1 0
MS = M MS = 1 0 0 0
0 1 0
0 1 0 1
 
(1 1) (1 1) (0 0) . . . (1 1) (1 0) (0 1)
=
(0 1) (1 1) (0 0) . . . (0 1) (1 0) (0 1)
   
110 000 100 100 1 0 1 1
= =
010 000 000 000 1 0 0 0

Ntese que esta ltima matriz es equivalente a la matriz de la relacin representada en el esquema anterior.
A B C A C
a S S
a b b b
a a b b
a

bb b
b b
b
b b

cb b
c b
c

b
d b b b
d
Figura 9. S

El siguiente teorema establece algunas relaciones interesantes entre las matrices de relaciones y las operaciones
booleanas entre ellas.

Teorema 4

Sean y S dos relaciones en A, entonces se cumple que:

1. MS = M MS
2. MS = M MS
3. MS = M MS
4. (M )n = M... = M M . . . (n veces)

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Producto Lgico de Matrices 27

Ejemplo 18
1 0 1 0 1 1

Sean M = 1 0 0 y M S = 1 1 0, se tiene entonces,
1 1 1 0 1 0

1 1 1 0 0 1

MS = 1 1 0 , MS = 1 0 0
1 1 1 0 1 0

1 1 1 0 0 1

M MS = 1 1 0 , M MS = 1 0 0
1 1 1 0 1 0

Ejemplo 19
Si = {(a, b), (a, c), (b, a)}, S = {(a, c), (b, a), (b, b), (c, a)}, entonces

2 1 0

MS = M MS = M MS = 0 0 1
0 0 0

Ejemplo 20 A B C

1 a x

2 b y

3 c z

= {(1, b), (2, a), (2, c)}, S = {(a, y), (b, x), (c, y), (c, z)}

a b c x y z

1 0 1 0 a 0 1 0

M = 2
1 0 1
MS = b
1 0 0

3 0 0 0 c 0 1 1
x y z x y z

1 1 0 0 1 1 0 0

MS = 2
0 1 1
M MS = 2
0 2 1

3 0 0 0 3 0 0 0

Nota: MS y M MS tienen ceros en las mismas posiciones

A. Caicedo B., G. Wagner de G., R. M. Mndez

28 RELACIONES Y GRAFOS

2.7 Trayectorias y Relaciones

La idea de una trayectoria en un digrafo tiene muchas interpretaciones, dependiendo de la aplicacin que est
siendo modelada. Por ejemplo, si el digrafo es un modelo de una red de comunicacin, las trayectorias en el
digrafo mostrarn las posibles rutas para mensajes entre diferentes computadores. Hay tres problemas que surgen
al tratar de aplicar el modelo a la realidad:
1. Establecer la existencia de trayectorias entre dos nodos.
2. Contar el nmero de trayectorias entre dos nodos.
3. Encontrar la trayectoria ms corta entre un par de nodos dados.

Definicin 2.9
Sea una relacin en un conjunto A. Una trayectoria de longitud n de a hasta b es una sucesin finita
= a, x1 , x2 ,. . . xn1 , b que se inicia en a y termina en b, y tal que ax1 , x1 x2 ,. . . , xn1 b.

Una solucin al primer problema de determinar cules nodos estn conectados por trayectorias a otros nodos
puede ser establecida en dos formas: la primera analizando visualmente el grafo y determinando la trayectoria
y la segunda en trminos de la matriz de la relacin que representa los arcos del digrafo. El primer mtodo no
es prctico cuando el grafo tiene muchos nodos y arcos, razn por la cual en esta seccin, se har el estudio del
segundo mtodo.

Las trayectorias en una relacin pueden usarse para definir nuevas trayectorias. Si n es un entero positivo fi-
jo, se define una relacin n como xn y y significa que existe una trayectoria de longitud n de x a y en , o x
est relacionado con y mediante un recorrido de n arcos.

Recordando cmo se defini la composicin de relaciones, se concluye que la composicin de con si misma
da trayectorias de longitud 2, y la composicin de este resultado con da trayectorias de longitud 3 y as sucesi-
vamente. Luego se puede proceder con un argumento inductivo para encontrar todas las trayectorias.

Tambin se puede definir una relacin en A como x y indica que existe alguna trayectoria en de x
a y, no importa la longitud.

se le llama relacin de conectividad de . (clausurativa, transitiva)

Nota: M muestra quines quedan conectados mediante trayectorias de cualquier longitud

Ejemplo 21
Sea A un conjunto de personas y la relacin conocerse mutuamente, entonces:
ab significa que a y b se conocen el uno al otro.
a2 b significa que a y b tienen un conocido en comn.
an b significa que a conoce a x1 , que conoce a x2 ,. . . ,que conoce a xn1 , que conoce a b.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Trayectorias y Relaciones 29

Ejemplo 22
El siguiente grafo representa un conjunto de vuelos con escala intermedia.
5
1 2

3 4 6

Figura 10.

Luego:
12 5 porque 12 y 25
1 2 5
12 4 porque 12 y 24
22 5 porque 24 y 45
22 6 porque 25 y 56
32 5 porque 34 y 45
42 6 porque 45 y 56 3 4 6
2
Grafo de la relacin

Ejemplo 23
Para el grafo de la figura 11 determinar .

1 2

= {(1, 1) , (1, 2) , (1, 3) , (1, 4) , (2, 1) , (2, 2) , (2, 3) , (2, 4) , (3, 4)}

1 2 3 4

1 1 1 1 1
2 1 1 1 1
M =
3 0 0 0 1
3 4 4 0 0 0 0

Figura 11.

Ejemplo 24
1 2
= {(1, 2), (1, 3), (1, 4), (3, 2), (3, 3), (3, 4)}

1 2 3 4

1 0 1 1 1
20 0 0 0
M =
3 4 30 1 1 1
4 0 0 0 0

A. Caicedo B., G. Wagner de G., R. M. Mndez

30 RELACIONES Y GRAFOS

Teorema 5

Sea G = (N, A) un digrafo. Sea n1 , . . . , n2 nodos en A. Para cada i, j hay una trayectoria desde ni a nj
en G si y solo si existe k = 1, 2, 3, . . . tal que ni k nj , por lo tanto:
= 2 3 . . .

Teorema 6

Sea G = (N, A) un digrafo, una relacin en A y sea n = |N | entonces:

= 2 3 . . . n
es decir que las potencias de mayores que n no son necesarias para calcular .

Teorema 7

Para n 1 y una relacin en un conjunto finito A, se tiene:

Mn = M M . . . M
| {z }
n veces

Definicin 2.10
x y si y solo si xy o x2 y o x3 y o . . .

Del teorema anterior y teniendo en cuenta que MS = M MS se concluye que:

M = M M 2 M 3 . . . M n

que tambin se puede escribir de la forma:

M = M (M )2 (M )3 . . . (M )n

donde,
(M )n
= M . . . M (n factores)

Definicin 2.11
La relacin de accesibilidad o alcanzabilidad de una relacin en un conjunto N de n elementos se
define como x y si y solo si x = y o x y.

En otras palabras esto indica que un nodo y es alcanzable desde x si y es x o existe una trayectoria de cualquier
longitud desde x a y.

La matriz de la relacin de accesibilidad o alcanzabilidad o matriz de caminos se nota M .

Teorema 8

M = In M donde In es la matriz identidad de n n, luego:

M = In M M 2 . . . M n

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Trayectorias y Relaciones 31

Ejemplo 25
Para la relacin representada por el siguiente grafo, determinar cules parejas de nodos estn unidas por
trayectorias de longitud 2 arcos.
b d

c e
Solucin
Figura 12.
1. Analizando visualmente el grafo se tiene:
2 = {(a, a), (a, b), (a, c), (a, d), (b, d), (b, e), (c, d), (d, d)}
2. En una forma ms analtica y usando la matriz de relaciones se tiene:

1 1 0 0 0

0 0 1 1 0

M = 0 0 0 1 1

0 0 0 1 0
0 0 0 0 0

1 1 0 0 0 1 1 0 0 0 1 1 1 1 0

0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 matriz de

M2 = M M = 0 0 0 1 1 0 0 0 1 1 = 0 0 0 1 0 = caminos de

0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 longitud 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Ejemplo 26
Encontrar la matriz de alcance (conectividad) para el digrafo de la figura 13.
1 2

3 4

Figura 13.
Solucin
La matriz de la relacin en el digrafo es:

0 1 0 0

0 0 1 0
M =
1 0 0 0
1 0 0 0

a partir de ella se pueden calcular otros productos:

A. Caicedo B., G. Wagner de G., R. M. Mndez

32 RELACIONES Y GRAFOS

0 0 1 0 1 0 0 0

2 1 0 0 0 , 0 1 0 0
M2 = (M ) = M M = M3 = (M )3 = M2 M =
0 0 1 0 0 0 1 0
0 1 0 0 0 0 1 0

0 1 0 0

4 0 0 1 0
M4 = (M ) = M3 M =
1 0 0 0
1 0 0 0

La matriz de relacin de conectividad es

M = M M2 M3 M4

0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0

0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0
=
1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0
1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0

1 1 1 0

1 1 1 0
=
1 1 1 0
1 1 1 0

Teorema 9

Sea M la matriz de adyacencias de un digrafo G. El elemento de la i-sima fila y j-sima columna de M n

con n > 0 es igual al nmero de caminos de longitud n que van desde el i-simo nodo hasta el j-simo nodo

Ejemplo 27
Sea G el siguiente digrafo y su correspondiente matriz de adyacencias
v1 v2
0 0 0 1 1


0 0 1 0 0


v3 M = 0 1 0 0 0


0 1 1 0 1

v5 v4
1 1 0 0 0

Figura 14.
0 1 1 0 1

0 1 0 0 0 Los valores diferentes de 0, indican cuntas trayectorias de
M2 =

M M = 0 0 1 0 0 = longitud 2 existen entre cada par de nodos

1 2 1 0 0
0 0 1 1 0

1 2 1 0 0

0 0 1 0 0 Los valores diferentes de 0, indican cuntas trayectorias de
M3 = M2 M =

0 1 0 0 0 = longitud 3 existen entre cada par de nodos

0 1 2 1 0
0 2 1 0 1

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Algoritmo de Warshall 33

0 1 2 1 0

0 1 0 0 0 Los valores diferentes de 0, indican cuntas trayectorias de
M4 = M3 M =

0 0 1 0 0 = longitud 4 existen entre cada par de nodos

0 3 2 0 1
1 2 2 0 0

0 3 2 0 1

0 0 1 0 0 Los valores diferentes de 0, indican cuntas trayectorias de
M5 = M4 M =

0 1 0 0 0 = longitud 5 existen entre cada par de nodos

1 3 3 0 0
0 2 2 1 0

1 7 6 2 2
el elemento de la i-sima fila y j-sima
0 2 3 0 0 columna indica el nmero de trayecto-
T 5 = M + M 2 + M 3 + M 4 + M 5 = 0

3 2 0 0 = rias de longitud 5 o menor entre v y
i
2 10 9 1 2 v
j
2 7 6 2 1
Si un elemento de esta matriz no es nulo, queda claro que vj es alcanzable o accesable desde vi mediante una
trayectoria o camino de longitud mxima 5.

2.8 Algoritmo de Warshall

Como el clculo de M o matriz de alcanzabilidad es muy laborioso mediante la unin de potencias de la matriz
de adyacencias, o sea usando
M = M1 M2 Mn
Stephen Warshall propuso en 1962 el siguiente procedimiento para hallar la matriz de alcanzabilidad a partir de
la matriz de adyacencias de G.

Para un grafo G, sea M su matriz de adyacencias n n

Procedimiento
W =M
para k = 1 hasta n
para i = 1 hasta n
para j = 1 hasta n
hacer W (i, j) = W (i, j) [W (i, k) W (k, j)]

Definicin 2.12

Sea G = (N, A) un digrafo. Se define la familia de relaciones W (k) como sigue:

Sea v1 , v2 , . . ., vn un etiquetamiento de los vrtices y
1. Para u, v N decimos que u W (1) v si y slo si existe el arco (u, v) o existe una trayectoria de u a v
usando a v1 como vrtice intermedio.
2. Para u, v N decimos que u W (k+1) v si y slo si u W (k) v o existe una trayectoria de u a v usando
algn subconjunto de vrtices v1 , . . . , vk+1 como vrtices intermedios.

A. Caicedo B., G. Wagner de G., R. M. Mndez

34 RELACIONES Y GRAFOS

De esta definicin se deriva que W (n) = M = matriz de alcanzabilidad o accesibilidad. Si consideramos las
relaciones W (k) como conjuntos, se obtiene que:

W (1) W (2) . . . W (n)

as que cada sucesiva relacin contiene a las relaciones precedentes.

Ejemplo 28
Hallar la matriz M de alcanzabilidad para el siguiente digrafo, usando el algoritmo de Warshall

1 2
La matriz de adyacencias es
1 2 3 4

1 0 1 0 0
20 0 1 0
M=
31 0 0 0
3 4 4 1 0 1 0

Figura 15.

En este momento W = M y W ser modificado mediante el proceso iterativo que usa la frmula: nuevo
W (i, j) = W (i, j) [W (i, k) W (k, j)]
Proceso iterativo
Primera iteracin
Para k = 1 nodo intermedio

i = 1, j = 1 W (1, 1) = W (1, 1) [ W (1, 1) W (1, 1) ]

= 0 [ 0 0 ] =0
j=2 W (1, 2) = W (1, 2) [ W (1, 1) W (1, 2) ]
= 1 [ 0 1 ] =1
j=3 W (1, 3) = W (1, 3) [ W (1, 1) W (1, 3) ]
= 0 [ 0 0 ] =0
j=4 W (1, 4) = W (1, 4) [ W (1, 1) W (1, 4) ]
= 0 [ 0 0 ] =0
i = 2, j = 1 W (2, 1) = W (2, 1) [ W (2, 1) W (1, 1) ]
= 0 [ 0 0 ] =0
j=2 W (2, 2) = W (2, 2) [ W (2, 1) W (1, 2) ]
= 0 [ 0 1 ] =0
j=3 W (2, 3) = W (2, 3) [ W (2, 1) W (1, 3) ]
= 1 [ 0 0 ] =1
j=4 W (2, 4) = W (2, 4) [ W (2, 1) W (1, 4) ]
= 0 [ 0 0 ] =0
i = 3, j = 1 W (3, 1) = W (3, 1) [ W (3, 1) W (1, 1) ]
= 1 [ 1 0 ] =1
j=2 W (3, 2) = W (3, 2) [ W (3, 1) W (1, 2) ]
= 0 [ 1 1 ] =1
j=3 W (3, 3) = W (3, 3) [ W (3, 1) W (1, 3) ]
= 0 [ 1 0 ] =0
j=4 W (3, 4) = W (3, 4) [ W (3, 1) W (1, 4) ]
= 0 [ 1 0 ] =0
i = 4, j = 1 W (4, 1) = W (4, 1) [ W (4, 1) W (1, 1) ]
= 1 [ 1 0 ] =1
j=2 W (4, 2) = W (4, 2) [ W (4, 1) W (1, 2) ]
= 0 [ 1 1 ] =1
j=3 W (4, 3) = W (4, 3) [ W (4, 1) W (1, 3) ]
= 1 [ 1 0 ] =1
j=4 W (4, 4) = W (4, 4) [ W (4, 1) W (1, 4) ]
= 0 [ 0 0 ] =0

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Algoritmo de Warshall 35

Se ha obtenido la siguiente matriz

1 2 3 4

1 0 1 0 0 Los unos de esta matriz indican cules parejas de nodos estn
2 0 0 1 0 comunicados directamente por un arco o usando al nodo v1
W (1) =
3 1 1 0 0 como nodo intermedio.
4 1 1 1 0
Segunda Iteracin
Para hallar W (2) partimos con todas las trayectorias encontradas en W (1) y establecemos las trayectorias
que usan a v1 y v2 como nodos intermedios.
Para k = 2 y usando los valores de W (1) ejecutamos el mismo proceso iterativo y se obtiene:
1 2 3 4

1 0 1 1 0 Los unos de esta matriz indican cuales parejas de nodos estn
(2) 2 0 0 1 0 comunicados directamente por un arco o por una trayectoria
W =
que usa los nodos v1 y v2 como nodos intermedios
3 1 1 1 0
4 1 1 1 0
Tercera Iteracin
Para k = 3 y usando los valores de W (2) , ejecutamos el mismo proceso iterativo y se obtiene:
1 2 3 4

1 1 1 1 0 Los unos de esta matriz indican cuales parejas de nodos estn
(3) 2 1 1 1 0 conectados directamente por un arco o por una trayectoria
W =
que usa los nodos v1 , v2 y v3 como nodos intermedios.
3 1 1 1 0
4 1 1 1 0
Cuarta Iteracin
Para k = 4 y usando los valores de W (3) y ejecutando el mismo proceso iterativo se obtiene:

1 2 3 4

1 1 1 1 0
2 1 1 1 0
W (4) = = Matriz de alcanzabilidad
3 1 1 1 0
4 1 1 1 0

Obsrvese que W (3) = W (4) porque el nodo 4 es un nodo fuente, l no recibe ningn arco, entonces no se
pueden establecer nuevas trayectorias. El proceso se detiene cuando:
1. W k1 = W k
2. W k = matriz de unos
3. W k = W n
Trayectorias de acceso o alcanzabilidad

W (4) (1, 1) = 1 Trayectoria de acceso: 1231

W (4) (1, 2) = 1 Trayectoria de acceso: 12
W (4) (1, 3) = 1 Trayectoria de acceso: 123
W (4) (2, 1) = 1 Trayectoria de acceso: 231
W (4) (2, 2) = 1 Trayectoria de acceso: 2312
W (4) (2, 3) = 1 Trayectoria de acceso: 23
W (4) (3, 1) = 1 Trayectoria de acceso: 31
W (4) (3, 2) = 1 Trayectoria de acceso: 312
W (4) (3, 3) = 1 Trayectoria de acceso: 3123
W (4) (4, 1) = 1 Trayectoria de acceso: 41
W (4) (4, 2) = 1 Trayectoria de acceso: 4312
W (4) (4, 3) = 1 Trayectoria de acceso: 43

A. Caicedo B., G. Wagner de G., R. M. Mndez

36 RELACIONES Y GRAFOS

Ejercicios Captulo 2

1. Sea A el conjunto de los nmeros reales. Se define la siguiente relacin en A: xy si y solo si x e y

satisfacen la ecuacin
x2 y2
+ =1
16 81
Establecer el dominio y el codominio de .
2. Dada la relacin = {(1, 3), (4, 5), (7, 9), (8, 20)} establecer su dominio y codominio.
3. Para la siguiente relacin = {(a, 3), (b, 5), (c, 7)} establecer la matriz de la relacin.
4. Sean A = {7, 10, 4, 12}, B = {3, 8, 5} y la relacin AB a < b. establecer el conjunto de parejas que
conforman a y la matriz de .
5. Trazar el grafo que represente cada una de las relaciones de los ejercicios 2, 3 y 4.
6. La siguiente es la matriz de una relacin ,

1 0 1 1


M = 1 1 0 0

0 0 1 0

establecer la relacin en forma de conjunto de parejas y trazar el grafo orientado correspondiente.

7. Dada la siguiente matriz de una relacin
x y z

a 1 0 1
M = b 1 1 1
c 0 1 1
establecer:

a) Dom()
b) Cod()
c) Conjunto de parejas.
d ) Trazar el grafo correspondiente.

8. Sean A = {1, 2, 3, 4, 8}, B = {1, 4, 6, 9} y la relacin ab si y solo si a es un divisor de b (a|b). Establecer el

conjunto de parejas de y trazar el grafo.
9. Sean A = {1, 2, 3, 4, 5}, B = {5, 2, 1, 4, 10} y la relacin ab si y solo si a es un mltiplo de b. Establecer el
conjunto de parejas de y trazar el grafo.
10. Sea A = {1, 2, 3, 4}. Encontrar la relacin en A determinada para la siguiente matriz:

1 1 0 1

0 1 1 0
M =
0 0 1 1
1 0 0 0
11. Dado el grafo de la figura 16, determinar:

a) M .
b) Conjunto de parejas.
c) Dominio y codominio de .

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Algoritmo de Warshall 37

4 2
1

5 3
Figura 16.
12. Sea A = {1, 2, 3, 4} y la relacin dada por:

= {(1, 1) , (1, 2) , (2, 1) , (2, 2) , (3, 4) , (4, 3) , (3, 3) , (4, 4)}

verificar que es una relacin de equivalencia.

13. Sea A el conjunto de enteros positivos y la relacin:

ab a b (mod 2)

Mostrar que es una relacin de equivalencia.

14. Determinar si las relaciones dadas por los siguientes grafos son reflexiva, irreflexiva, simtrica, asimtrica
o transitiva.
2 1 2

1 5 3 5

4 3 4
Figura 17.
15. En los ejercicios de a hasta h, determinar si la relacin sobre el conjunto A es reflexiva, irreflexiva,
simtrica, asimtrica o transitiva.
a) A = Z; ab a b + 1
b) A = Z+ ; ab a = bn , n Z+
c) A = Z; ab |a b| = 4
d ) A = Z+ ; ab |a b| 2
e) A = Z; ab a + b es par
f ) A = Z; ab a + b es impar
g) A = Z; ab a b es par
h) A = Z; ab a b es impar
16. Sea A = {x, y, z} . Determinar si la relacin cuya matriz M se muestra a continuacin, es una relacin
de equivalencia.
1 0 1


M = 0 1 1

0 1 1

A. Caicedo B., G. Wagner de G., R. M. Mndez

38 RELACIONES Y GRAFOS

17. Para los ejercicios de a hasta e, considere la relacin cuyo grafo dirigido se ilustra en la figura 18.

1 2 7

3 6
4

5
Figura 18.

a) Listar todas las trayectorias de longitud 3 que se inicien en el nodo 1.

b) Encontrar un ciclo que se inicie en el nodo 2.
c) Trazar el grafo dirigido de 2 .
d ) Encontrar M2 , y M .
e) Encontrar todas las trayectorias de longitud 4 que se inicien en el nodo 4.

18. Sean y S las siguientes relaciones sobre A = {1, 2, 3, 4}

S = {(2, 1) , (3, 3) , (3, 4) , (4, 1) , (4, 2)} y

= {(1, 1) , (1, 3) , (3, 2) , (3, 4) , (4, 2)}

Encontrar cada una de las siguientes relaciones compuestas:

a) S
b) S
c)
d) S S
19. Para las relaciones del ejercicio 18 hallar:
a)
b) S
c) 1
d ) S 1
20. Aplicar el algoritmo de Warshall para hallar la matriz de alcanzabilidad del siguiente grafo

1 2 3

4 5

Figura 19.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 ulo
pt
Ca

3 CONEXIDAD

El concepto de conexidad en la teora de grafos es uno de los conceptos ms importantes

y de mayor aplicabilidad. Para desarrollar este concepto se hace uso de otros que ya fueron
tratados en la unidad anterior, tales como trayectoria y ciclo o circuito.

Como en la mayora de las situaciones de optimizacin en redes y rboles se requiere

que el grafo o red inicial sea conexa, es conveniente establecer un algoritmo que determine si
un grafo es conexo o n. Este es el propsito central de la presente unidad.

3.1 Grafo Conexo

Definicin 3.1 Grafo Conexo

Un grafo se dice ser conexo si para cada par de vrtices x e y existe una trayectoria desde x hasta
y la cual use mximo n-1 arcos.

Un grafo conexo consiste de una sola pieza, mientras que un grafo que no es conexo consiste de dos o ms
piezas. Estas piezas son subgrafos del grafo original y son llamadas componentes.

Definicin 3.2 Grafo Fuertemente Conexo

Un grafo orientado es fuertemente conexo si para cada par de vrtices x e y existe una trayectoria
desde x hasta y y una trayectoria desde y hasta x. Las trayectorias pueden ser diferentes

Definicin 3.3 Grafo Dirigido Conexo

Un grafo dirigido es llamado conexo si para cada par de vrtices x e y existe una trayectoria desde
un nodo al otro.

Sea M una matriz de adyacencias del grafo G donde cada elemento mij de M es de la forma
(
1, si existe el arco (i, j)
mij =
0, si no existe el arco (i.j)

39
40 CONEXIDAD

Al efectuar M M = M 2 sus entradas indicarn el nmero de trayectorias diferentes que existen entre
cada par de nodos y que tengan longitud de 2 arcos. Similarmente en M 2 M = M 3 sus entradas
indicarn el nmero de trayectorias diferentes que existen entre cada par de nodos y que tienen longitud
de tres arcos.

En al menos una de las matrices M, M 2 , . . . , M n1 habr una entrada no cero en la (i, j) esima
posicin si existe una trayectoria entre i y j.

Al formar la matriz C = M + M 2 + M 3 + . . . + M n1 , sta tendr una entrada cero para cualquier

nodo que no est conectado a otro. Si C es totalmente no cero entonces el grafo es conexo.

A partir de la matriz de adyacencias se puede determinar si un grafo es conexo o n siguiendo el al-

goritmo que a continuacin se describe.

3.2 Algoritmo para Conexidad

paso 0. Entrar la matriz de adyacencias M.

Hacer n el nmero de nodos.

paso 1. Hacer C = M
Hacer I = 1

paso 2. Si C tiene todas las filas libres de ceros ejecutar paso 4, en caso contrario continuar.

paso 3. Hacer I = I + 1
Si I = n, ejecutar paso 5, en caso contrario hacer C = C + M I y regresar al paso 2.

paso 4. Parar, Imprimir el grafo es conexo.

paso 5. Parar, Imprimir, el grafo no es conexo.

Ejemplo 1
Usando el algoritmo anterior, determinar si el grafo de la figura 1 es conexo

1 3
4

5 6

Figura 1.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Algoritmo para Conexidad 41

Solucin
Paso 0. Matriz de adyacencias. n = 6.

0 1 0 1 0 0

1 0 1 0 0 0

0 1 0 0 1 1
M =
1 0 0 0 1 0

0 0 1 1 0 1
0 0 1 0 1 0

paso 1. Hacer C = M , I = 1
paso 2. C no tiene todas las filas libres de cero. Continuar
paso 3. Hacer I = I + 1 = 2 I 6= n, hacer C = C + M2 .

0 1 0 1 0 0 2 0 1 0 1 0 2 1 1 1 1 0

1 0 1 0 0 0 0 2 0 1 1 1 1 2 1 1 1 1

0 1 0 0 1 1 1 0 3 1 1 1 1 1 3 1 2 2
C= + =
1 0 0 0 1 0 0 1 1 2 0 1 1 1 1 2 1 1

0 0 1 1 0 1 1 1 1 0 3 1 1 1 2 1 3 2
0 0 1 0 1 0 0 1 1 1 1 2 0 1 2 1 1 2

paso 2. C no tiene todas las filas libres de cero. Continuar

paso 3. Hacer I = I + 1 = 3 I 6= n, Hacer C = C + M 3.

2 1 1 1 1 0 0 3 1 3 1 2 2 4 2 4 2 2

1 2 1 1 1 1 3 0 4 1 2 1 4 2 5 2 3 2

1 1 3 1 2 2 1 4 2 2 5 4 2 5 5 3 7 6
C= + =
1 1 1 2 1 1 3 1 2 0 4 1 4 2 3 2 5 2

1 1 2 1 3 2 1 2 5 4 2 4 2 3 7 5 5 6
0 1 2 1 1 2 2 1 4 1 4 2 2 2 6 2 6 4

paso 2. C tiene todas las lneas libres de cero. Ir al paso 4.

paso 4. Parar. Imprimir el grafo es conexo.

Cuando se hace mencin a la frase est conectado por una trayectoria, se est definiendo una relacin
sobre el conjunto de los vrtices de un grafo. Para un grafo no dirigido, la relacin bajo A (un conjunto
de arcos) es simtrica, entonces, es simtrica y transitiva. Asumiendo que cada vrtice est conectado
a si mismo por una trayectoria de longitud cero, entonces es reflexiva. Luego es una relacin de
equivalencia.

El conjunto de vrtices puede ser particionado en clases de equivalencia.

Dado que en cada clase de equivalencia todas las aristas estn conectando sus vrtices, se pueden construir
subgrafos de G, los cuales se llaman componentes de conectividad o simplemente componentes conexas
del grafo.

A. Caicedo B., G. Wagner de G., R. M. Mndez

42 CONEXIDAD

Definicin 3.4
Sea el grafo G (N, A) y ni N uno de los nodos. Se denota Cni el conjunto formado por el nodo
ni y todos los nodos de G ligados a ni , por una trayectoria.

Definicin 3.5
Se llama componente conexa de G a un subgrafo de G engendrado por un conjunto de la forma
Cni .

Ejemplo 2
En el grafo siguiente las dos subgrficas son componentes conexas del grafo dado.
2
4

1 3 6

Figura 2.

Definicin 3.6
El nmero de componentes de un grafo G es llamado el nmero de conectividad de G y es notado
por C (G) .

Teorema 1

G es conexo si y solo si C (G) = 1.

3.3 Algoritmo para Grafos no Dirigidos

El siguiente algoritmo calcula el nmero de conectividad C (G) de un grafo G.

Sea G (N, A) un grafo no dirigido. Sea C (G) el nmero de conexidad de G. El procedimiento es el

siguiente:

Se parte de cualquier nodo y se procede a encontrar todos los nodos que son vecinos al nodo origi-
nal. Luego se procede a encontrar todos los vecinos de ellos y as sucesivamente hasta que no haya ms
vecinos. Esto significa que se ha encontrado una componente completa. Luego se salta a la siguiente
componente y se ejecuta el mismo procedimiento. Como el grafo es finito, entonces eventualmente todos
los nodos son alcanzados.
A. Caicedo B., G. Wagner de G., R. M. Mndez
 Algoritmo para Grafos no Dirigidos 43

ALGORITMO
Inicio
N N
C0
mientras N 6= haga
inicio
Escoger n N
Encontrar todos los nodos conectados a n y guardarlos en W
Remover todos estos nodos de N , es decir, hacer N = N W
C =C +1
Terminar
Terminar

Ejemplo 3
Aplicar el algoritmo anterior al grafo de la figura 3.

2 5 6 7

1 3 10
b

8
4 9
Figura 3.
SOLUCIN
N = {1, 2, . . . , 10} C = 0
Primera iteracin:
N 6= continuar
Escoger n = 5 arbitrariamente
W = {5, 6, 7, 8, 9} nodos conectados a n (componente)
N = N W = {1, 2, 3, 4, 10}
C =0+1=1
Segunda iteracin
N 6= continuar
Escoger n = 1 arbitrariamente
W = {1, 2, 3, 4} nodos conectados a n (componente)
N = N W = {10}
C =1+1=2
Tercera iteracin
N 6= continuar
Escoger n = 10 arbitrariamente
W = {10} nodos conectados a n (componente)
N = N W =
C =2+1=3
Cuarta iteracin
N = Parar
No se pudieron visitar todos los nodos, entonces el grafo no es conexo.

A. Caicedo B., G. Wagner de G., R. M. Mndez

44 CONEXIDAD

Ejercicios Captulo 3

1. Use el algoritmo de conexidad para determinar si el grafo cuya matriz de adyacencias que se da a
continuacin, es conexo o n.
0 0 1 0 0

0 0 0 1 0

1 0 0 0 1

0 1 0 0 1
0 0 1 1 0

2. Por simple inspeccin determinar cul es el arco que hace que el siguiente grafo sea conexo
b b

b b b

b b

Figura 4.

3. Verificar si los siguientes enunciados son ciertos o no.

a) Un grafo con A N es conexo.
b) Un grafo con A V 2 no es conexo.
c) Un grafo que contiene un ciclo permite la remocin de algn arco y sigue siendo conexo.
4. Use el algoritmo anterior para verificar si el grafo de la figura 5 es conexo o no.
c
b

d
Figura 5.

5. Aplique un algoritmo para mostrar si el siguiente grafo no dirigido es conexo o no.

a b

e
c

d f
Figura 6.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 ulo
pt
Ca

4 CIRCUITO EULERIANO

Cuando se posee una red no dirigida conexa se puede disear un circuito que recorra todos
sus nodos, partiendo de un nodo especfico y regresando a l, pero sin pasar ms de una vez
por cada arco, adems escogiendo el circuito de forma tal que el recorrido sea mnimo.

Este tipo de problema se resuelve hallando un circuito euleriano de longitud mnima.

4.1 Circuito de Euler

Definicin 4.1 Circuito Euleriano

En una red conexa, un circuito que recorra todos los nodos y todos los arcos pasando una vez por
cada arco, se llama circuito euleriano.

Si la red no es conexa puede ocurrir que no exista un circuito euleriano.

Definicin 4.2 Trayectoria Euleriana

Una trayectoria euleriana es una trayectoria que incluye cada arco exactamente una sola vez.

El problema de determinar un circuito euleriano de longitud mnima de una red conexa, tambin es
llamado El Problema del Cartero o Problema Chino del Cartero el cual apareci formulado por primera
vez por M. K. Kwan en el Chinese Mathematical Journal. Sus orgenes se remontan a 1736 cuando
Leonard Euler estudi el problema de los puentes de Knigsberg.

4.1.1. Puentes de Knigsberg

La ciudad de Knigsberg, situada en Prusia Oriental, en la poca de Euler (1707-1783) y hoy perteneciente
a Rusia con el nombre de Kaliningrado es atravesada por el ro Pregel o Pregolia. La parte central de la
ciudad se encuentra sobre una isla del ro llamada Kniphof que se une a las dos orillas por cuatro puentes,
dos a cada lado; un quinto puente une a Kniphof con otra isla que tambin est unida a las orillas por
dos puentes, uno hacia cada orilla.
45
46 CIRCUITO EULERIANO

Figura 1. Puentes de Knigsberg

En aquella poca alguien propuso el siguiente problema: Ser posible, en una sola caminata, pasar por
los siete puentes sin cruzar ninguno de ellos dos veces?. En la ciudad de San Petesburgo, entonces capital
de Rusia, el matemtico suizo Leonard Euler, analiz el problema y escribi un trabajo que present a
la Academia Rusa de Ciencias. Este trabajo demostr que el problema tal como haba sido propuesto no
tiene solucin.

El problema lo esquematiz en un grafo donde sustituy las porciones de tierra por puntos o nodos
y los puentes por lneas o arcos como se muestra en la figura 2.

B D

C
Figura 2.

Bajo esta simplificacin el problema se resuma en coger un lpiz y a partir de un nodo del grafo y sin
levantarlo, tratar de recorrer todo el grafo sin repetir arco. Esto equivaldra a atravesar fsicamente los
siete puentes del problema, donde el concepto recorrer el grafo es pasar todos los arcos solamente una
vez y regresar al punto de partida.

En su trabajo Euler descubri que un grafo puede ser recorrido (cruzado) si todos sus nodos son pares.
Obsrvese que en el grafo de los puentes todos los nodos son de grado impar.

Para iniciar el proceso de hallar un ciclo euleriano en una red conexa, son de gran ayuda los siguientes
teoremas:

Teorema 1

G es un gafo conexo y de grado par si y solo si G tiene un ciclo euleriano.

Teorema 2

Un grafo conexo es euleriano si y solo si cada nodo tiene grado par.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Circuito de Euler 47

Definicin 4.3
Una red par es aquella en la cual el nmero de arcos que inciden a todos y cada uno de los nodos
es par.

Corolario

Un grafo conexo contiene una trayectoria euleriana, pero no un ciclo euleriano, si y solo s
exactamente dos nodos tienen grado impar. La trayectoria debe comenzar en un nodo impar y
terminar en otro nodo impar.

Ejemplo 1
Si en el grafo de los puentes se retira el arco BD, solamente los nodos A y C sern de grado impar
y el grafo podr cruzarse pero no se lograr regresar al punto de partida (figura 3a). Si se agrega
un nuevo arcoAC, solamente los nodos B y D sern impares y se podr cruzar el grafo pero no se
podr regresar al punto de partida (figura 3b). Si se hacen conjuntamente los dos casos anteriores
(retirar el arco BD y agregar el arco AC) todos los nodos quedan de orden par y el grafo podr ser
recorrido y regresar al nodo de partida (figura 3c).

A A A

B D B D B D

C C C

a) b) c)
Figura 3.

Con relacin al corolario anterior se puede afirmar que la trayectoria euleriana empieza en un nodo impar
y termina en el otro nodo impar.

De acuerdo a estos teoremas, si el grafo es par entonces la solucin ptima al problema del cartero
es un ciclo euleriano. El cartero no tiene que repetir ningn arco.

Para una red par la bsqueda de un ciclo euleriano se puede desarrollar en la siguiente forma:
1. Dividir el conjunto de datos en dos subconjuntos: uno que contenga los arcos usados en el circuito
y otro que contenga los no usados. Inicialmente todos los arcos estn en el segundo conjunto.
2. El circuito es construido transfiriendo arcos del segundo conjunto al primero a medida que se van
usando.
3. Partiendo de un nodo origen cualquiera se selecciona un arco no usado que sea incidente a ese nodo
origen. Este arco se considera usado y se transfiere del segundo conjunto al primero.
4. Se repite el proceso hallando un nuevo arco no usado incidente al ltimo nodo del arco anterior
usado. As el circuito se construye arco por arco, hasta que eventualmente se regresa al nodo origen.
A. Caicedo B., G. Wagner de G., R. M. Mndez
48 CIRCUITO EULERIANO

El siguiente algoritmo se basa en los conceptos anteriores y permite hallar un circuito de Euler de longitud
mnima en redes conexas de orden par.

4.2 Algoritmo de Euler

Paso 0. Determinar el orden de cada nodo del grafo G = (N, A). Hacer S el conjunto de todos los
nodos de orden impar. Si S es vaco ejecutar el paso 1.
Paso 1. Hallar un ciclo euleriano:

a. Marcar el origen del ciclo con s y el ltimo nodo visitado con t. Hacer U = conjunto
de arcos que van a formar el ciclo parcial. Hacer V = conjunto de arcos que forman
ciclos parciales empezando en s.

b. Escoger cualquier arco entre t y q que est sin usar, marcarlo como usado y adicionarlo
a U. Hacer t = q.

c. Si t diferente de s, repetir paso 1b, en caso contrario continuar.

d. Inserta U en V , en el punto donde el nodo s es alcanzado por primera vez. U queda

vaco. Encontrar un nodo t que est visitado en V pero que tenga arcos incidentes no
usados. Si tal nodo no existe PARAR. En caso contrario hacer s = t y repetir paso 1b.

Ejemplo 2
Hallar la trayectoria del cartero para el grafo de la figura 4 aplicando el algoritmo anterior.

3
4

6 5 1
2

3
3 4

5
Figura 4.

paso 0. La matriz de distancias es

0 4 2
4 0 5 3 6

D=2 5 0 3 7
3 3 0
6 7 0

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Algoritmo de Euler 49

El grado de los nodos es:

nodo 1 grado 2
nodo 2 grado 4
nodo 3 grado 4
nodo 4 grado 2
nodo 5 grado 2
No hay nodos de grado impar. S = 0, ejecutar paso 3.

paso 1. Hallar un ciclo euleriano de G.

1a. Hacer s = 1 y t = s. U = V = . Todos los arcos de A estn sin usar.
1b. Escoger el arco (1, 2) y marcarlo como usado. U = {(1, 2)}, t = 2.
1c. An t diferente de s, repetir paso 1b.
1b. Escoger el arco (2, 5) y marcarlo como usado. U = {(1, 2)(2, 5)}, t = 5
1c. An t diferente de s, repetir paso 1b.
1b. Escoger el arco (5, 3) y marcarlo como usado. U = {(1, 2)(2, 5)(5, 3)}, t = 3
1c. An t diferente s, repetir paso 1b.
1b. Escoger el arco (3, 1) y marcarlo como usado. U = {(1, 2)(2, 5)(5, 3)(3, 1)}, t = 1.
1c. Ahora t = s. continuar
1d. Insertar U en V . Como V = entonces:
V = U = {(1, 2)(2, 5)(5, 3)(3, 1)}. Hacer U =
En V hay dos nodos que tienen arcos incidentes no usados:
Nodo 2 tiene 2 arcos no usados: (3, 2), (4, 2).
Nodo 3 tiene 2 arcos no usados: (2, 3), (4, 3).
Escoger uno de estos nodos y hacerlo igual a t. Sea t = 2 = s. Repetir paso 1b
1b. Escoger el arco (2, 4) y marcarlo como usado. U = {(2, 4)}, t = 4.
1c. An t es diferente de s repetir paso 1b.
1b. Escoger el arco (4, 3) y marcarlo como usado. U = {(2, 4)(4, 3)}, t = 3.
1c. An t es diferente de s repetir paso 1b.
1b. Escoger el arco (3, 2) y marcarlo como usado. U = {(2, 4)(4, 3)(3, 2)}, t = 2.
1c Ahora t = s, continuar.
Insertar U en V en la posicin donde se encuentre t por primera vez
V = {(1, 2), U, (2, 5)(5, 3)(3, 1)}
V = {(1, 2)(2, 4)(4, 3)(3, 2)(2, 5)(5, 3)(3, 1)}
Hacer U =
En V ya no hay nodos con arcos incidentes sin usar. PARAR. El ciclo ptimo es

V = {(1, 2)(2, 4)(4, 3)(3, 2)(2, 5)(5, 3)(3, 1)}

Long(V ) = 4 + 3 + 3 + 5 + 6 + 7 + 2 = 30

Si el grafo es conexo y de orden par, el paso 1 del algoritmo anterior se puede reemplazar por el siguiente
procedimiento:

A. Caicedo B., G. Wagner de G., R. M. Mndez

50 CIRCUITO EULERIANO

paso 0. Verificar que el grafo G = (N, A) es conexo con todos los nodos de orden par.
paso 1. Hacer C = {x} con x N (un nodo arbitrario),
paso 2. Mientras |A(G)| > 0 hacer:
begin
paso 3. Escoger x en N (C) con grado mayor de 0, y que no haya sido escogido con anterio-
ridad.
paso 4. Crear un ciclo D mximo simple que comience en x
paso 5. Hacer A(G) = A(G) A(D)
paso 6. Hacer C = ciclo obtenido desde C al insertar D en la posicin x.
end.
paso 7. Tomar C como el ciclo euleriano. Parar.

Ejemplo 3
Aplicar el procedimiento anterior para establecer si el grafo de la figura 5 contiene un ciclo euleriano.
1 2 9 3 4

8 7 6 5
Figura 5.

Obsrverse que el grafo tiene todos sus nodos de grado par.

La aplicacin sucesiva del algoritmo se muestra en la siguiente tabla, escogiendo el nodo 9 como nodo
inicial y N = {1, 2, 3, 4, 5, 6, 7, 8, 9}

Paso X C D |A(G)| > 0 A(G)

1 9 {9}
2 si
3 9
4 {9, 6, 7, 9}
5 11 3 = 8
6 {9, 6, 7, 9}
2 si
3 6
4 {6, 3, 4, 5, 6}
5 84=4
6 {9, 6, 3, 4, 5, 6, 7, 9}
2 si
3 7
4 {7, 2, 1, 8, 7}
5 44=0
6 {9, 6, 3, 4, 5, 6, 7, 2, 1, 8, 7, 9}
2 no parar

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Algoritmo de Euler 51

Ejercicios Captulo 4

1. Aplicar el algoritmo general de Euler para hallar un circuito euleriano en el grafo de la figura 6,
usando el nodo a como nodo inicial.
a

d c e

f g
Figura 6.

2. Mostrar que el grafo de la figura 7 tiene una trayectoria euleriana, pero no un circuito euleriano.
Construir la trayectoria.
a

b c

d e
Figura 7.

3. Mostrar que el grafo de la figura 8 no tiene trayectoria euleriana.

Figura 8.

4. Un ingeniero supervisor de carreteras tiene asignado un circuito vial que debe revisar una vez por
semana para informar sobre el estado de dichas vas. El circuito vial es el de la figura 9
2
10 12
20 14
1 3 4

18
9 18
25
5
7 6 11
10 Figura 9.

A. Caicedo B., G. Wagner de G., R. M. Mndez

52 CIRCUITO EULERIANO

El ingeniero tiene su sede en la ciudad 1 y debe planear su recorrido en forma tal que recorra todas
las carreteras de la red vial con el mnimo de distancia recorrida.

5. En una red de estaciones repetidoras se emite una seal de prueba de la estacin R1, la seal debe
llegar a todas las otras estaciones; cada estacin la replica a la estacin ms cercana, hasta que la
seal regresa a R1. Determinar la trayectoria seguida por la seal de prueba si la red de repetidoras
es la mostrada en la figura 10.
R2
20
35
18
R1 30
R4 R3
30 80
26
24 30
32

R5 R6
35
72

Figura 10.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 ulo
pt

5
Ca

CICLO HAMILTONIANO

Cuando se tiene un grafo conexo no dirigido G = (N, A) puede ocurrir que se desea hacer
un recorrido por el grafo, que pase por todos lo nodos, sin repetir nodo y regresar al nodo de
partida. Tal tipo de recorrido se define como un ciclo o circuito hamiltoniano.
El nombre de este tipo de ciclo se ha dado en honor al matemtico irlands Sir William Rowan
Hamilton (1805-1865), quien fue el primero que los estudi en 1857.
Si el grafo G tiene asociados a sus arcos valores que pueden ser las distancias entre los nodos
o el costo de recorrer dichas distancias, es de inters hallar un circuito que recorra todos los
nodos una sola vez, y que tenga distancia mnima o costo mnimo. Este problema ha sido
formulado desde hace mucho tiempo con el nombre de: Problema del Agente Viajero.

5.1 Ciclo de Hamilton

Definicin 5.1

En un grafo G = (N, A), una trayectoria (o ciclo) que contenga exactamente n 1 arcos y recorra
todos los nodos, es llamado hamiltoniana. Un grafo es llamado hamiltoniano si contiene un ciclo
hamiltoniano.

No hay una regla simple para determinar la existencia de un circuito hamiltoniano como si la hay para
circuitos eulerianos. Es cierto que un grafo con circuito hamiltoniano es conexo, pero no cada grafo conexo
tendr un circuito hamiltoniano.
Si un grafo representa un conjunto de ciudades a ser visitadas, luego una trayectoria que visite cada
ciudad exactamente una sola vez es un circuito hamiltoniano. Asumiendo que cada ciudad est conectada
por un arco a cada una de las otras ciudades, siempre habr un circuito hamiltoniano.

Teorema 1 De Dirac

Si G tiene n mayor o igual a 3 nodos y cada nodo tiene grado al menos n/2, entonces G es
hamiltoniano.

Teorema 2 de la existencia de las trayectorias

Sea G un grafo conexo sin lazos, con n nodos, n 3. Si x, y N, x 6= y, grad(x)+grad(y) n1,

entonces G tiene una trayectoria Hamiltoniana

53
54 CICLO HAMILTONIANO

Ejemplo 1 1 2 3

5 4
Figura 1.

Obsrvese que para cualquier par de nodos que se escoja, se cumple que la suma de los grados es
n 1, por lo tanto el grafo tiene una trayectoria Hamiltoniana, sta podra ser 1 4 3 2 5.

Basado en el teorema anterior De Dirac, se obtiene el siguiente algoritmo

5.2 Algoritmo Hamiciclo

paso 1 Entrar el grafo G con N nodos todos de grado N/2

paso 2 Hacer P = (trayectoria vaca)
paso 3 Repita Hasta |N (c)| = N
begin
paso 4. Escoger z {N (G) N (P )}. P trayectoria maximal que contiene a N (P ) y a z
paso 5. Hallar C un ciclo sobre N (P )
end
paso 6 Imprimir C y parar.

Ejemplo 2
Aplicar el algoritmo anterior al grafo de la figura 2 para hallar un ciclo hamiltoniano C
u

x v t w y

Figura 2.
Solucin
El seguimiento del algoritmo se muestra en la tabla siguiente:

paso z P C |N (C) = N |
2
4 x {x, v, t, w, y}
5 {x, t, w, y, v, x} no
4 u {u, t, w, y, v, x}
5 {u, w, y, v, x, t, u} si
6 {u, w, y, v, x, t, u} parar

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Problema del Agente Viajero 55

5.3 Problema del Agente Viajero

Sea G = (N, A) un grafo conexo cuyos nodos representan ciudades y sus arcos representan las carreteras
que unen cada par de ciudades. El valor asociado a cada arco d(x, y) 0 es la distancia entre ellas. Un
agente viajero desea escoger una ruta que le permita visitar cada ciudad una sola vez y retornar a la
ciudad de origen cubriendo el mnimo de distancia.

Planteado en esta forma, el problema del agente viajero es equivalente a hallar un ciclo hamiltoniano
con la distancia mnima o costo mnimo

Un circuito hamiltoniano con la menor longitud total es llamado un ciclo hamiltoniano ptimo y es
una solucin ptima al problema del agente viajero.

Un circuito ptimo para el problema del agente viajero no necesariamente es un circuito hamiltonia-
no ptimo como se observa en el siguiente grfico.

b
2

2
15
a 4

4 c
Figura 3.

El nico circuito hamiltoniano en este grafo es:

(a, b)(b, c)(c, a)

con una longitud total de 2 + 15 + 4 = 21 unidades, mientras que para el agente viajero lo ms econmico
sera hacer el siguiente recorrido:
(a, b)(b, a)(a, c)(c, a)
con longitud total 2 + 2 + 4 + 4 = 12 unidades. Este circuito no es hamiltoniano pero es una solucin
ptima para el agente viajero.

Para resolver situaciones como la anterior se ha establecido una condicin de optimizacin, expresa-
da en el siguiente teorema:

Teorema 3

Si para cada par de nodos x e y en el grafo G se cumple que d(x, y) d(x, z) + d(z, y) z
G, z 6= x 6= y, entonces un circuito hamiltoniano en G es una solucin ptima al problema del agente
viajero si la solucin existe.

Para hallar una solucin aproximada al problema del agente viajero se dispone de diversos algoritmos
como los de Bellmore-Nemhauser (1968), Held-Karp (1970), Garfinkel-Nemhauser (1972), Little-Murty
(1973) y otros. Todos estos algoritmos caen dentro de dos categoras:
A. Caicedo B., G. Wagner de G., R. M. Mndez
56 CICLO HAMILTONIANO

1. Algoritmo que siempre halla una solucin ptima pero que se requiere de un nmero muy grande
de operaciones.

2. Algoritmo que encuentra un circuito hamiltoniano pero que no siempre es el ptimo. Requiere un
nmero razonable de operaciones.

Un algoritmo que encuentra una sub-ptima solucin al problema del agente viajero en un grafo completo
es el llamado algoritmo del vecino ms cercano. Este algoritmo se describe a continuacin.

5.4 Algoritmo del Vecino ms Cercano

paso 0. Entrar un grafo G = (N, A) completo.

paso 1. Escoger cualquier nodo n1 N
Hacer n = n1 y w = 0 (w es el valor del arco, o longitud de la trayectoria)
Adicionar n a la lista de nodos en la trayectoria.
paso 2. Marcar n
Mientras existan nodos sin marcar, hacer:
begin
paso 3. Escoger cualquier nodo u no marcado que sea el ms
cercano a n y adicionarlo a la lista de nodos en la
trayectoria.
paso 4. Hacer w = w+ el valor del arco (n , u)
paso 5. Hacer n = u
end
paso 6. Adicionar n1 a la lista de nodos en la trayectoria.
paso 7. Hacer w = w+ el valor del arco (n , n1 )
paso 8. Imprimir la trayectoria. Parar

Ejemplo 3
Aplicar el algoritmo del vecino ms cercano al grafo pesado de la figura 4, para hallar un ciclo
hamiltoniano.
b
5
10
a d
7

6 3
c
8
Figura 4.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Algoritmo del Vecino ms Cercano 57

Solucin
paso 0. El grafo dado es completo.
paso 1. Escoger arbitrariamente a b como nodo inicial.
Hacer n = b, y w = 0

Adicionar n a la lista de nodos en la trayectoria. T = {b}

paso 2. Marcar n . An quedan nodos sin marcar. Ejecutar pasos 3 a 5.
paso 3. Escoger el nodo a que es el ms cercano a b de los adyacentes sin marcar.
Adicionarlo a la trayectoria. T = {b, a}.
paso 4. Hacer w = w+ valor de (b, a) = 0 + 5 = 5.
paso 5. Hacer n = a.
paso 2. Marcar n . An quedan nodos sin marcar. Ejecutar pasos 3 a 5
paso 3. Escoger el nodo c que es el ms cercano a a de los adyacentes sin marcar.
Adicionarlo a la trayectoria. T = {b, a, c}.
paso 4. Hacer w = w+ valor de (b, c) = 5 + 6 = 11
paso 5. Hacer n = c.
paso 2. Marcar n . An quedan nodos sin marcar. Ejecutar pasos 3 a 5
paso 3. Escoger el nodo d que es el ms cercano a c de los adyacentes sin marcar.
Adicionarlo a la trayectoria. T = {b, a, c, d}
paso 4. Hacer w = w+ valor de (c, d) = 11 + 3 = 14
paso 5. Hacer n = d
paso 2. Marcar n . No quedan nodos sin marcar. Continuar
paso 6. Adicionar nodo inicial a la trayectoria. T = {b, a, c, d, b}
paso 7. Hacer w = w+ valor de (d, b) = 14 + 10 = 24.
paso 8. Imprimir la trayectoria: T = {b, a, c, d, b}. El valor del circuito es de 24
unidades. Parar

Se ha hallado un circuito hamiltoniano que no es una solucin ptima al problema del agente viajero
puesto que si se toma como nodo inicial al nodo a, el circuito resultante ser de longitud 23 como se
muestra en la figura 5.
b
5

a d
7

3
c

8
Figura 5.

A. Caicedo B., G. Wagner de G., R. M. Mndez

58 CICLO HAMILTONIANO

Teorema 4

Sea G un grafo conexo sin lazos, con n nodos, n 3. Entonces x, y N, si grad(x) + grad(y) n
y x e y no estn conectados por un arco, entonces G es hamiltoniano

Ejemplo 4

1 2
(2, 3),
no existe
n = 5 y (3, 4), no existe
3
no existe

(1, 5),
4 5

Figura 6.

grad(2) + grad(3) = 3 + 2 =5 5

grad(3) + grad(4) = 2 + 3 =5 5 = G es hamiltoniano



grad(1) + grad(5) = 3 + 3 =6 5

Teorema 5

Sea G un grafo conexo sin lazos, |N (G)| = n 3. Si G tiene al menos 21 (n 1)(n 2) + 2 arcos,
entonces G es hamiltoniano

Ejemplo 5

b b b

n = 5 y 12 (5 1)(5 2) + 2 = 8 aristas,
entonces G es hamiltoniano

b b

Figura 7.

Nota: Observe que los grafos de los ejemplos 4 y 5 son hamiltonianos pero no cumplen el teorema de
Dirac.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Algoritmo del Vecino ms Cercano 59

Ejercicios Captulo 5
1. Encontrar un ciclo hamiltoniano y un circuito euleriano para el grafo de la figura 8.
2 3 4

1 5 8

6 7
Figura 8.

2. Aplique el algoritmo del vecino ms cercano para hallar un ciclo hamiltoniano en el grafo de la
figura 9, empezando en el nodo a) 1; b) 2; c) 3.
4 6 7
1 2 3 4
12 3 11

9 10
10 2 6 8
5

5 6 7 8
5 4 3
Figura 9.

3. Cules de los grafos de la figura 10 contienen un circuito hamiltoniano. Cules contienen una
trayectoria hamiltoniana pero no un circuito hamiltoniano
b b b b b b b

b b b b b b b b b

b b b b b b

Figura 10.

4. Encontrar un circuito hamiltoniano en el grafo de la figura 11.

b

b b

b b
b b
b b

b b
b b

b b b

b b

A. Caicedo B., G. Wagner de G., R. M. Mndez

60 CICLO HAMILTONIANO

Figura 11.

5. Aplique el algoritmo HAMICICLO al grafo de la figura 12.

a b c d e

Figura 12.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 ulo
pt

6
Ca

LA TRAYECTORIA MS CORTA

Existen diversas situaciones o problemas de la vida real que pueden ser llevadas a formularse
como un caso especfico de la Teora de Grafos, como es el hecho de encontrar la trayectoria
ms corta que une dos puntos de abastecimiento, dos ciudades, etc.

Algunos de los problemas ms comunes que pueden darse dentro de este mbito son:

a. Las compaas areas necesitan con frecuencia determinar las rutas ms cortas de sus vuelos que
cubran el mximo nmero posible de los aeropuertos a los cuales estn autorizados para llegar.

b. Los agentes viajeros de las compaas comerciales requieren de rutas que les permitan visitar el
mayor nmero de clientes sin salirse del lmite de sus presupuestos.

c. Las agencias de inversionistas deben decidir cmo invertir ptimamente sus fondos, escogiendo de
entre una gama de posibilidades de diversos montos y tiempos de duracin, y as llegar a establecer
el mejor plan de inversin, el cual correspondera a la trayectoria ms corta de una red establecida
considerando los nodos como fechas y los valores de los arcos como las rentabilidades esperadas.

d. Las compaas manufactureras deben enfrentar el problema de reposicin de maquinaria despus

de un perodo de tiempo dado, por lo cual pueden planear una poltica de reemplazo que minimice
el costo total de operacin para la mquina durante dicho periodo. Esta poltica se puede establecer
partiendo de plantear el modelo como un problema de ruta ms corta en una red orientada.

De los algoritmos diseados para resolver el problema de la trayectoria ms corta se destacan:

Algoritmo de DIJKSTRA (1959): permite encontrar la trayectoria ms corta entre dos nodos espec-
ficos, cuando los valores de los arcos son todos positivos

Algoritmo de FLOYD (1962): permite encontrar la trayectoria ms corta desde un nodo cualquiera
hasta uno de los otros nodos en el grafo, el cual puede tener arcos de valor negativo pero no circuitos
negativos

Algoritmo de FORD (1964): sirve para calcular la trayectoria ms corta entre dos nodos dados cuando
los valores de los arcos pueden ser negativos. Es una generalizacin del algoritmo de DIJKSTRA y
no se puede aplicar a grafos que contengan circuitos cuya longitud total sea negativa.

Algoritmo de DANTZIG (1967): es similar al algoritmo de FLOYD puesto que tambin encuentra
la trayectoria ms corta desde un nodo dado hasta cada uno de los otros nodos en el grafo.

Algoritmo de POLLAC (1967): encuentra la primera y segunda trayectoria ms corta en un grafo

que puede tener arcos negativos.
61
62 LA TRAYECTORIA MS CORTA

Algoritmo de FLOYD-WARSHALL (1962): permite encontrar el valor de la trayectoria ms corta

entre cualquier par de nodos de un grafo dirigido o no dirigido, usando en cada iteracin un nodo
intermedio.

6.1 Trayectoria Mnima

Definicin 6.1
Dados los nodos ni y nj de un grafo G = (N, A) se llama trayectoria mnima o camino mnimo
de ni a nj al nmero de arcos del camino de longitud mnima que va desde ni a nj y se representa
por d(ni , nj )

Cuando en el grafo no exista un camino que vaya de ni a nj se dice que el camino mnimo es d(ni , nj ) = .
Adems, cuando ni = nj se escribe d(ni , nj ) = 0.

Si ni , nj y nk son nodos adyacentes, entonces:

d(ni , nj ) + d(nj , nk ) d(ni , nk )

Si el grafo es simtrico, entonces

d(ni , nj ) = d(nj , ni )

Ejemplo 1
Para el grafo de la figura 1 se tiene:
Camino mnimo del nodo 1 al 7 es d(1, 7) = 2
Camino mnimo del nodo 2 al 5 es d(2, 5) = 2

1 3

5
7

2 4 6
Figura 1.

6.2 Algoritmo del Camino Mnimo

Para determinar el o los caminos mnimos que van desde el nodo np al nodo nf en un grafo no pesado
se sigue el siguiente procedimiento:
A. Caicedo B., G. Wagner de G., R. M. Mndez
 Trayectoria del Valor Mnimo 63

paso 1. Se marca con 0 el nodo np (np = nodo de partida)

paso 2. Se marcan con 1 a todos los nodos ni no marcados, adyacentes a np , y tales que (np , ni ) A
(o sea que debe existir arco entre np y ni )
paso 3. Se marcan con 2 los nodos nj no marcados, adyacentes a los nodos ni marcados en el paso
anterior y tales que (ni , nj ) A
paso 4. Continuar el proceso hasta llegar a marcar el nodo nf , los caminos mnimos quedan deter-
minados por las secuencias de nodos que estn marcados en secuencia ascendente 0, 1, 2, . . .

Ejemplo 2
En el grafo de la figura 2 determinar el camino mnimo desde n0 a n7

n3
n5

n0

n2 n7

n1
n4 n6

Figura 2.
Solucin
paso 1. Se marca con 0 el nodo n0 , n0 = np
paso 2. Se marcan con 1 los nodos n1 , n2 , n3 adyacentes a n0 .
paso 3. Se marcan con 2 los nodos n4 , n5 adyacentes a n1 , n2 , n3 .
paso 4. Se marcan con 3 los nodos n6 , n7 adyacentes a n4 , n5 . Ya se marc el nodo final n7. Parar.
El camino mnimo desde n0 a n7 es:
{n0 , n3 , n5 , n7 } {n0 , n2 , n4 , n7 } {n0 , n1 , n4 , n7 }
Con d(n0 , n7 ) = 3. El camino ms corto est formado por los nodos que quedaron
etiquetados en un orden consecutivo ascendente 0, 1, 2, 3.

6.3 Trayectoria del Valor Mnimo

Sea G = (N, A) un grafo y supngase que todo arco u tiene asociado un nmero l(u) 0 llamado valor
de u. Se trata de hallar una trayectoria o camino que vaya desde un nodo vi a otro vj tal que su valor
total sea mnimo. Este problema es resuelto en una forma muy eficiente con el algoritmo propuesto por
Edsgar W. Dijkstra.

A. Caicedo B., G. Wagner de G., R. M. Mndez

64 LA TRAYECTORIA MS CORTA

6.4 Algoritmo de DIJKSTRA

El algoritmo asigna un etiqueta a cada nodo en el grafo. Esta etiqueta es la distancia que hay desde el
nodo s escogido como origen a lo largo de la trayectoria ms corta encontrada, hasta el nodo que se est
etiquetando.
La etiqueta de cada nodo puede estar en 2 estados:

a. Puede ser permanente: en este caso la distancia encontrada es a lo largo de la trayectoria ms corta
de todas las encontradas.

b. Puede ser temporal: cuando hay incertidumbre de que la trayectoria encontrada sea la ms corta
de todas.

A medida que el mtodo trabaja se cambian gradualmente las etiquetas temporales por etiquetas perma-
nentes. Al comienzo se tiene un conjunto de nodos con etiquetas temporales y el objetivo es hacer que esas
etiquetas disminuyan, encontrando trayectorias a esos nodos usando trayectorias a nodos etiquetados per-
manentemente. Cuando esto se ha logrado, se selecciona el nodo con la etiqueta temporal ms pequea y
esta etiqueta se convierte en permanente. El proceso se repite hasta que al nodo terminal t se le haya asig-
nado una etiqueta permanente, pero esto puede ocurrir eventualmente, ya que cada vez que el algoritmo
es usado, una de las etiquetas es omitida y as el nmero de nodos con etiquetas temporales decrece a cero.

Algoritmo:
paso 0. Asignar un etiqueta temporal l(i) = a todos los nodos i 6= s. Fijar l(s) = 0 y p = s. Hacer
l(s) permanente (p es el ltimo nodo al que se le haya asignado una etiqueta permanente).
s es el nodo de partida
paso 1. Para cada nodo i con una etiqueta temporal redefnase l(i) a ser el menor entre l(i) y
l(p) + d(p, i). Hallar el nodo i con la menor etiqueta temporal. Hacer p igual a ste i y hacer
permanente la etiqueta l(p)
paso 2 Si el nodo t tiene etiqueta temporal, repetir el paso 1. En caso contrario, t tiene una etiqueta
permanente y sta corresponde a la longitud de la trayectoria ms corta desde s hasta t a
travs de la red. Parar.

Ejemplo 3
El grafo de la figura 3 muestra los costos en miles de pesos, para transportar una tonelada de
mercanca entre los diversos centros de consumo. Se desea determinar la trayectoria ms corta (menos
costosa) para transportar la mercanca desde el centro de abastecimiento S al centro de consumo t
S

4 7
3
a 3
b

2
2

c d t
3 2
Figura 3.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Algoritmo de DIJKSTRA 65

Para efectos de aplicacin del algoritmo, el centro de consumo t se llamar el nodo terminal t

Solucin

Matriz de adyacencias (o de costos); si el grafo no es dirigido

s a b c d t

s 0 4 7 3
a 4 0 3 2
b 7 3 0 2
M=
c 3 0 3
d 2 3 0 2
t 2 2 0

paso 0. Se asignan etiquetas. Hacer p = s y l(s) = permanente

s a b c d t
l() = 0
permanentes? si no no no no no

paso 1. Redefinir etiquetas:

l(a) = mn{, 0 + 4} = 4
l(b) = mn{, 0 + 7} = 7
l(c) = mn{, 0 + 3} = 3
l(d) = mn{, 0 + } =
l(t) = mn{, 0 + } =

Hacer p = c y l(c) = permanente

s a b c d t
l() = 0 4 7 3
permanentes? si no no si no no

paso 2. El nodo t tiene etiqueta temporal. Repetir paso 1.

paso 1. Redefinir etiquetas:
l(a) = mn{4, 3 + } = 4
l(b) = mn{7, 3 + } = 7
l(d) = mn{, 3 + 3} = 6
l(t) = mn{, 3 + } =

Hacer p = a y l(a) = permanente

s a b c d t
l() = 0 4 7 3 6
permanentes? si si no si no no

A. Caicedo B., G. Wagner de G., R. M. Mndez

66 LA TRAYECTORIA MS CORTA

paso 1. Redefinir etiquetas:

l(b) = mn{7, 4 + 3} = 7
l(d) = mn{6, 4 + 2} = 6
l(t) = mn{, 4 + } =

Hacer p = d y l(d) = permanente

s a b c d t
l() = 0 4 7 3 6
permanentes? si si no si si no

paso 2. El nodo t tiene etiqueta temporal. Repetir paso 1.

paso 1. Redefinir etiquetas:
l(b) = mn{7, 6 + } = 7
l(t) = mn{, 6 + 2} = 8

Hacer p = b y l(b) = permanente

s a b c d t
l() = 0 4 7 3 6 8
permanentes? si si si si si no

paso 2. El nodo t tiene etiqueta temporal. Repetir paso 1.

paso 1. Redefinir etiquetas:
l(t) = mn{8, 7 + 2} = 8

Hacer p = t y l(t) = permanente

s a b c d t
l() = 0 4 7 3 6 8
permanentes? si si si si si si

paso 2. El nodo t tiene etiqueta permanente. PARAR

La trayectoria ms corta a travs de la red desde el nodo s hasta t tiene longitud de 8
unidades (el valor de la etiqueta de t)

6.5 Algoritmo de Floyd-Warshall

El algoritmo de Floyd-Warshall encuentra el camino mnimo entre todos los pares de nodos, en una nica
ejecucin, en grafos dirigidos ponderados, sin ciclos negativos. El algoritmo compara todos los posibles
caminos a travs del grafo entre cada par de nodos y escoge la estimacin ptima (la de menor costo).
A. Caicedo B., G. Wagner de G., R. M. Mndez
 Algoritmo de Floyd-Warshall 67

Sea G un grafo ponderado de n nodos. Sea cmin(i, j, k) una funcin que devuelve el camino mnimo de i
a j usando nicamente los nodos de 1 a k como puntos intermedios en el camino. El objetivo es encontrar
el camino mnimo desde cada i a cada j, usando nicamente los nodos 1 hasta k + 1.

El camino ptimo de i a j que utiliza nicamente los nodos de 1 hasta k, como nodos intermedios,
est definido por cmin(i, j, k). Si hubiera un camino mejor de i a k + 1 a j, la longitud de ese camino
sera la concatenacin del camino mnimo de i a k + 1 (utilizando nodos de 1 . . . k) y el camino mnimo
de k + 1 a j (que tambin utiliza los nodos en 1 . . . k)

Proceso Recursivo
cmin(i, j, k) = mn [cmin(i, j, k 1), cmin(i, k, k 1) + cmin(k, j, k 1)]
cmin(i, j, 0) = valorarco(i, j)

Para efectos de implementar el algoritmo se usa una matriz de adyacencias del grafo, modificada y
que se llamar matriz de distancias o Dist; esta matriz es la matriz de pesos del grafo donde la ausencia
de un arco se simboliza con , y los valores en la diagonal principal son ceros.

Se utiliza algn nodo k como nodo intermedio para hallar la distancia ms corta entre todos los pares de
nodos.

Para una pareja de nodos (i, j) el camino ms corto del nodo i al k, que es Dist[i, k], se suma al camino
ms corto desde el nodo k hasta el nodo j. Si esta suma es menor que el camino actualmente ms corto
entre los nodos i y j, entonces se utiliza el camino ms corto que pasa por el nodo k.

Si Dist[i, k] + Dist[k, j] < Dist[i, j] entonces Dist[i, j] = Dist[i, k] + Dist[k, j]

Repitiendo este proceso para todas las parejas de nodos, se puede obtener para cada pareja la longitud
del camino de mnimo costo que pasa por el nodo k.

Al tomar todos los nodos de G como nodos intermedios, se obtiene la matriz de distancias mnimas
entre todos los pares de nodos.

Se introduce una matriz en la cual se registra informacin acerca de los nodos intermedios. Dicha matriz
se puede llamar CAM IN O. Esta informacin se puede utilizar para generar los nodos que se encuentran
en cada uno de los caminos mnimos.

La matriz CAM IN O se inicializa en cero y cuando el proceso termina CAM IN O[i, j] contiene el nmero
de nodos que ha dado lugar a un cambio en Dist[i, j].

Si CAM IN O[i, j] = 0 el camino ms corto es un camino que va directo de i a j

Si CAM IN O[i, j] = k el camino ms corto que va de i a j pasa por el nodo k
Si Dist[i, k] < y Dist[k, j] < , entonces el camino va desde i a k y luego de k a j
Si Dist[i, k] = entonces se puede hallar recursivamente un camino desde i hasta k
Si Dist[k, j] = entonces se puede hallar recursivamente un camino desde k hasta j

A. Caicedo B., G. Wagner de G., R. M. Mndez

68 LA TRAYECTORIA MS CORTA

Procedimiento (1)
Entrar Dist[i, j] =matriz inicial de valores de G
begin
para i = 1 hasta n
para j = 1 hasta n
hacer CAM IN O[i, j] = 0
para k = 1 hasta n
para i = 1 hasta n
para j = 1 hasta n
si Dist[i, k] + Dist[k, j] < Dist[i, j], hacer
begin
Dist[i, j] = Dist[i, k] + Dist[k, j]
CAM IN O[i, j] = k
end
end.

Ejemplo 4
Para el siguiente grafo establecer la matriz de distancias ms cortas entre todas las parejas de nodos
y la matriz que indica los nodos intermedios por los cuales pasa cada camino ms corto.
1 3 2

0 1 0 0 0 0
1 5

3 0 1 0 0 0 0
8 1 1 1 Dist =


CAM IN O =



5 1 0 0 0 0 0

8 1 4 0 0 0 0 0
4 4 3

Figura 4.
k=1 (
Dist[1, 1], no cambia
i = 1, j = 1, Dist[1, 1] + Dist[1, 1] = 0 + 0 = 0 < 0? (no)
CAM IN O[1, 1], no cambia
(
Dist[1, 2], no cambia
j = 2, Dist[1, 1] + Dist[1, 2] = 0 + = < ? (no)
CAM IN O[1, 2], no cambia
(
Dist[1, 3], no cambia
j = 3, Dist[1, 1] + Dist[1, 3] = 0 + = < ? (no)
CAM IN O[1, 3], no cambia
(
Dist[1, 4], no cambia
j = 4, Dist[1, 1] + Dist[1, 4] = 0 + 1 = 1 < 1? (no)
CAM IN O[1, 4], no cambia
(
Dist[2, 1], no cambia
i = 2, j = 1, Dist[2, 1] + Dist[1, 1] = 3 + 0 = 3 < 3? (no)
CAM IN O[2, 1], no cambia
(
Dist[2, 2], no cambia
j = 2, Dist[2, 1] + Dist[1, 2] = 3 + = < 0? (no)
CAM IN O[2, 2], no cambia
(
Dist[2, 3] no cambia
j = 3, Dist[2, 1] + Dist[1, 3] = 3 + = < 1? (no)
CAM IN O[2, 3] no cambia

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Algoritmo de Floyd-Warshall 69

(
Dist[2, 4] cambia a 4
j = 4, Dist[2, 1] + Dist[1, 4] = 3 + 1 = 4 < ? (si)
CAM IN O[2, 4] = 1
(
Dist[3, 1] no cambia
i = 3, j = 1, Dist[3, 1] + Dist[1, 1] = 5 + 0 = 5 < 5? (no)
CAM IN O[3, 1] no cambia
(
Dist[3, 2] no cambia
j = 2, Dist[3, 1] + Dist[1, 2] = 5 + = < ? (no)
CAM IN O[3, 2] no cambia
(
Dist[3, 3] no cambia
j = 3, Dist[3, 1] + Dist[1, 3] = 5 + = < 0? (no)
CAM IN O[3, 3] no cambia
(
Dist[3, 4] cambia a 6
j = 4, Dist[3, 1] + Dist[1, 4] = 5 + 1 = 6 < ? (si)
CAM IN O[3, 4] = 1
(
Dist[4, 1] no cambia
i = 4, j = 1, Dist[4, 1] + Dist[1, 1] = 8 + 0 = 8 < 8? (no)
CAM IN O[4, 1] no cambia
(
Dist[4, 2] no cambia
j = 2, Dist[4, 2] + Dist[1, 2] = 1 + = < 1? (no)
CAM IN O[4, 2] no cambia
(
Dist[4, 3] no cambia
j = 3, Dist[4, 3] + Dist[1, 3] = 4 + = < 4? (no)
CAM IN O[4, 3] no cambia
(
Dist[4, 4] no cambia
j = 4, Dist[4, 4] + Dist[1, 4] = 0 + 1 = 1 < 0? (no)
CAM IN O[4, 4] no cambia

Las matrices revisadas al final de estas iteraciones son:

Para k = 1 (nodo intermedio o pivote)

0 1 0 0 0 0

3 0 1 4 0 0 0 1
Dist1 = CAM IN O1 =
5 1 0 6 0 0 0 1
8 1 4 0 0 0 0 0

Para k = 2
0 1 0 0 0 0

3 0 1 4 0 0 0 1
Dist2 = CAM IN O2 =
4 1 0 5 2 0 0 2
4 1 2 0 2 0 2 0

Para k = 3
0 1 0 0 0 0

3 0 1 4 0 0 0 1
Dist3 = CAM IN O3 =
4 1 0 5 2 0 0 2
4 1 2 0 2 0 2 0

Para k = 4
0 2 3 1 0 4 4 0

3 0 1 4 0 0 0 1
Dist4 = CAM IN O4 =
4 1 0 5 2 0 0 2
4 1 2 0 2 0 2 0

A. Caicedo B., G. Wagner de G., R. M. Mndez

70 LA TRAYECTORIA MS CORTA

La matriz Dist4 posee los valores de las distancias ms cortas entre cualquier par de nodos. Por
ejemplo Dist(1, 3) = 3, Dist(3, 4) = 5, etc.

La matriz CAM IN O4 sirve para establecer cules nodos conforman los caminos ms cortos. Por
ejemplo establecer el camino ms corto de 3 a 4. CAM IN O[3, 4] = 2 indica que 2 es un nodo
intermedio entre 3 y 4, es decir,
3 2 4

Pero CAM IN O[2, 4] = 1 indica que 1 es un nodo intermedio entre 2 y 4, es decir,

3 2 1 4

Como CAM IN O[3, 2] = 0, CAM IN O[2, 1] = 0, CAM IN O[1, 4] = 0, entonces no hay ms nodos
intermedios.

El camino ptimo entre 3 y 4 es

3 1 2 3 1 1 4
con longitud= 5 como lo indica la matriz Dist[3, 4] = 5

Otra forma de presentar el procedimiento de Floyd-Warshall es:

Procedimiento (2)
Entrar la matriz de distancias Dist del grafo G
Para k = 1 hasta n
Para i 6= k, 1 hasta n
Para j 6= k, 1 hasta n
hacer Dist[i, j] = mn(Dist(i, j), Dist(i, k) + Dist(k, j))

Ejemplo 5
Hallar la matriz de distancias ms cortas entre todas las parejas de nodos del siguiente grafo no
dirigido
5
1 3 2 3
1 2 3 4 5 6

1 0 3 5 1
1 9 7 1
2
3 0 9
3 5 0 7 7 1
Dist =
4
1 7 0 4

4 5 6 5 9 7 0
6 1 4 0
4
7
Figura 5.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Algoritmo de Floyd-Warshall 71

0 3 5 1

3 0 9

5 0 7 7 1
Dist =
1 7 0 4

9 7 0
1 4 0
Aplicamos el algoritmo de Floyd-Warshall, y para ello en cada iteracin fijamos un vrtice intermedio.
1a Iteracin: nodo intermedio = k = 1
La matriz en simtrica, por lo que solamente har falta calcular el tringulo superior de las distancias.

d23 = mn(d23 , d21 + d13 ) = 8, d24 = mn(d24 , d21 + d14 ) = 4

d25 = mn(d25 , d21 + d15 ) = 9, d26 = mn(d26 , d21 + d16 ) =
d34 = mn(d34 , d31 + d14 ) = 6, d35 = mn(d35 , d31 + d15 ) = 7
d36 = mn(d36 , d31 + d16 ) = 1, d45 = mn(d45 , d41 + d15 ) =
d46 = mn(d46 , d41 + d16 ) = 4, d56 = mn(d56 , d51 + d16 ) =

La matriz de distancias despus de la primera

iteracin es:
0 3 5 1

3 0 8 4 9

5 8 0 6 7 1
Dist1 =
1 4 6 0 4

9 7 0
1 4 0
2a Iteracin: nodo intermedio = k = 2, usando Dist1

d13 = mn(d13 , d12 + d23 ) = 5, d14 = mn(d14 , d12 + d24 ) = 1

d15 = mn(d15 , d12 + d25 ) = 12, d16 = mn(d16 , d12 + d26 ) =
d34 = mn(d34 , d32 + d24 ) = 6, d35 = mn(d35 , d32 + d25 ) = 7
d36 = mn(d36 , d32 + d26 ) = 1, d45 = mn(d45 , d42 + d25 ) = 13
d46 = mn(d46 , d42 + d26 ) = 4, d56 = mn(d56 , d52 + d26 ) =

La matriz de distancias despus de esta iteracin es:

0 3 5 1 12

3 0 8 4 9

5 8 0 6 7 1
Dist2 =
1 4 6 0 13 4

12 9 7 13 0
1 4 0

A. Caicedo B., G. Wagner de G., R. M. Mndez

72 LA TRAYECTORIA MS CORTA

3a Iteracin: nodo intermedio = k = 3, usando Dist2

d12 = mn(d12 , d13 + d32 ) = 3, d14 = mn(d14 , d13 + d34 ) = 1

d15 = mn(d15 , d13 + d35 ) = 12, d16 = mn(d16 , d13 + d36 ) = 6
d24 = mn(d24 , d23 + d34 ) = 4, d25 = mn(d25 , d23 + d35 ) = 9
d26 = mn(d26 , d23 + d36 ) = 9, d45 = mn(d45 , d43 + d35 ) = 13
d46 = mn(d46 , d43 + d36 ) = 4, d56 = mn(d56 , d53 + d36 ) = 8

La matriz de distancias despus de esta iteracin es:

0 3 5 1 12 6

3 0 8 4 9 9

5 8 0 6 7 1
Dist3 =
1 4 6 0 13 4

12 9 7 13 0 8
6 9 1 4 8 0
4a Iteracin: nodo intermedio = k = 4, usando Dist3

d12 = mn(d12 , d14 + d42 ) = 3, d13 = mn(d13 , d14 + d43 ) = 5

d15 = mn(d15 , d14 + d45 ) = 12, d16 = mn(d16 , d14 + d46 ) = 5
d23 = mn(d23 , d24 + d43 ) = 8, d25 = mn(d25 , d24 + d45 ) = 9
d26 = mn(d26 , d24 + d46 ) = 8, d35 = mn(d35 , d34 + d45 ) = 7
d36 = mn(d36 , d34 + d46 ) = 1, d56 = mn(d56 , d54 + d46 ) = 8

La matriz de distancias despus de esta iteracin es:

0 3 5 1 12 5

3 0 8 4 9 8

5 8 0 6 7 1
Dist4 =
1 4 6 0 13 4

12 9 7 13 0 8
5 8 1 4 8 0
5a Iteracin: nodo intermedio = k = 5, usando Dist4

d12 = mn(d12 , d15 + d52 ) = 3, d13 = mn(d13 , d15 + d53 ) = 5

d14 = mn(d14 , d15 + d54 ) = 1, d16 = mn(d16 , d15 + d56 ) = 5
d23 = mn(d23 , d25 + d53 ) = 8, d24 = mn(d24 , d25 + d54 ) = 4
d26 = mn(d26 , d25 + d56 ) = 8, d34 = mn(d34 , d35 + d54 ) = 6
d36 = mn(d36 , d35 + d56 ) = 1, d46 = mn(d46 , d45 + d56 ) = 4

La matriz de distancias despus de esta iteracin es:

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Algoritmo Matricial 73

0 3 5 1 12 5

3 0 8 4 9 8

5 8 0 6 7 1
Dist5 = Dist4 =
1 4 6 0 13 4

12 9 7 13 0 8
5 8 1 4 8 0

6a Iteracin: nodo intermedio = k = 6, usando Dist5

d12 = mn(d12 , d16 + d62 ) = 3, d13 = mn(d13 , d16 + d63 ) = 5

d14 = mn(d14 , d16 + d64 ) = 1, d15 = mn(d15 , d16 + d65 ) = 12
d23 = mn(d23 , d26 + d63 ) = 8, d24 = mn(d24 , d26 + d64 ) = 4
d25 = mn(d25 , d26 + d65 ) = 9, d34 = mn(d34 , d36 + d64 ) = 5
d35 = mn(d35 , d36 + d65 ) = 7, d45 = mn(d45 , d46 + d65 ) = 12

La matriz de distancias despus de esta iteracin es:

0 3 5 1 12 5

3 0 8 4 9 8

5 8 0 5 7 1
Dist6 =
1 4 5 0 12 4

12 9 7 12 0 8
5 8 1 4 8 0
Ya se han hecho todas las iteraciones posibles. Por tanto, el camino mnimo entre dos vrtices
cualesquiera del grafo ser el obtenido en la matriz final. En este caso, el camino mnimo entre 3 y
4 vale 5.

6.6 Algoritmo Matricial

Este algoritmo propuesto por SHUMBEL en Structure in Communication Nets, Symposium of Informa-
tion Networks en 1954, establece un procedimiento para hallar la trayectoria de valor mximo o de valor
mnimo, usando producto de matrices a partir de la matriz inicial de costos o adyacencias.

Algoritmo de Shumbel
Sea M la matriz de valores asociados a un grafo G, la cual se representa por M = [mij ] donde los
elementos mij se definen de dos formas.

a. Si se desea encontrar la trayectoria de valor mnimo, se establece:

valor, vr del arco, si el arco existe

mij = X, si el arco no existe. Con X

si hay un bucle o si i = j

0,

A. Caicedo B., G. Wagner de G., R. M. Mndez

74 LA TRAYECTORIA MS CORTA

b. Si se desea encontrar la trayectoria de valor mximo, se define:

valor, vr del arco, si el arco existe

mij = X, si el arco no existe. Con X

si hay un bucle o si i = j

0,

La matriz de trayectorias de valor ptimo es M n1 en donde n es el nmero de nodos del grafo.

Si en un momento dado se obtiene que M m = M m1 , siendo m < n 1 la matriz M m es la matriz

de trayectorias de valor ptimo, o sea qu la matriz de valor ptimo se obtiene del clculo de las siguientes
potencias: M , M 2 , M 3 , M 4 , . . . donde las operaciones matriciales se definen de la siguiente forma:

a. Si se trata de hallar la trayectoria de valor mnimo:

El producto de las dos matrices dar origen a otra matriz C obtenida as:

cij =mnk (aik + bkj )

=mnk (ai1 + b1j , ai2 + b2j , ai3 + b3j , . . . , ain + bnj )

La anterior expresin es equivalente a: sumar las parejas de elementos que intervienen en el producto
de matrices y escoger la suma mnima.

b. Si se trata de hallar la trayectoria de valor mximo:

Los elementos de la matriz producto son de la forma:

cij =mxk (aik + bkj )

=mxk (ai1 + b1j , ai2 + b2j , ai3 + b3j , . . . , ain + bnj )

La anterior expresin es equivalente a: sumar las parejas de elementos que intervienen en el producto
de matrices y escoger la suma mxima.

Ejemplo 6
Determinar las trayectorias de valor mnimo en el grafo de la figura 6

x2 8 x4

3 5
4 1

x1 3 4 3 x6

7 6
x3 4 x5

Figura 6.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Algoritmo Matricial 75

Solucin
La matriz de costos asociados al grafo es:

1 2 3 4 5 6

1 0 3 7 X X X
2
X 0 3 8 4 X
3 X X 0 1 4 X
M=
4
X X X 0 3 5
5X X X 4 0 6
6 X X X X X 0
El primer producto de matrices es: M M = M 2 , donde los elementos de M 2 se determinan as:

m11 = mn{0 + 0, 3 + x, 7 + x, x + x, x + x, x + x} = 0

m12 = mn{0 + 3, 3 + 0, 7 + x, x + x, x + x, x + x} = 3
m13 = mn{0 + 7, 3 + 3, 7 + 0, x + x, x + x, x + x} = 6
............
m16 = mn{0 + x, 3 + x, 7 + x, x + 5, x + 6, x + 0} = x
Se continua el proceso con las otras filas y columnas y se obtiene:

0 3 6 8 7 X

X 0 3 4 4 10

X X 0 1 4 6
M2 =
X X X 0 3 5

X X X 4 0 6
X X X X X 0

El segundo producto es: M 2 M = M 3

Se continua el proceso de obtener nuevas matrices potencias de M hasta hallar dos matrices potencias
que coincidan en todos sus elementos. Para este ejemplo se lleg a que:

0 3 6 7 7 12

X 0 3 4 4 9

X X 0 1 4 6
M5 = M6 =
X X X 0 3 5

X X X 4 0 6
X X X X X 0

La matriz M 5 es la matriz de trayectorias de valor mnimo; muestra los valores de las trayectorias
mnimas para ir de un nodo a otro, por ejemplo: para ir del nodo 1 al nodo 6 la trayectoria mnima
tiene un valor de 12. Para ir del nodo 2 al 6 la trayectoria mnima vale 9.

A. Caicedo B., G. Wagner de G., R. M. Mndez

76 LA TRAYECTORIA MS CORTA

6.7 La Trayectoria ptima

Hasta ahora se ha encontrado una matriz de distancias mnimas, pero no se ha determinado cules son
esas trayectorias mnimas. Para llegar a encontrar una trayectoria mnima se procede de la siguiente forma:

Sea S una matriz cuyos elementos sij son determinados de la siguiente forma:


1, si el valor del arco no cambi entre M y la matriz M m .
M m es la matriz donde par el algoritmo de Shumbel
Sij =
0,

si conserva la X, en la diagonal y en cualquier otro caso, es decir,
si ocurri un cambio en la posicin.
En el ejemplo analizado se comparan las matrices M y M 5 y se obtiene:
1 2 3 4 5 6

1 0 1 0 0 0 0
2
0 0 1 0 1 0
3 0 0 0 1 1 0
S=
4
0 0 0 0 1 1
50 0 0 1 0 1
6 0 0 0 0 0 0

En esta matriz el 1 indica presencia del arco y el 0 la ausencia del mismo. A partir de esta matriz se
pueden establecer las trayectorias, por ejemplo, para ir del nodo 1 al nodo 6 se pueden establecer las
siguientes trayectorias:
a. Del nodo 1 ir al nodo 2 (ver matriz S), estando en 2 ir al nodo 3, estando en 3 ir al nodo 4, del 4
ir al 5 y del 5 ir al 6. Longitud = 16.
b. Del nodo 1 ir al nodo 2, estando en 2 ir al nodo 5 y del 5 ir al nodo 6. Longitud = 13.
c. Del nodo 1 ir al nodo 2, del 2 ir al 4 y del 4 ir al 6. Longitud = 16.
d. Del nodo 1 ir al nodo 2, del 2 ir al nodo 3, del 3 ir al nodo 4 y del 4 ir al nodo 6. Longitud = 12.
Esta trayectoria tiene longitud igual a la que indica la matriz de valores mnimos, lo que indica que
ya se ha encontrado una de las trayectorias ms cortas para ir del nodo 1 al nodo 6.
Lo anterior se puede reorganizar mediante una estructura de rbol:
6
3 5 6 Vr = 16
4 5
1
6 Vr = 12
3
4 5
3 4 4 6 Vr = 19
5 6
3
1 2 6 Vr = 16
4
5
4 4 6 Vr = 16
5 6
6 Vr = 13
Figura 7.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 La Trayectoria ptima 77

La trayectoria de menor costo para ir del nodo 1 al nodo 6 es 1 2 3 4 6 con un valor de 12. Como
lo indica la matriz de parada M 5 es la posicin (1, 6).

En forma similar se procede para hallar otras trayectorias mnimas entre cada par de nodos, las cuales
no necesariamente son nicas.

Ejemplo 7
Un problema simple de control de produccin
Un fabricante de pinturas produce 5 tipos de pinturas que se pueden fabricar con la misma maqui-
naria. Los costos de adecuacin de mquinas para pasar de un producto a otro se muestran en la
siguiente tabla.

i 1 2 3 4 5
1 0 x 10 x 8
2 7 0 5 7 11
3 5 x 0 6 8
4 8 6 7 0 10
5 x 10 8 x 0

Se desea establecer el orden en que deben producir para que el costo sea mnimo.

El problema se puede traducir a un problema de trayectoria ms corta en un grafo conexo como el

siguiente:
8
7
2 4
6
7
11 10
7
1 10
5 5 6
10 5
8
3
8

8
Figura 8.

Se pueden encontrar varias trayectorias mnimas, dependiendo del nodo que se tome como nodo
inicial.
Aqu los nodos son los productos. Los valores en los arcos son los costos.

A. Caicedo B., G. Wagner de G., R. M. Mndez

78 LA TRAYECTORIA MS CORTA

Aplicacin del grafo anterior

M M M2

0 x 10 x 8 0 x 10 x 8 0 18 10 16 8

7 0 5 7 11 7 0 5 7 11 7 0 5 7 11

5 x 0 6 8 5 x 0 6 8 = 5 12 0 6 8

8 6 7 0 10 8 6 7 0 10 8 6 7 0 10
x 10 8 x 0 x 10 8 x 0 13 10 8 14 0
M M2 M3

0 x 10 x 8 0 18 10 16 8 0 18 10 16 8

7 0 5 7 11 7 0 5 7 11 7 0 5 7 11

5 x 0 6 8 5 12 0 6 8 = 5 12 0 6 8

8 6 7 0 10 8 6 7 0 10 8 6 7 0 10
x 10 8 x 0 15 10 8 14 0 13 10 8 14 0

Se encontr que M 2 = M 3 , 3 n 1, entonces M 3 contiene los valores de las trayectorias mnimas.

Por ejemplo, para ir del nodo 1 al 2 la trayectoria mnima vale 18 pasando por el nodo 5.
Para facilitar la bsqueda de las trayectorias mnimas, Shumbel defini una mtriz S de la siguiente
forma:
(
1, si el valor del arco n o cambi entre M y M m
Sij =
0, en la diagonal, si se conserv la x en M m , y en cualquier otro caso

Comparando M y M 3 se obtiene:
1 2 3 4 5

1 0 0 1 0 1
2
1 0 1 1 1
S = 3
1 0 0 1 1
41 1 1 0 1
5 0 1 1 0 0
El 1 indica presencia de arco y el 0 ausencia de arco. Con esta matriz ya se pueden establecer las
trayectorias ptimas de valor mnimo.
2 11 5
6 = 33
4 10
6 10
5 2 = 36
3 Si se inicia con la pintura
8 1 la secuencia ptima es
10 10 7
5 2 4 = 35
15342
1
3 6 4
con un costo de 28
5 = 29
8 2 7
10
4 7 3 = 32
5
8 6
3 6 4 2 = 28 X
Figura 9.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 La Trayectoria ptima 79

4 10 5
6 = 33

10 3 5

1 8 5 8 3 6 4 = 29
1 5
7 8 1 8 5 Si se inicia con la pintura 2 exis-
6 = 27 X
3 4 ten 3 secuencias ptimas
5 5
5 23415
10 3 8 5
2 = 33
1 24315
8 5 8 3
7 8
= 31
6 5 1 8 5 = 27 X 25341
4 7 3
10 5 las tres con un costo de 27
5 8 3 5 1 = 30
5
8
1
3
6 4 8 1 = 27 X
Figura 10.

1 8 5 10 2 7 4 = 30

1 8 5 10 2
5 = 30
6
7 1 8 5 = 27 X Si se inicia con la pintura
3 6 4 6 2 11 3 la secuencia ptima es
10 5
34215
8 5 10 2 7 1 con un costo de 27
= 33

7 1
5 10 2 7
4 8 1 = 33
Figura 11.

A. Caicedo B., G. Wagner de G., R. M. Mndez

80 LA TRAYECTORIA MS CORTA

3 8 5 10 2 = 36
10
2 5 5
10 = 31
1 8 5 8
3

3 8 5
10 = 31
8 1 8
8 Si se inicia con la pintura
5 3 = 29
7 4 la secuencia ptima es
1 8 5
5 = 24 X 42315
4 6 2 5 3 8
5 con un valor de 24
11
7 8 5 En este orden se debe pro-
5 3 1 = 30 ducir las 5 pinturas para
8 10 que el costo sea mnimo.
10 5 1 5 2 = 30
3 8
5 10 2 7 1 = 32

1 10 3
7 = 37
5 10 2 5
3 5 1
8 = 30

3 5 1
Figura 12.

1 10 3 6 4 = 33
7
2 5 5 1
10 3 6 Iniciando con la pintura 5
8
4 1 = 29 la secuencia ptima es
5
1
53421
8
5
con un costo de 27.
3 6 8 1
4 2
2 7 1 = 27 X
Figura 13.

Nota: Obsrvese que en los rboles anteriores algunas ramas quedan sin completar, lo cual indica
que determinadas secuencias no se pueden realizar para producir las 5 pinturas.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 La Trayectoria ptima 81

Ejercicios Captulo 6

1. Aplicar el algoritmo de Dijkstra para encontrar la trayectoria de mnimo valor entre los nodos A y
F del grafo de la figura 5
4

B E

3 12 2 6

3
A 11 D 4 3 G

10 5 8 3

C F

Figura 14.

2. Use un algoritmo que permita hallar la trayectoria de menor nmero de arcos entre los nodos A y
H del grafo de la figura 6

A G

B F
H
D

C E

Figura 15.

3. Aplicar el algoritmo matricial de Shumbel para hallar la trayectoria de mnimo valor entre los nodos
1 y 9, entre los nodos 2 y 10 y entre los nodos 3 y 8 del grafo de la figura 7

1 3 8
5 2
4 8
7
6 2
5 5
2 4 9
2
8 4 4
3 1

3
3 7 11 10
6 6
Figura 16.

4. Debido a los avances tecnolgicos, una compaa procesadora de datos considera que un determinado
tipo de computador tiene una vida til de 4 aos y luego entra en obsolescencia. La compaa puede
tener este tipo de computador por un perodo de 4 aos y luego venderlo por un valor de rescate, o
puede reemplazarlo por un nuevo modelo al final de cualquier ao dado. El costo neto estimado de
operacin (precio de compra + instalacin y mantenimiento precio de venta) para un computador
comprado al inicio del ao i y vendido al inicio del ao j est dado en la tabla 1 y representado en
el grafo de la figura 8; adems, determinar una poltica de reemplazo que minimice el costo total
de operacin durante el perodo de 4 aos. Usar el algoritmo de Dijkstra
A. Caicedo B., G. Wagner de G., R. M. Mndez
82 LA TRAYECTORIA MS CORTA

i 1 2 3 4 5 1

1 12 19 33 49
2 14 23 38
3 16 26 2 3 4 5

4 13
Tabla 1. Figura 17.

5. Un fabricante de pegantes produce 5 clases de productos que se pueden fabricar con la misma
maquinaria, con los correspondientes costos de adecuacin y operarios. Desea determinar el orden
en que debe producir estos 5 productos para que el costo sea mnimo. La tabla de costos por cambio
de actividad se muestra en la tabla 2, en donde m indica que no se puede llevar a cabo el intercambio
de la actividad i por la actividad j.

i 1 2 3 4 5
1 0 m 9 m 7
2 6 0 4 6 9
3 4 m 0 5 7
4 7 5 6 0 9
5 m 9 7 m 0
Tabla 2.

6. Use el procedimiento (1) del algoritmo de Floyd-Warshall para hallar la matriz de distancias mnimas
y la matriz de caminos para los siguientes grafos
2 3 4 5
1 2 3 1 2 3

5 2 4
2 2 1

2 10 2 5
4 5 6 4 1 1 4

4 2
1
a) b)
1 10
7 7 6 5

7. Use el procedimiento (2) del algoritmo de Floyd-Warshall para hallar la matriz de distancias mnimas
del siguiente grafo.
1

2 3 5
1
4 6
2 4 5

3 5 7

A. Caicedo B., G. Wagner de G., R. M. Mndez

 ulo
pt
Ca

7 RBOLES

Uno de los elementos de la teora de grafos ms ampliamente aplicados es el concepto de rbol,

el cual es muy usado al solucionar problemas de redes locales de comunicacin.

7.1 Conceptos Bsicos

Una definicin amplia del concepto de rbol es la siguiente:

Definicin 7.1
Un grafo G conexo que no tenga ciclos es llamado un rbol.

Dicho de otra forma se tiene:

Definicin 7.2
Un grafo G = (N, A) es llamado un rbol si G es conexo y acclico.

Desde el punto de vista de las relaciones en un conjunto finito de nodos, un rbol se puede definir de la
siguiente forma:

Definicin 7.3
Sea N un conjunto finito de nodos (vrtices) y T una relacin en N . Se dice que T es un rbol si
existe un nodo v0 en N con la propiedad de que haya una trayectoria nica en T de v0 a cualquier
otro vrtice en N , pero ninguna trayectoria de v0 a v0

El vrtice v0 es nico y es llamado la raz del rbol T ; a T se le llamar rbol arraigado en v0 y se

notar (T, v0 )

83
84 RBOLES

Ejemplo 1
Los grafos de la figura 1 son rboles
b b b b

b b b b

b b b b b

b b b

Figura 1.

Ejercicio 1
Determinar cules de los grafos de la figura 2 son rboles
b b b b

b
b b b b b b b b

b b b b

b b

b b
b

b b

Figura 2.

Algunas de las propiedades simples de un rbol se encuentran en el siguiente teorema.

Teorema 1

Los siguientes enunciados son equivalentes para un grafo G = (N, A) con n vrtices y m aristas:
1. G es un rbol
2. Existe exactamente una trayectoria entre cualquier par de vrtices en G
3. G es conexo y m = n 1
4. G es conexo y removiendo cualquier arista, G deja de ser conexo
5. G es acclico y m = n 1
6. G es acclico y adicionando alguna arista se crea un ciclo

Definicin 7.4
Un vrtice v de un digrafo se dice ser una raz del digrafo si todos los vrtices del mismo son
accesibles desde v

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Conceptos Bsicos 85

Definicin 7.5
Un rbol con raz (o rbol dirigido) es un digrafo tal que posee una raz y su grafo asociado es un
rbol

En un rbol arraigado en v0 , la trayectoria entre v0 y cualquier otro vrtice vn es nica y la longitud de

dicha trayectoria se llama el nivel del vrtice vn

El nivel donde terminan las aristas adyacentes a v0 se llaman vrtices de nivel 1 y se considera que v0
est en el nivel 0. A v0 se le llama tambin antecesor o padre de los vrtices del nivel 1 y a stos se les
llama vstagos o descendientes de v0 . Recursivamente, los descendientes de v0 pueden ser designados
como races de los subrboles obtenidos al borrar la raz del rbol original.

En la figura 3 se muestra un rbol con sus correspondientes niveles o grupos de descendientes.

v0 nivel 0

v1 v2 v3 nivel 1

v4 v5 v6 v7 v8 v9 nivel 2

Figura 3.

La relacin antecesor vstago se mantiene entre los niveles, por ejemplo: v1 es antecesor de los vstagos
v4 , v5 y v3 es antecesor de los vstagos v7 , v8 , v9

Definicin 7.6
El nmero de niveles de un rbol T se llama altura del rbol o nivel del rbol o profundidad del
rbol.

La anterior definicin es equivalente a decir que la longitud de la trayectoria ms larga desde la

raz es la profundidad o nivel del rbol arraigado.

Definicin 7.7
Los vrtices de un rbol que no tengan vstagos se les llama hojas del rbol.

Ejemplo 2
En el rbol de la figura 3 las hojas son v4 , v5 , v6 , v7 , v8 , v9

Definicin 7.8
La altura de un nodo en un rbol es la longitud de la trayectoria ms larga desde ese nodo a cada
hoja. La profundidad de un nodo es la longitud de la trayectoria desde la raz hasta ese nodo.

A. Caicedo B., G. Wagner de G., R. M. Mndez

86 RBOLES

Cuando al construir un rbol se introducen los conceptos de relacin y de niveles, se considera que el
rbol est siendo construido en forma orientada. (rbol orientado o dirigido).

Al dibujar el grafo dirigido de un rbol se puede introducir algn ordenamiento para cada nivel, arreglan-
do (numerando) los vstagos de izquierda a derecha. A un rbol de este tipo se le llama rbol ordenado.
El rbol de la figura 3 es un rbol ordenado.

Ejemplo 3
El siguiente rbol (figura 4) es ordenado segn un orden alfabtico
a

b c

d e f g

h i

Figura 4. Arbol ordenado

7.2 Subrboles

Sea (T, v0 ) un rbol arraigado sobre el conjunto N de nodos. Sea v un vrtice de T y B el conjunto que
consta de v y todos sus descendientes. B N .

Sea T (v) la restriccin de la relacin T a B que es T (B B) entonces T (v) tambin es un rbol

arraigado con raz v. Luego T (v) es un subrbol de T .

Definicin 7.9
Un subrbol T (v) est compuesto por el nodo v y todos sus descendientes.

Ejemplo 4
El rbol siguiente es trinario no ordenado y de l se pueden sacar tres subrboles: T (v5 ), T (v4 ), T (v2 )
(figura 6)
v3

v5 v4 v2

v9 v6 v10 v7 v8

Figura 5.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 rbol Binario 87

v5 v4 v2

v9 v6 v10 v7 v8

T (v5 )
T (v4 ) T (v2 )

Figura 6.

7.3 rbol Binario

Un concepto muy importante a tener en cuenta en el estudio de rboles es su clasificacin segn el nmero
de descendientes que posea cada nodo

Definicin 7.10

Si n Z+ , se dice que T es un rbol n-ario si cada vrtice tiene mximo n vstagos.

Si todos los vrtices de T , excepto las hojas, tienen exactamente n vstagos, se dice que T es un
rbol n-ario completo.
Particularizando, un rbol binario es aquel que tiene como mximo dos descendientes (vstagos)
para cada vrtice excepto para las hojas.

Definicin 7.11

Un rbol binario es un conjunto finito de cero o ms nodos tal que

1. Existe un nodo denominado la raz del rbol.
2. Cada nodo puede tener 0, 1 2 vstagos conocidos como vstago izquierdo y vstago derecho.

Ejemplo 5
Los rboles de la figura 7 son binarios. El de la derecha es un rbol binario completo.
b b

b b
b b

b b b b

b b b
b b

b b b

Figura 7.

A. Caicedo B., G. Wagner de G., R. M. Mndez

88 RBOLES

Definicin 7.12
Un rbol binario se considera equilibrado o balanceado si al seleccionar uno cualquiera de sus
nodos, cada uno de los subrboles que penden de l tiene un nmero de nodos que no difiere en
ms de uno, de los otros subrboles del nodo.

Un tipo de rbol muy usado al estructurar datos son los rboles parcialmente balanceados o rboles AVL
llamados as en honor a sus creadores, Adelson, Velskii y Landis.

Definicin 7.13
Un rbol es parcialmente balanceado por altura o AVL cuando la diferencia de altura de
cualquiera de los subrboles que penden de un nodo del rbol no es mayor de uno.

Definicin 7.14
Si T es un rbol con raz y n es el mayor nivel de T , entonces T tiene altura n y T es balanceado
si el nivel del cualquier hoja es n o n 1.

Ejemplo 6
El siguiente rbol no es un rbol AVL
b

b b

b b b b

b b b b

b b

Figura 8.

Teorema 2

Un rbol binario completo de altura h tiene a lo mximo 2h vrtices en el nivel h

Prueba
La prueba se hace por induccin sobre h. Como la raz es el nico vrtice en el nivel cero,
entonces existen 2 o cero vrtices adyacentes a la raz y estos estn en el nivel 1.
Asmase que no hay ms de 2k vrtices en el nivel k. Considrese el nivel k + 1. Cada vrtice
en este nivel debe ser adyacente a un slo vrtice en el nivel k. Como cada vrtice en el nivel k
tiene grado 1 3 entonces l es adyacente a cero o 2 vrtices en el nivel k + 1. Luego, el nmero
de vrtices en el nivel k + 1 no puede ser mayor de 2 veces el nmero de vrtices en el nivel k.
Si Nk = nmero de vrtices en el nivel k, entonces:


Nk+1 2Nk 2 2k = 2k+1

A. Caicedo B., G. Wagner de G., R. M. Mndez

 rboles Etiquetados 89

Corolario
Un rbol binario completo de altura h tiene como mximo 2h+1 1 vrtices
Prueba
Por el teorema anterior se sabe que en el nivel k hay como mximo 2k vrtices. As, el nmero
total de vrtices en el rbol es a lo mximo
1 2h+1
1 + 2 + 4 + . . . + 2k + . . . + 2h = = 2h+1 1
12

7.4 rboles Etiquetados

Un rbol especfico se puede usar para modelar un problema o para usarlo para un propsito particular;
para tal efecto conviene etiquetar los vrtices o las aristas y as poder usar ms fcilmente las propiedades
de los rboles en la computacin.

Una de las aplicaciones ms simples de los rboles etiquetados es usarlos para representar expresiones
algebraicas.

Ejemplo 7
La expresin algebraica:
(7 (5 y)) + ((y + 3) (8 y))
se puede representar mediante el rbol etiquetado de la figura 9

7 +

5 y y 3 8 y

Figura 9.

Se etiqueta el nodo raz con el operador central (+), los dos vstagos de la raz se etiquetan con los
operadores centrales de las expresiones de argumentos izquierdo y derecho. Si algn argumento es una
constante o una variable y no una expresin, se etiqueta el vstago correspondiente con dicha constante
o variable.

Reglas para representar expresiones:

a. Cada hoja es etiquetada por un solo operando

b. Cada nodo interior es etiquetado por un operador

A. Caicedo B., G. Wagner de G., R. M. Mndez
90 RBOLES

Ejemplo 8
El rbol de la figura 10 representa la expresin:

(x (y (x + y))) ((3 (2 y)) 7)

7.5 rbol Posicional

Sea (T, v0 ) un rbol n-ario. Cada vrtice tiene como mximo n vstagos. Suponiendo que cada vrtice
tiene exactamente n vstagos que se pueden ordenar del 1 al n. Si alguno de los vstagos en la suce-
sin se elimina o no aparece, los restantes se etiquetarn con la posicin que ocuparan en la sucesin
hipottica; por lo tanto los vstagos de cualquier vrtice estarn etiquetados con nmeros distintos 1, 2, . . .

Un rbol etiquetado en esta forma se le llama rbol posicional

x 7

y + 3

x y 2 y

Figura 10.

Ejemplo 9
El rbol de la figura 11 es 3-ario posicional.

1 3

1 2 1 2 3

1 3 1 2 3

1 2 3 1 2 3

Figura 11.

Cuando se trata de un rbol binario, las posiciones de los vstagos potenciales se acostumbra etiquetarlas
como Izquierdo (I) y derecho (D), ver figura12.
A. Caicedo B., G. Wagner de G., R. M. Mndez
 Otras Formas de rboles Ordenados 91

Definicin 7.15

Sea T un rbol binario posicional con raz v. Si vI existe, al subrbol T (vI ) se le llama subrbol
izquierdo de T , y si vD existe, al subrbol T (vD ) se le llama subrbol derecho de T

T (vI ) es tambin un rbol binario posicional con raz en vI , y T (vD ) es un rbol binario
posicional con raz en vD

I D

I D D

D D I D

I I

Figura 12.

7.6 Otras Formas de rboles Ordenados

A) rbol posicional 3-ario, ordenado mediante etiquetamiento lexicogrfico numrico

0b

1
b b b
2 3

1.1 2.1 3.3

b b b b b b
3.2
1.2 2.3

b b b b b b b b b

1.1.1 1.1.2 1.1.3 2.1.2 2.1.3 3.2.1 3.2.2 3.2.3 3.3.3

Figura 13.

B) rbol binario posicional, ordenado mediante etiquetamiento lexicogrfico alfabtico

b
r

a b
b b

a.a a.b b.a b.b

b b b b

b b b b b b b b
a.a.a a.a.b a.b.a a.b.b b.a.a b.a.b b.b.a b.b.b
Figura 14.

A. Caicedo B., G. Wagner de G., R. M. Mndez

92 RBOLES

C) rbol binario posicional, ordenado mediante etiquetamiento binario

b
r

0 1
b b

0.0 0.1 1.0 1.1

b b b b

b b b b b b b b

0.0.0 0.0.1 0.1.0 0.1.1 1.0.0 1.0.1 1.1.0 1.1.1

Figura 15.

7.7 Representacin Matricial

Para facilitar su programacin mediante un lenguaje de computacin, los rboles binarios se pueden
representar mediante arreglos matriciales o mediante listas encadenadas. En esta seccin se har una
introduccin a la representacin matricial.

En la representacin matricial se usan dos arreglos: vstagos izquierdos y vstagos derechos.

Si n es el nmero de vrtices de un rbol binario, entonces: V AST IZQ[i] = j si y solo si j es un

vstago izquierdo de i. Si i no tiene vstagos izquierdos, entonces V AST IZQ[i] = 0.

Similarmente: V AST DER[i] = j si y solo si j es un vstago derecho de i. Si i no tiene vstagos derechos,

entonces, V AST DER[i] = 0.

Ejemplo 10
En la figura 16 se muestra un rbol binario no posicional y su correspondiente representacin matricial
i hijoizq hijoder
1 2 6 1
2 3 4
3 0 0
2 6
4 0 5
5 0 0
6 7 8 3 4 7 8
7 0 0
8 0 9
9 0 0 5 9

Figura 16.

Ejemplo 11
La figura 17 muestra un rbol binario etiquetado y su correspondiente representacin matricial

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Representacin Secuencial 93

1
i hijoizq dato hijoder
1 2 3
2 4 5
3 6 7 2 3
4 0 a 0
5 0 b 0
6 0 c 0
7 8 9 a b c
8 0 d 0 4 5 6 7
9 0 e 0 8 9
d e

Figura 17.

7.8 Representacin Secuencial

Si T es un rbol binario completo o casi completo, entonces una forma eficiente de mantener a T en
memoria es mediante una representacin secuencial o arreglo lineal T , establecido de la siguiente forma:

a. La raz se guarda en T [1]

b. Si un nodo n est en T [k] entonces su vstago izquierdo est en T [2 k] y su vstago derecho est
en T [2 k + 1]

c. Si un subrbol es vaco se representa con NULO. T [1] = N U LO indica que el rbol est vaco.

Ejemplo 12
Para el rbol de la figura 18 la representacin secuencial se muestra en la tabla siguiente

I 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...
T [I] 60 31 70 10 40 100 14 20 80 ...

1
31 60
2 3

40 70
4 5 7
10 100
14 20 80
9 19 14

Figura 18.

A. Caicedo B., G. Wagner de G., R. M. Mndez

94 RBOLES

7.9 Representacin Enlazada

Un rbol binario tambin se puede mantener en memoria mediante una representacin enlazada de 3
arreglos paralelos que se pueden llamar IZG, DAT O, DER y una variable puntero llamada RAIZ que
contendr la posicin de la raz R de T .

Cada nodo N de T corresponde a una posicin K, tal que:

DAT O[K] : contiene los datos del nodo N .
IZQ[K] : contiene la localizacin del vstago izquierdo del nodo N
DER[K] : contiene la localizacin del vstago derecho del nodo N .

Una representacin que haga uso de estos tres conceptos se llama una lista doblemente enlazada
o doblemente ligada en donde la unidad de almacenamiento es la clula que contiene un dato y los dos
apuntadores. Simblicamente una clula se representa con la figura 15.

b
DAT O b

Figura 19.

Cada clula corresponde a un nodo; la parte del dato contiene el valor de la etiqueta del nodo. Los apun-
tadores izquierdo y derecho se dirigen a los vstagos izquierdo y derecho, si es que existen. Si un vstago
no existe el apuntador se simboliza con b

Ejemplo 13
Para el rbol de la figura 20a, la representacin simblica como una lista doblemente enlazada es el
esquema de la figura 20b, y la implementacin de esa lista mediante tres arreglos se muestra en la
tabla 1.
a
1) b
Inicio b

b
2) b
a b

e c
3) b
b b b
c b b
d b

4) 5)
f d
6) b
e b b
f b b g b

7) 8)
g
a) Figura 20.
b)

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Conversin de un rbol General a Binario 95

i IZQ DAT O DER

1 2 nil 0
2 3 a 0
3 6 b 4
4 0 c 5
5 0 d 0
6 0 e 7
7 0 f 8
8 0 g 0
Tabla 1.

7.10 Conversin de un rbol General a Binario

Para que un rbol A general pueda ser representado por cualquiera de los anteriores mtodos, debe ser
convertido primero en rbol binario B.

Algoritmo de Conversin

a. Tomar la raz de A como la raz de B

b. Enlazar el nodo raz con el camino que conecta el nodo ms a la izquierda

c. Enlazar este nodo con los restantes descendientes del nodo raz en un camino, formndose as el
nivel 1 del nuevo rbol

d. Repetir los pasos 2 y 3 con los nodos del nivel 2 de A, enlazando siempre en un solo camino todos
los hermanos. Repetir todos estos pasos hasta llegar al nivel ms alto

e. Girar el rbol resultante aproximadamente 30o a la derecha para poder diferenciar entre los subr-
boles izquierdo y derecho de B

Ejemplo 14
La figura 21 muestra un rbol general y el correspondiente rbol binario obtenido al aplicar el
algoritmo anterior.
a a
b
b c d e c
f d
e f g h i j g h
k i
k l l j
Figura 21.

A. Caicedo B., G. Wagner de G., R. M. Mndez

96 RBOLES

7.11 Recorrido de un rbol Binario

Existen problemas de la estructuracin de datos donde es necesario examinar cada vrtice de un rbol una
sola vez, en un orden especfico. El proceso de visitar cada vrtice de un rbol en algn orden especial
se llama recorrer, atravesar o analizar el rbol. Existen tres formas de recorrer un rbol binario
posicional: recorrido pre-orden, recorrido in-orden y recorrido post-orden. Las subrutinas para cada uno
de estos recorridos se muestran a continuacin, en forma de seudocdigo.
A. Recorrido pre-orden o anterior o jerrquico
Subrutina Anterior(T ,v)
1. Visitar raz (v)
2. Si vI existe llamar Anterior(T (vI ),vi )
3. Si vD existe llamar Anterior(T (vD ),vD )
Fin subrutina
B. Recorrido in-orden o interior o simtrico
Subrutina Interior(T ,v)
1. Si vi existe llamar Interior(T (vi ),vi )
2. Visitar raz (v)
3. Si vD existe llamar Interior(T (vD ),vD )
Fin subrutina
C. Recorrido post-orden o posterior
Subrutina Posterior(T ,v)
1. Si vi existe llamar Posterior(T (vi ),vi )
2. Si vD existe llamar Posterior(T (vD ),vD )
3. Visitar raz (v)
Fin subrutina
De estas tres formas de recorrer un rbol binario, la ms usual y prctica es el recorrido in-orden, el cual
se puede describir en la siguiente forma:
Para cada vrtice en el rbol, comenzando por la raz, imprima todos los elementos del subrbol izquier-
do, comenzando por la hoja izquierda. Luego imprima el vrtice. Despus imprima todos los vrtices del
subrbol derecho del vrtice, empezando por la hoja derecha.

Ejemplo 15
Aplicar el recorrido in-orden al rbol de la figura 22
K

B T

A L Z

Figura 22.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Recorrido de un rbol Binario 97

Considerando K como la raz del rbol, iniciamos el recorrido por el subrbol izquierdo, visitando los
nodos K, B, A. Bajamos hasta la hoja izquierda A e imprimimos su valor (A). Visitamos la raz del
subrbol e imprimimos su valor (B); como no existe rama derecha para este subrbol, continuamos
el recorrido y visitamos la raz del rbol (K). Efectuamos el mismo proceso para el subrbol derecho.
El recorrido efectuado se muestra en la figura 22 con lneas punteadas. Siguiendo este recorrido se
obtiene: A, B, K, L, N, R, T, Z

Otra forma de visualizar este proceso es encerrar todos y cada uno de los subrboles en cajas y empezar a
imprimir lo que est contenido en cada uno de ellas, a partir de las cajas ms internas. Se analiza primero
el subrbol izquierdo y luego el derecho.

Ejemplo 16
Recorrer el rbol de la figura 23 en in-orden aplicando la metodologa de encerrar los subrboles en
cajas

x y 2

2 3 5
1 x +

7
y 20

9 10
8
6
4

Figura 23.
Haciendo el recorrido se obtiene:

subrbol izquierdo raz subrbol derecho

(x y) (2 (x (y + 20)))

Ejemplo 17
Ejecutar los recorridos PRE-ORDEN, IN-ORDEN y POST-ORDEN al siguiente rbol
r

a b

c d e f

g h i
Figura 24.

A. Caicedo B., G. Wagner de G., R. M. Mndez

98 RBOLES

a) Recorrido PRE-ORDEN o anterior

Tr = r, Ta , Tb

= r, a, Tc , Td , Tb r

= r, a, c, d, Tg , Th , Ti , Tb a b

= r, a, c, d, g, h, i, b, Te , Tf c d e f

= r, a, c, d, g, h, i, b, e, f g h i
Figura 25.

Nota: la lnea punteada indica el sentido del recorrido. La cabeza de flecha indica que se lee dicho
nodo. La raz se lee de primero.
El recorrido pre-orden tambin es llamado recorrido RAICES-HOJAS porque para cada subarbol
primero se lee la raz y luego las hojas

B) Recorrido IN-ORDEN o interior

Este recorrido tambin es llamado recorrido HOJAS-RAIZ-HOJAS porque para cada subrbol
primero se leen las hojas del hijo izquierdo, luego la raz y despus las otras hojas del subrbol.
Primero se recorre el subrbol izquierdo, luego la raz y despus el subrbol derecho.
Tr = Ta , r, Tb

= Tc , a, Td , r, Tb r

= c, a, Tg , d, Th , Ti , r, Tb a b

= c, a, g, d, h, i, r, Te , b, Tf c d e f

= c, a, g, d, h, i, r, e, b, f g h i
Figura 26.

C) Recorrido POST-ORDEN o posterior

Este recorrido tambin es llamado recorrido HOJAS-RAICES porque para cada subrbol primero se
leen las hojas y luego la raz. La raz principal del rbol se lee de ltimo.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Notacin Polaca 99

Tr = Ta , Tb , r

= Tc , Td , a, Tb , r r

= c, Tg , Th , Ti , d, a, Tb , r a b

= c, g, h, i, d, a, Te , Tf , b, r c d e f

= c, g, h, i, d, a, e, f, b, r g h i
Figura 27.

7.12 Notacin Polaca

En la seccin anterior vimos que los recorridos en preorden, inorden y postorden producen formas de
listas de los nodos de un rbol enraizado ordenado. Si se etiquetan los nodos en forma tal que el rbol
represente o contenga una expresin algebraica, las listas obtenidas en cada recorrido se llama notacin
polaca de la expresin algebraica.

El recorrido preorden produce la notacin polaca directa o prefija

El recorrido inorden produce la notacin infija o algebraica normal
El recorrido postorden produce la notacin polaca inversa o sufija

Cuando el rbol representa una expresin algebraica, el recorrido inorden produce la expresin alge-
braica, pero es indispensable que cada vez que se recorra un subrbol se agrupe su contenido por medio
de parntesis o corchetes para que no se presenten ambiguedades al evaluar numricamente la expresin.

Cuando el recorrido ha sido preorden y postorden las listas no necesitan los signos de agrupamiento
porque estos listados determinan de manera nica el rbol y por lo tanto a la expresin algebraica origi-
nal. Estas notaciones no son ambiguas sin parntesis.

Al evaluar las expresiones en notacin polaca se lee la expresin de izquierda a derecha, buscando cadenas
de la forma:

a. F x y, en la notacin polaca directa

b. x y F , en la notacin polaca inversa

donde F =operador algebraico, x, y =operandos (variables)

Ejemplo 18
La expresin algebraica [(x + (a b)) y] [((a (b + x)) y) x] da origen al siguiente rbol
binario
A. Caicedo B., G. Wagner de G., R. M. Mndez
100 RBOLES

+ y x

x y

a b a +

b x
Figura 28.

a) El recorrido inorden retornar la expresin algebraica dada.

b) El recorrido preorden produce:
+ x aby a + bxyx
Notacin polaca directa de la expresin algebraica inicial
c) El recorrido postorden produce:
xab xy abx + y x
Notacin polaca inversa de la expresin algebraica inicial.
La evaluacin numrica de las dos ltimas expresiones cuando a = 10, b = 2, x = 3, y = 4 es:
Preorden (F x y)
+ 3 10 2 4 10 + 2 3 43
| {z } | {z }
+ 3 5 4 10 5 43
| {z } | {z }
8 4 2 4 3
| {z } | {z }
4 (2) 3
| {z }
4 (6)
| {z }
4/(6) = 2/3

Postorden (x y F )
3 10 2 + 4 10 2 3 + 4 3
| {z } | {z }
3 5 + 4 10 5 4 3
| {z } | {z }
8 4 2 4 3
| {z } | {z }
4 (2) 3
| {z }
4 (6)
| {z }
4/(6) = 2/3

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Bsqueda y Ordenamiento con rboles Binarios 101

7.13 Bsqueda y Ordenamiento con rboles Binarios

Los algoritmos de bsqueda y ordenamiento tienen un lugar preponderante en la teora de la computacin

puesto que facilitan la tarea de organizar grandes grupos de datos y buscar un dato especfico dentro de
un archivo de datos. En esta unidad se har uso de la estructura de rbol para realizar un ordenamiento
de un conjunto de elementos.

Una de las estructuras de datos ms usadas en la programacin es la bsqueda binaria dentro de un

arreglo de datos. Esta estructura se puede modelar fcilmente mediante un rbol binario de bsqueda, el
cual permite ordenar arreglos, buscar un elemento determinado del arreglo e insertar un elemento dentro
del arreglo.

Definicin 7.16 rbol Binario de Bsqueda

Sea T un rbol binario. T se dice ser un rbol binario de bsqueda o rbol ordenado, si cada
nodo N de T cumple la siguiente propiedad: El valor de N es menor que cualquier valor de su
subrbol derecho y es mayor que cualquier valor de su subrbol izquierdo

Ejemplo 19
Sea A = {8, 45, 19, 50, 25, 30, 56, 48, 80} un arreglo. El rbol de la figura 29 es un rbol binario de
bsqueda para A.
45
< >

19 50
< > >

8 25 56
> < >

30 48 80

Figura 29.

Bsqueda:
Para proceder a buscar un elemento k en el rbol binario se procede mediante el siguiente algoritmo:
Algoritmo de Bsqueda, insercin y ordenamiento
Supngase que k es un tem de informacin dado. N es cualquier valor del arreglo.
paso 0. Construir un rbol binario de bsqueda. Hacer el nodo raz igual a N
paso 1. a) Si k < N proceder con el hijo izquierdo de N
b) Si k > N proceder con el hijo derecho de N
paso 2. Repetir paso 1 hasta que se cumpla una de las siguientes condiciones:
a) Se encuentra un nodo N tal que k = N . Se termina la bsqueda.
b) Se encuentra un subrbol vaco, lo que indica que la bsqueda ha fallado.
Se inserta k en el lugar del subrbol vaco.
paso 3. Se recorre el rbol In-orden para hallar la lista ordenada

A. Caicedo B., G. Wagner de G., R. M. Mndez

102 RBOLES

En otras palabras lo que se hace es iniciar la bsqueda a partir de la raz R del rbol y se desciende por
uno de sus subrboles hasta que se logr encontrar a k.

Ejemplo 20
Dado el rbol de bsqueda de la figura 30, ubicar el elemento k = 20 en el arreglo A =
{17, 8, 38, 40, 26, 19, 35, 52, 45}

35

17 40

8 26 38 52

19 45
Figura 30.

Siguiendo el algoritmo anterior se tiene:

paso 0. Construir el rbol de bsqueda. Escoger arbitrariamente a 35 como riz

paso 1 y 2.

a. Se compara k = 20 con la raz N = 35. Como 20 < 35 se procede con el hijo izquierdo de
35 que es 17
b. Se compara k = 20 con 17. Como 20 > 17 se procede con el hijo derecho de 17 que es 26
c. Se compara k = 20 con 26. Como 20 < 26 se procede con el hijo izquierdo de 26 que es 19
d. Se compara k = 20 con 19. Como 20 > 19 se procede con el hijo derecho de 19, pero 19
no tiene hijo derecho. No se puede encontar el nmero buscado. Se inserta k = 20 como
hijo derecho de 19. El nuevo rbol con k = 20 insertado es:

35

17 40

8 26 38 52

19 45

20
Figura 31.

El camino recorrido al aplicar el algoritmo se muestra con lnea doble.

paso 3. Se recorre el rbol en In-orden y se obtiene A = {8, 17, 19, 20, 26, 35, 38, 45, 52}

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Bsqueda y Ordenamiento con rboles Binarios 103

Ordenamiento:
Para realizar un ordenamiento usando un rbol binario, existen diversos mtodos, entre ellos los ms
conocidos son el mtodo de FOSTER y el mtodo de FLOYD, siendo el de Foster el ms fcil de
aplicar.

Algoritmo de Foster
paso 1. Se forma un rbol binario AVL de acuerdo con las siguientes normas:
a) El primer elemento del arreglo se usa como nodo de la raz del rbol.
b) Cualquier nuevo elemento se compara con la raz, en forma recursiva, hasta encontrar su posicin
en el rbol
c) Si el elemento es menor o igual a la raz, se coloca en el subrbol izquierdo
d) Si el elemento es mayor que la raz se coloca en el subrbol derecho
e) Para cualquier nodo, todos los valores del subrbol izquierdo del nodo son menores o iguales al
valor del nodo. Todos los valores del subrbol derecho deben ser mayores que el valor del nodo
f) Si el rbol est sesgado se pueden usar algoritmos de balanceo para corregirlo.
paso 2. Se recorre el rbol en in-orden para obtener la lista ordenada de los elementos del arreglo.

Ejemplo 21
Dado el arreglo {D, F, E, B, A, C, G} al aplicarle el algoritmo de Foster se obtiene el rbol de bsque-
da de la figura 32.
D

B F

A C E G

Figura 32.

Se escoge D como raz. Se ubica F en el subrbol derecho porque F > D; se ubica E en el subrbol
izquierdo de F porque E < F . Se ubica B en el subrbol izquierdo de D porque B < D. Se ubica A
en el subrbol izquierdo de B porque A < B. Se ubica C en el subrbol derecho de B porque C > B.
Se ubica G en el subrbol derecho de F porque G > F

El recorrido in-orden produce el arreglo ordenado {A, B, C, D, E, F, G}

A. Caicedo B., G. Wagner de G., R. M. Mndez

104 RBOLES

Ejercicios Captulo 7

a. Determinar cules de los grafos de la figura 33 son rboles

b b b

b b b
b

b b b

b b
b b b

b b b b b b

Figura 33.

b. Para el rbol de la figura 34 establecer cada uno de los subrboles

a

b c d

e f

g h i

Figura 34.

c. Para el rbol de la figura 34 establecer: a) su altura o profundidad; b) cules son sus hojas y c) la
altura de los nodos a, b y c

d. Trazar un rbol ordenado segn un orden alfabtico y de 3 niveles

e. Trazar un rbol trinario ordenado de 4 niveles

f. Trazar un rbol binario incompleto y uno completo

g. Trazar un rbol binario equilibrado o balanceado

h. Determinar si el rbol binario de la figura 35 es AVL y explique por qu.

b

b b

b b b b

b b

Figura 35.

i. Trazar un rbol binario incompleto de profundidad 4

j. Trazar un rbol binario completo de altura 3

k. Trazar un rbol trinario incompleto de altura 2

A. Caicedo B., G. Wagner de G., R. M. Mndez
 Bsqueda y Ordenamiento con rboles Binarios 105

l. Representar con un rbol binario la siguiente expresin

(3 + (x y) 8) (6 y) + ((3 y 5) 9 x)

m. Escribir la expresin algebraica representada por el siguiente rbol

+
1
6 3
3 +
3 + x y

5 x x y

Figura 36.

n. Elaborar el anlisis (recorrido) anterior, interior y posterior de los rboles de la figura 37

x a

y z
2 b d
s t
+ 1 c i k e
u

v 2 3 g h j f
a) b) Figura 37.
c)

. Representar en forma de listas enlazadas los tres rboles del ejercicio anterior
o. Convertir en binario el rbol de la figura 38
a

b c d

e f g h i

j k l
Figura 38.

p. Evalue las siguientes expresiones dadas en notacin polaca directa

a) 3 5 2 2
b) 3 5 2 2
c) 3 5 2 2
d) + 6 3 3 7 3
A. Caicedo B., G. Wagner de G., R. M. Mndez
106 RBOLES

e) 2 + 2 5 + 3 4 2

q. Evalue las siguientes expresiones dadas en notacin polaca inversa

a) 3 3 4 5 1 + +
b) 3 3 + 4 + 5 1
c) 3 3 4 + 5 1 +
d) 6 3 3 + 7 3
e) 3 2 4 2 + 5 2

r. Escriba en notacin polaca directa e inversa las siguientes expresiones

a) (5x + 9)3
b) (x + 2y)/(x 2y)
c) (a b) (c + (d e))

s. Construir el rbol de bsqueda para el siguiente arreglo: {35, 20, 12, 40, 60, 18, 38, 26}

t. Mediante el algoritmo BUSQUEDA, insertar el elemento k = 22 en el arreglo del ejercicio anterior.

u. Dado el arreglo {C, F, B, A, G, H, E} aplicar el algoritmo de FOSTER para ordenarlo ascendente-

mente.

v. Determinar si k = 2 se encuentra en el siguiente arreglo, usando un algoritmo de bsqueda binaria

M {18, 4, 18, 40, 17, 15, 2, 9, 14, 7, 9, 8}

w. Mediante un rbol binario de bsqueda insertar el valor k = 2 en el siguiente arreglo y ordenar el

arreglo
R = {7, 7, 8, 22, 1, 6, 9, 18, 14, 0, 15, 5, 5}

x. Ordenar ascendentemente el arreglo A = {x, a, p, m, b, c, t, y, d, o, q} usando el algoritmo de Foster

y. Construir un rbol de bsqueda para el siguiente arreglo

B = {35, 72, 2, 12, 8, 4, 18, 30, 32, 3, 26}

e insertar k = 22 usando el algoritmo de bsqueda e insercin.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 ulo
pt

8
Ca

RBOLES NO DIRIGIDOS

En la unidad anterior se han estudiado rboles en los cuales se ha especificado claramente

un nodo raz, y se ha considerado su anlisis haciendo un recorrido descendente desde la raz
hasta sus hojas, ahora en esta unidad se estudiar un nuevo tipo de rbol al cual no se le
considera un nodo raz y que se puede recorrer en cualquier sentido. Esta clase de rboles son
de gran aplicacin en el estudio de redes elctricas, de redes locales de comunicacin entre
computadores, sistemas de riego, etc.

8.1 rbol No Dirigido

Definicin 8.1
Un rbol no dirigido es aquel en el que todas las aristas son bidireccionales, no posee un nodo raz
especfico y no se analiza teniendo en cuenta niveles de ubicacin de sus nodos

Ejemplo 1
Los dos rboles de la figura 1 son no dirigidos
b b

b b

b b

b b b

Figura 1.

Un rbol no dirigido sigue siendo un grafo conexo sin ciclos pero con la propiedad de que corresponde a
una relacin simtrica puesto que si a y b son dos nodos del rbol y existe la arista (a, b) entonces tambin
existe la arista (b, a).

Los siguientes teoremas ayudan a comprender el vnculo que hay entre relacin simtrica y rbol no
dirigido
107
108 RBOLES NO DIRIGIDOS

Teorema 1

Si es una relacin simtrica en un conjunto N entonces los siguientes enunciados son equivalentes:

a. es un rbol no dirigido con n 1 arcos

b. es conexa y acclica

Nota: Una relacin simtrica es conexa si existe una trayectoria en desde cualquier nodo a
cualquier otro nodo.

Teorema 2

Sea una relacin simtrica en N . Entonces es un rbol no dirigido si y slo si cualquiera de los
siguientes enunciados es verdadero

a. es acclica y si se aade a cualquier arista no dirigida, la nueva relacin no ser acclica.

b. es conexa y si cualquier arista no dirigida se remueve de , la nueva relacin no ser conexa.

c. es acclica con n 1 arcos

8.2 rbol Generado de Relaciones Conexas

Definicin 8.2
Si es una relacin simtrica conexa en un conjunto N , se dice que un rbol T en N es un rbol
generado por si T

En otras palabras, un rbol generado T es un rbol con exactamente los mismos nodos que y que se
puede obtener de al suprimir algunas aristas hasta que quede sin ciclos y siga siendo conexa.

Un rbol generado a partir de un grafo G tambin es llamado rbol expansor de G o rbol ge-
nerador de G o rbol de comunicacin de G porque hace que todos los nodos del grafo G queden
intercomunicados entre s.

Teorema 3

Un grafo G contiene un rbol generador si y solo si es conexo. Si el grafo es disconexo contiene un

rbol generador para cada componente conexa

Para verificar que un grafo conexo contiene un rbol generador se pueden seguir dos metodologas dife-
rentes:
Primera: comenzar con un grafo conexo y remover arcos sucesivamente en forma tal que en cada etapa
A. Caicedo B., G. Wagner de G., R. M. Mndez
 rbol Generador de Mnimo Peso 109

el subgrafo resultante sea conexo. Eventualmente al borrar algn arco el subgrafo se desconecta. Por el
enunciado b) del teorema 2, el subgrafo que se tiene hasta el momento es un rbol generador. Este rbol
tendr n 1 arcos, donde n es el nmero de nodos del grafo original.
Segunda: Esta segunda forma de trabajar es totalmente opuesta a la primera. Se comienza suponiendo
un rbol vaco, sin arcos, y se adiciona luego un arco cada vez, teniendo en cuenta que el arco adicionado
no forme un ciclo con los anteriores. Eventualmente la adicin de un arco ms crear un ciclo. El grafo
construido hasta ese paso ser un rbol.

Ejemplo 2
En la figura 2 se muestra una secuencia grfica de los pasos seguidos para obtener un rbol generador
a partir de un grafo dado, aplicando la primera metodologa.
b b b

b b b b b b b b b

b b b b b b

b b

b b b b b b

b b b b

Figura 2.

La segunda metodologa se puede resumir en el siguiente algoritmo:

Algoritmo Arbolgen
paso 0. Entrar el grafo G con n nodos y m arcos: a1 , a2 , . . . , am
paso 1. Hacer T = {N, }
paso 2. Para i = 1 hasta n hacer
a) Adicionar el arco ai al rbol T si l no crea un ciclo con arcos que ya existan en T
b) Si T contiene n1 arcos, imprimir T como el rbol generador y PARAR. En caso contrario
declarar que G no contiene un rbol generador y PARAR.

8.3 rbol Generador de Mnimo Peso

Definicin 8.3
Un grafo G con una funcin w = A(G) R+ es llamado un grafo pesado. Si a es un arco en
A(G) entonces w(a) ser el peso de a

A. Caicedo B., G. Wagner de G., R. M. Mndez

110 RBOLES NO DIRIGIDOS

Por lo general los valores asignados a los arcos representan costos, capacidad, longitud o algn otro
parmetro de inters en la vida real.

Definicin 8.4
Sea G un grafo conexo. Un rbol generador de G de mnimo peso es un rbol no dirigido tal que la
trayectoria nica que une cualquier par de nodos es de mmino valor

Cuando se tiene un grafo conexo pesado, es de mucha utilidad determinar cul es el rbol generador de
mnimo peso, puesto que con l queda determinada la forma de intercomunicar todos los nodos del grafo
con el mnimo costo o la mnima distancia, etc. Una aplicacin tpica ocurre en el diseo de redes de
comunicacin donde los nodos representan ciudades y las aristas son las posibles lneas de comunicacin
entre las ciudades. El valor asociado a cada arco representa el costo de seleccionar esa lnea para la red.

Se han diseado diversos algoritmos que hallan el rbol generador de mnimo peso, entre ellos se destacan
el de Sollin, el de Kruskal y el de Prim, siendo el ms conocido el de Kruskal que fue presentado en
1956. Este problema de hallar el rbol de mnimo peso ya haba sido estudiado por otros matemticos
anteriores a los ya citados, como es el caso del ingeniero electricista ruso Otakar Boruvka quien formul
un algoritmo bastante eficiente cuando enfrent el trabajo de la electrificacin del sureste de Moravia en
1928.

8.4 Algoritmo de Prim (Robert C. Prim, 1957)

Supngase N = {1, 2, 3, . . . , n}. El algoritmo de Prim comienza con un conjunto U inicializado con
cualquier nodo, por ejemplo {1}. Luego se hace crecer un rbol generador, arco por arco. En cada paso
se encuentra el arco ms corto (u, v) que conecta a U y N U y luego se adiciona v, el nodo en N U ,
a U . Se repite este paso hasta que U = N .

El algoritmo es resumido en los siguientes pasos:

Algoritmo de Prim
paso 0. Iniciar el grafo T con un solo nodo i escogido al azar. N = {i}, A = , T = ({i}, )
paso 1. Seleccionar el arco (i, j) cuya longitud es la menor entre todos aquellos arcos adyacentes a T .
Adicionar este arco (i, j) a T y j al conjunto de nodos de T
paso 2. Preguntar si T ya es un rbol que contiene todos los nodos de G y detenerse. En caso contrario
repetir el paso 1.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Algoritmo de Kruskal 111

Ejemplo 3
Aplicar el algoritmo de Prim para hallar el rbol de mmino peso a partir del grafo de la figura 3.
a b c
10 6

8
7 14

20 d 16

17

e
Figura 3.
Solucin

paso 0. A = . U = {e}. T = ({e}, )

paso 1. De los arcos adyacentes a T , el arco (e, c) es el de menor peso. Adicionar (e, c) a A y el
nodo c a U . T = ({e, c}, {(e, c)})
paso 2. T todava no es un rbol. Repetir paso 1.
paso 1. De los arcos adyacentes a T , el arco (c, b) es el de menor peso. Adicionar (c, b) a A y el
nodo b a U . T = ({e, c, b}, {(e, c)(c, b)})
paso 2. T an no es un rbol. Repetir paso 1.
paso 1. De los arcos adyacentes a T , el arco (b, d) es el de menor peso. Adicionar (b, d) a A y el
nodo d a U . T = ({e, c, b, d}, {(e, c)(c, b)(b, d)})
paso 2. T an no es un rbol. Repetir paso 1
paso 1. De los arcos adyacentes a T , el arco (d, a) es el de menor peso. Adicionar (d, a) a A y el
nodo a a U . T = ({e, c, b, d, a}, {(e, c)(c, b)(b, d)(d, a)})
paso 2. T ya es un rbol porque U = N . Parar

8.5 Algoritmo de Kruskal

Supngase que se tiene un grafo pesado G = (N, A) con N = {1, 2, . . . , n} nodos. Se inicia con T = (N, )
consistente de n nodos y sin arcos. Cada nodo es una componente conexa de s mismo. Cuando el al-
goritmo procede siempre se tendr una coleccin de componentes conexas y para cada componente se
seleccionarn aristas que formen un rbol. Para construir progresivamente las componentes se examinan
los arcos de A en orden creciente de peso. Si el arco conecta dos nodos en dos componentes diferentes,
entonces el arco se adiciona a T . Si conecta dos nodos en la misma componente se descarta pues podra
causar un ciclo. Cuando todos los nodos estn en una componente, T ser el rbol generador de mnimo
peso.

Algoritmo de Kruskal
paso 0. Iniciar T con n nodos y sin arcos. T = {1, 2, . . . , }.
paso 1. Crear una lista L de arcos, desde G, en orden ascendente de peso. Los arcos con el mismo
peso son ordenados arbitrariamente.
paso 2. Seleccionar el arco (i, j) del comienzo de L. Si este arco forma un circuito en T se borra de L
y se repite el paso 2; en caso contrario se transfiere de L a T .
paso 3. Si T es un rbol, PARAR; en caso contrario repetir el paso 2.

A. Caicedo B., G. Wagner de G., R. M. Mndez

112 RBOLES NO DIRIGIDOS

Ejemplo 4
Aplicar el algritmo de Kruskal para hallar el rbol generador de mnimo peso al grafo de la figura 4.
5
1 2

8 10

10 3

7 4

5 4
6
Figura 4.

Solucin

paso 0. Iniciar el rbol con los nodos de G y sin arcos. T = ({1, 2, 3, 4, 5}, )
paso 1. L = {(3, 4)(1, 2)(4, 5)(3, 5)(1, 3)(1, 5)(2, 3)}
paso 2. El arco (3, 4) se pasa de L a T , entonces
L = {(1, 2)(4, 5)(3, 5)(1, 3)(1, 5)(2, 3)}. T = ({1, 2, 3, 4, 5}, {(3, 4)})
paso 3. T no es un rbol de G. Repetir paso 2.
paso 2. El arco (1, 2) se pasa de L a T , entonces
L = {(4, 5)(3, 5)(1, 3)(1, 5)(2, 3)}. T = ({1, 2, 3, 4, 5}, {(3, 4)(1, 2)}). El arco (1, 2) no
forma un crculo en T
paso 3. T no es un rbol de G. Repetir paso 2
paso 2. El arco (4, 5) se pasa de L a T , entonces
L = {(3, 5)(1, 3)(1, 5)(2, 3)}. T = ({1, 2, 3, 4, 5}, {(3, 4)(1, 2)(4, 5)})
paso 3. T no es un rbol de G. Repetir paso 2
paso 2. El arco (3, 5) no se puede pasar de L a T porque forma un ciclo con arcos que ya estn
en T . El arco (3, 5) se borrar de L. El arco (1, 3) se pasa de L a T , entonces:
L = {(1, 5)(2, 3)}. T = ({1, 2, 3, 4, 5}, {(3, 4)(1, 2)(4, 5)(1, 3)}). El arco (1, 3) no forma
un ciclo en T
paso 3. T ya es un rbol de G, porque todos los nodos de G estn interconectados. Parar
El rbol recubridor de mnimo peso es:
5
1 2

6
5 4

Figura 5.

A. Caicedo B., G. Wagner de G., R. M. Mndez

 rbol Generador de Mnima Distancia 113

8.6 rbol Generador de Mnima Distancia

En un grafo pesado conexo G la distancia entre dos nodos cualquiera x e y se denota por d(x, y) y es
el mnimo valor de w(P ) tomado sobre todas las trayectorias P desde x a y, w(P ) es el peso de una
trayectoria P y es la suma de los pesos de todas las aristas de P . w(P ) tambin es llamada la longitud
de la trayectoria P .

En un rbol generador tambin se puede fijar un nodo como nodo origen y hablar entonces de dis-
tancias entre ese nodo y cualquier otro nodo.

Definicin 8.5
Un rbol generador de mnima distancia con nodo origen r es un rbol T que contiene una trayectoria
de mnima distancia desde r a cada nodo.

Definicin 8.6
Un rbol generador de mnimo peso en un grafo conexo G con nodo origen r, es un rbol T tal que
para cada nodo v de G, la longitud de la trayectoria nica en T desde r a v es igual a d(r, v)

Ejemplo 5
El rbol a) de la figura 6 es un rbol de mnima distancia y el rbol b) es un rbol de mnimo peso,
generados a partir del grafo G.
r 8 6
2 3

4 9 5
7 9 7
7
8 3
4 5 6

G
r 8 r 8 5
2 3 2 3

4 5 4
7

3 8 3
4 5 6 4 5 6

a) b)

Figura 6.

8.7 Algoritmo de Dijkstra (rbol de mnima distancia)

Como el problema de establecer un rbol generador a partir de un nodo origen en un grafo conexo G
se presenta frecuentemente al tratar de intercomunicar una central de comunicaciones con una serie de
puntos, es conveniente contar con un algoritmo rpido que establezca cul es el conjunto de aristas que se
A. Caicedo B., G. Wagner de G., R. M. Mndez
114 RBOLES NO DIRIGIDOS

deben tener en cuenta para formar el rbol de comunicacin. El algoritmo propuesto por E.W. Dijkstra,
que se presenta a continuacin, es muy adecuado para este tipo de problema.

Algoritmo de Dijkstra
paso 0. Verificar que G es un grafo conexo
paso 1. Entrar el grafo pesado G y establecer un nodo r como nodo origen
paso 2. Hacer T = {r}
paso 3. Para i=1 hasta N-1 hacer
begin
paso 4. Econtrar z un nodo en G T cuya distancia desde r sea mnima. Sea e un arco
desde z a un nodo de T y que est en alguna trayectoria de distancia mnima
desde z a r.
paso 5. Adicionar e a los arcos de T
Adicionar z a los nodos de T
Hacer T = (N (T ), A(T ))
end
paso 6. Imprimir T y PARAR.

Ejemplo 6
Aplicar el algoritmo de Dijkstra al grafo de la figura 7 a) para obtener el grafo generador de mnima
distancia, considerando el nodo r como nodo origen.
r r

2 4 2 4

x s x s

3 3 3 3 3
5

u v 1 w u v 1 w

a) Grafo inicial Figura 7. b) Arbol Generador de mnima distancia

paso i z N (T ) e A(T )
2 r
4 1 x (r, x)
5 1 x {r, x} {(r, x)}
4 2 s (r, s)
5 2 s {r, x, s} {(r, x)(r, s)}
4 3 u (x, u)
5 3 u {r, x, s, u} {(r, x)(r, s)(x, u)}
4 4 v (x, v)
5 4 v {r, x, s, u, v} {(r, x)(r, s)(x, u)(x, v)}
4 5 w (v, w)
5 5 v {r, x, s, u, v, w} {(r, x)(r, s)(x, u)(x, v)(v, w)}

El rbol resultante se muestra en la figura 7 b)

A. Caicedo B., G. Wagner de G., R. M. Mndez
 Algoritmo de Dijkstra (rbol de mnima distancia) 115

Ejemplo 7
Aplicar el algoritmo de Dijkstra al grafo de la figura 8 a) para obtener el rbol generador de mnima
distancia que se muestra en la figura 8 b). Usar el nodo a como nodo raz
a 5 3 c 4 a 5 3 c 4
b d b d

4 3 e 6 2 4 e 2

2 2

f 5 g f 5 g
h h
a) b)
Figura 8.

paso i z N (t) arco (e) A(T )

2 {a}
3-4 1 f (a, f )
5 {a, f } {(a, f )}
3-4 2 b (a, b)
5 {a, f, b} {(a, f )(a, b)}
3-4 3 c (b, c)
5 {a, f, b, c} {(a, f )(a, b)(b, c)}
3-4 4 g (f, g)
5 {a, f, b, c, g} {(a, f )(a, b)(b, c)(f, g)}
3-4 5 e (g, e)
5 {a, f, b, c, g, e} {(a, f )(a, b)(b, c)(f, g)(g, e)}
3-4 6 d (c, d)
5 {a, f, b, c, g, e, d} {(a, f )(a, b)(b, c)(f, g)(g, e)(c, d)}
3-4 7 h (d, h)
5 {a, f, b, c, g, e, d, h} {(a, f )(a, b)(b, c)(f, g)(g, e)(c, d)(d, h)}

A. Caicedo B., G. Wagner de G., R. M. Mndez

116 RBOLES NO DIRIGIDOS

Ejercicios Captulo 8

a. Aplicar el algoritmo de remover aristas para hallar un rbol generador en cada uno de los grafos de
la figura 9.
b b b b

b b b b b b

b b b b b

Figura 9.

b. Para el grafo de la figura 10 hallar grficamente los 16 rboles generadores distintos que posee.
b

b b

Figura 10.

c. Aplicar el algoritmo de Kruskal para hallar el rbol generador de valor mnimo en cada uno de los
grafos de la figura 11.
a 4 7 c a 8 11 c
b b

6 8
3 10

3 2 6 1 5 e 12
12
d 10 9
11

9 e 8 f f g
d

a 2 3
2
1 b
c 2 20 8 10 15 11
4
1 d
2 e 5 7 7
3 1 4 5 6
f 2
5
g 12 15
10 9
6
6 h
i 7
10
j Figura 11.

d. Aplicar el algoritmo de Prim para hallar el rbol generador de valor mnimo en cada uno de los
grafos de la figura 11.

e. Aplicar el algoritmo de Dijkstra para hallar un rbol generador de mnima distancia para cada uno
de los grafos de la figura 12. Considrese el nodo 1 como nodo raz.
A. Caicedo B., G. Wagner de G., R. M. Mndez
 Algoritmo de Dijkstra (rbol de mnima distancia) 117

5 3 4 4
1 2 3 4 1 2

9 7 11

4 5
3 5 6 2 4 4 5

2
2

5
6 7 8 3

Figura 12.

f. Dada la matriz de costos C, donde cij es el costo de tender una lnea de transmisin de energa
entre las ciudades xi y xj , encontrar la red de transmisin de costo mnimo.
x1 x2 x3 x4 x5 x6 x7 x8

x1 5 4 7 6 6

x2 7 8

x3 2 9 8 7
M=
x4 5 5

x5 4 9 5

x6 7 8
x7 8
x8

g. Una empresa constructora se encuentra realizando 3 obras que requieren ciertas cantidades de
cemento y se dispone de 2 fbricas que pueden satisfacer estas necesidades. Existe comunicacin
entre las dos fbricas y las 3 obras. El costo cij = cji de transportar una unidad (tonelada) de
cemento del lugar i al j se muestra sobre los arcos del grafo de la figura 13.
2
7
6
1 9
8 3 5

5
5 4

4
Figura 13.

Determinar la red de abastecimiento de costo mnimo.

h. Aplique el algoritmo de Dijkstra para hallar el rbol generador de mnima distancia del siguiente
grafo, tomando r como nodo raz.
a 5 4 r 6 c
b

7 2 9 3 4

p 4 q 3
t 5
Figura 14.

A. Caicedo B., G. Wagner de G., R. M. Mndez

118 RBOLES NO DIRIGIDOS

A. Caicedo B., G. Wagner de G., R. M. Mndez

 Bibliografa

[1] Garnier R. y John T. Discrete Mathematics. Adam Hilger. Editorial Philadelphia 1992.

[2] Grassmann W. y Jean- Paul T. Matemtica Discreta y Lgica. Editorial Prentice Hall. Espaa 1996.

[3] Brassard y Bratley P. Fundamentos de Algoritmia. Editorial Prentice Hall. Espaa 1997.

[4] Gorcbtov V. A. Fundamentos de Matemtica Discreta. Editorial Mir Mosc. URSS 1988.
[5] Skvarcius y Robinson. Discrete Mathematics whit Computer Sciencie Applications. Editorial Benjamin
Diummings. California 1986.

[6] Ross K. A. Y Charles R.B. Matemticas Discretas. Prentice Hall. Mxico 1988.

[7] Kolman B, Robert C. y Sharon R. Estructuras de Matemticas Discretas para la Computacin. Pren-
tice Hall. Mxico 1997.

[8] Wirth N. Algoritmos y Estructura de Datos. Prentice Hall. Mxico 1986.

[9] Knuth D. E. Clasificacin y Bsqueda. Editorial Revert. Espaa 1987.

[10] Johnsonbaugh J. Matemticas Discretas. Editorial Prentice Hall. Mxico 1999.

[11] Cormen T. H, Charles E. L. y Ronald L. R. Introduction to Algoritms. Editorial McGraw-Hill. New

York 1989.

[12] Toranzas F.A. Introduccin a la Teora de Grafos. OEA. Washington 1976.

[13] Aho A, John E. H. y Jeffrey D. U. The Desing and Analysis of Computer Algorithms. Editorial
Addison Wesley. USA 1974.

[14] Tenenbaum A. y Moshe J. A. Estructura de Datos en Pascal. Editorial Prentice Hall. Colombia 1983.

[15] Aho A, John E. H. y Jeffrey D. U. Estructura de Datos y Algoritmos. Editorial Addison Wesley.
USA 1988.

[16] Jauffred F. y otros. Mtodos de Optimizacin. Centro Regional de ayuda tcnica, agencia para el
desarrollo internacional. Mxico 1971.

[17] Kaufmann A. Mtodos y modelos de la investigacin de operaciones. Compaa Editorial Continental.

Mxico 1972.

[18] Phillips D.T. y Alberto G.D. Fundamentals of Network Analysis. Editorial Prentice Hall. USA
[Link] Me

[19] Minieka E. Optimization Algorithms for Networks and graphs. Editorial Marcel Dekker. New York

[20] Bazaraa M. y John J.J. Programacin lineal y flujo en redes. Editorial Limusa. Mxico 1981

119