introducción a la teoria de grafos

INTRODUCCIN A LA

TEORA DE GRAFOS

Primera Edicin

cDerechos reservadosReproducido y editado por Ediciones ElizcomPrimera edicin, diciembre del 2010200 ejemplaresISBN: [email protected]: 3113340748Armenia, Quindo

Contenido

PRLOGO iii

1. GRAFOS 11.1. Conceptos Bsicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2. Representacin de un Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.3. Matriz de Adyacencias de un Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.4. Lista de Adyacencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.5. Coeficiente de estabilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2. RELACIONES Y GRAFOS 172.1. Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.2. Matriz de una Relacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.3. Grfica de una Relacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.4. Propiedades de una Relacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.5. Operaciones entre Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.6. Producto Lgico de Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.7. Trayectorias y Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.8. Algoritmo de Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3. CONEXIDAD 393.1. Grafo Conexo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.2. Algoritmo para Conexidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.3. Algoritmo para Grafos no Dirigidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4. CIRCUITO EULERIANO 454.1. Circuito de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.1.1. Puentes de Knigsberg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454.2. Algoritmo de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5. CICLO HAMILTONIANO 535.1. Ciclo de Hamilton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535.2. Algoritmo Hamiciclo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545.3. Problema del Agente Viajero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.4. Algoritmo del Vecino ms Cercano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

6. LA TRAYECTORIA MS CORTA 616.1. Trayectoria Mnima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 626.2. Algoritmo del Camino Mnimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 626.3. Trayectoria del Valor Mnimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636.4. Algoritmo de DIJKSTRA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646.5. Algoritmo de Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666.6. Algoritmo Matricial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 736.7. La Trayectoria ptima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

i

ii CONTENIDO

7. RBOLES 837.1. Conceptos Bsicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 837.2. Subrboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867.3. rbol Binario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 877.4. rboles Etiquetados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 897.5. rbol Posicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907.6. Otras Formas de rboles Ordenados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 917.7. Representacin Matricial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 927.8. Representacin Secuencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 937.9. Representacin Enlazada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 947.10. Conversin de un rbol General a Binario . . . . . . . . . . . . . . . . . . . . . . . . . . . 957.11. Recorrido de un rbol Binario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 967.12. Notacin Polaca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 997.13. Bsqueda y Ordenamiento con rboles Binarios . . . . . . . . . . . . . . . . . . . . . . . . 101

8. RBOLES NO DIRIGIDOS 1078.1. rbol No Dirigido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1078.2. rbol Generado de Relaciones Conexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1088.3. rbol Generador de Mnimo Peso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1098.4. Algoritmo de Prim (Robert C. Prim, 1957) . . . . . . . . . . . . . . . . . . . . . . . . . . 1108.5. Algoritmo de Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1118.6. rbol Generador de Mnima Distancia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1138.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 daun lugar muy importante entre los conocimientos bsicos que deben adquirir las personas que se dedicanal estudio de las ciencias de la computacin, las matemticas aplicadas, la teora de la optimizacin, laplaneacin 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, conuna duracin de un semestre y en efecto se ha elaborado con base al programa curricular de MatemticasDiscretas II (Teora de Grafos) de la carrera de Ingeniera de Sistemas de la Universidad del Quindo. Seha experimentado durante varios semestres con los estudiantes de dicha disciplina y se ha complementadocon 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 lacreacin 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 omitidolas 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 unpoco el carcter abstracto de la teora. Al final de cada captulo se incluye un grupo de ejercicios queayudarn a reforzar los conocimientos adquiridos.

Los Autores, Diciembre de 2010.

iii

iv PRLOGO


Cap

tulo

1 GRAFOS

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

Los grafos son una estructura de datos no lineal, la cual sepuede usar para modelar diversas aplicaciones. Es una parteimportante de la Teora Combinatoria en Matemticas, loque le da un carcter bastante amplio y complejo. En estaunidad slo se har una introduccin a los conceptos bsicosde la teora de grafos y a los algoritmos que permiten suaplicacin a problemas prcticos.

b

b

b

b

b

b

b

b

b

bb

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 delos 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 parde 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 primerelemento es el nodo origen o fuente y el segundo es el nodo destino de ese arco, por lo tanto se puededecir que el arco va desde vi hasta vj y que vj es adyacente a vi. Un grafo orientado tambin se llama undigrafo. Si los arcos del grafo no indican una direccin, el grafo es no dirigido y en l cada arco se puederepresentar 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 y5 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 relacionesentre esos objetos. En el ejemplo anterior los nodos podran ser ciudades y los arcos las rutas areas entreesas ciudades. A los nodos y arcos de un grafo se pueden asignar nombres o valores (etiquetas), crendoseas 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 arcosincidentes a x y se denota grad(x).

Ejemplo 2

v1

grad(v1) = 2

v2

grad(v2) = 0

v3

grad(v3) = 4

A continuacin enunciaremos un teorema que relaciona el nmero de aristas de un grafo con el orden delos vrtices de este; adems se da uno de los conceptos ms importantes en el estudio de los grafos comoes 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


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 arcosque 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 4es una trayectoria de longitud 4.

3 4

5

1 2

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 mismonodo se llama un ciclo o circuito. Los ciclos de longitud 1 se llaman bucles o lazos porque salen de unnodo e inciden en el mismo nodo sin pasar por ningn otro.

Ejemplo 4

c

b

a

d e

e2

e1

e4

e5

e6

e3 e7

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 unatrayectoria simple. Este ciclo tambin se puede nombrar usando las etiquetas de los arcos: e2, e5, e3 opor 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 unasecuencia particular y donde es importante que no existan ciclos puesto que una tarea en un ciclo estaraprecedida de s misma, es decir, que se repetira.


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 2 y 3

5. Adicionar cielo raso 4

6. Instalar plomera 4

7. Instalar redes elctricas 4 y 5

8. Pegar piso 4 y 6

9. Instalar puertas 4 y 8

10. Pintar paredes interiores 4, 7, 8 y 9

11. Pulir piso 10

1 2 3

4

5

6

7

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 eldigrafo. Un etiquetamiento consistente es una forma de numerar los nodos en forma tal que cada nodotenga 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 etiquetamientoes consistente si (ni, nj) A i < j.

Un digrafo puede tener varios etiquetamientos consistentes diferentes.


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 eldigrafo G tiene un etiquetamiento consistente n1, n2, . . . , nn. Si existe un ciclo ni1, ni2, ..., nikse debe tener que i1 = ik y que i1 < i2 < . . . < ik, pero esto es una contradiccin, entonces Gno 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 construirel etiquetamiento consistente. El algoritmo parte del hecho de que un digrafo debe teneruna fuente; la metodologa del algoritmo consiste en etiquetar el conjunto de fuentes y luegoremoverlas de su consideracin, luego ser etiquetado el siguiente nivel de fuentes y assucesivamente. Eventualmente se presentar una de las siguientes situaciones: o todos los nodoshan 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 conjuntosde antecedentes sea vaco.

beginPara n N hacer

computar A(n)etiqueta = OMientras S 6= hacer

beginetiqueta = etiqueta +1n = nodo con A(n) = asignar la etiqueta a n y sacarlo de consideracin. Establecer a SPara cada nodo no etiquetado u N , hacer

A(u) = A(u) {n}end

Si todos los nodos no estn etiquetados entoncesreportar: "hay un ciclo en el digrafo".

end.


6 GRAFOS

Ejemplo 6

Aplicar el algoritmo del ordenamlento topolgico al siguiente digrafo para obtener un etiquetamientoconsistente.

1

2

6

4

5

3

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 nuevoconjunto 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 conjuntode 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 conjuntode 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 nuevoconjunto de antecedentes: A(3) = , A(5) = .

e) n = 3 Etiquetar 3 con E(5) y sacarlo de consideracin. S = {5}. Computar nuevo conjuntode 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.


Conceptos Bsicos 7

b

b

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 unidoa 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

Un r-grafo no dirigido contiene exactamenter(r 1)

2arcos.

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

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

2

Corolario

Para cada grafo Kr no dirigido se cumple que:

A N(N 1)

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.


8 GRAFOS

Ejercicio 2

1. Trazar dos grafos 3-regular con 6 nodos

2. Trazar los siguientes grafos:

a) 0-regularb) 1-regularc) 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

b

1.2 Representacin de un Grafo

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


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 valoresbooleanos, donde M(i, j) es verdad si y solo si existe un arco desde el nodo i al nodo j.

M(i, j) =

{1, si existe el arco (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 nodosestn relacionados (unidos por un arco)

Ejemplo 8

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

M(i, j) =

a b c d

a 0 1 1 0b 0 0 1 1c 1 0 0 1d 1 0 0 0

a

b

c

d

Figura 8.

Nota: Para un digrafo, la matriz de adyacencias depende del orden de los nodos. Para distintos rdenesen 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)

M(i, j) =

1 2 3 4 5

1 0 100 0 0 02 0 0 120 0 03 0 0 0 200 04 0 110 0 0 805 0 0 0 0 0

1

5

2

4

3

100

120

110

200

80

Figura 9.


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 unidadde mando, d es una unidad de memoria y e es un dispositivo de salida. Las relaciones entre unidadesy dispositivos se representan en el grafo de la figura 10.

a

b c d

e

Figura 10.

Si con un 1 se indica que hay un paso de informacin (relacin) desde el componente vi al componentevj , la matriz que representa al grafo es:

M(i, j) =

a b c d e

a 0 1 1 1 0b 0 0 1 1 1c 1 1 0 1 1d 0 1 1 0 1e 0 0 1 0 0

Ejemplo 11

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

a b

c

d e

f

a)

a b

c

d e

f

b)

4

16

11 6 19

15

4

8

3

5

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 ahasta f y escoger la menor. Una de tales trayectorias es : a b c d e f de longitud 22.


Lista de Adyacencias 11

De hecho este no es el mejor mtodo para resolver el problema. Se han desarrollado algoritmos muyeficientes que con la ayuda del computador pueden producir una solucin muy ptima en un tiempobastante corto. Uno de estos algoritmos es el propuesto por DIJKSTRA 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, detodos los nodos adyacentes a i.

En esta representacin el grafo incluye dos partes: un directorio y un conjunto de listas enlazadas. Hayuna 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

3 4 b

b

b

b

b

b

b

b b

3

2

4

2 3

4

3

2

1

Figura 12.

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

Ejemplo 13

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

1

2 3

4

5

6

b

b

b

b

b

b

b

b

b

b

b

b

b

b

3

5

2

2

6

3

6

5

4

3

2

1

Figura 13.

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


12 GRAFOS

b

b

b

b

b

b

b

b

b

b

b

b

b

b

3

2

1

2

4

2

3

36

5

4

3

2

1

5

3

b

b

b6

Figura 14.

Ejemplo 14

Otra forma de presentar la lista de adyacencias

A

P

B

Q

C Lista de adyacenciasA : B, PB : A, C, P, QC : BP : A, BQ : 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 quesirve 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 sino 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.


Coeficiente de estabilidad 13

Ejemplo 15 1 23

4

5

6

78

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 conjuntosinteriormente 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 sereciben 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 puederepresentar en el grafo de la figura 16.a.

a

b

c

d

e

p

q

r

s

t

a)

a

b

c

de

b)Figura 16.

Cul es el nmero mximo de seales que pueden emitirse simultneamente en forma tal que noexista posibilidad de confusin en la recepcin?

El problema equivale a buscar un conjunto interiormente estable y mximo, del grafo de la figura16a en donde dos nodos son adyacentes si representan dos seales que puedan confundirse. Se llegaas a construir un nuevo grafo, ver fig. 16 b donde:

a se une con b porque ellas pueden producir qb se une con c porque ellas pueden producir rc se une con d porque ellas pueden producir sd se une con e porque ellas pueden producir te 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.


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 ligadoal 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 esigual 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

def

g

h

El coeficiente de estabilidad externa es:

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

Figura 17.

Ejemplo 18

Redes de ComunicacinConsidrese un conjunto de subestaciones telefnicas con sus respectivas redes, como lo indica Elgrafo de la figura 18.

A

1

2

3

4

5

6

7

8

9

10

11

B

Figura 18.

Cul es el nmero mnimo de subestaciones que deben fallar para que las centrales A y B nopueden intercomunicarse?. El problema se reduce a encontrar un conjunto mnimo de articulacionesque 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 Testn ligados al menos a uno de los nodos de T por un arco que se inicia en ellos. Adems T es elmnimo de los subconjuntos exteriormente estables que se pueden obtener de G. El coeficiente deestabilidad externa para G es (G) = min{T} = 3. Se concluye que si fallan las subestaciones 4, 5 y9, las centrales A y B no pueden comunicarse.


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, dibujarel grafo correspondiente.

2. Dados los dos grafos de la figura 19, establecer el conjunto de nodos N y el conjunto de arcos A.

a

b

c

d

e

f

g

1

2 3 4

5 6

7

Figura 19.

3. En los grafos del ejercicio anterior determinar el orden y el nmero de arcos de cada uno. Usar lanotacin correspondiente.

4. En el grafo de la figura 20, determinar el grado de cada uno de sus nodos.

a

b

c

d

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 porcada arco una sola vez.

a b c

d e

f

a

b c

d

ef

Figura 21.

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

a b

c d

a b

c d

1 2

3

1 2

3

Figura 22.


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

c

d e

a

b c

d

e f

a

b

c

d e

f

g

h

i

a b

c d

e

12

10 20 12

14

1

2

3 4

55

4

8

6

20

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.

A

1

2

3

4

5

6

B

7

Figura 24.


Cap

tulo

2 RELACIONES Y GRAFOS

El concepto fundamental de las Matemticas Discretas es el de Relacin, por ello en esta seccinse hace una breve introduccin a las relaciones y se utilizarn para designar la correspondenciaentre 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 AB

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

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 unarelacin de A en A.

Si el conjunto de referencia para la relacin es el conjunto N de puntos (nodos) y la relacin binariaes N2, entonces la coleccin formada por N y se denomina un grafo G. Algunos autores llaman aN el portador del grafo y a la signatura del grafo.

Si AB 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 relacionadoscon 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 relacionadoscon algn elemento de A, por lo tanto Cod() B.

17


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 ] conelementos de la forma:

mij =

1, si (ai, bj) 0, si (ai, bj) /

Ejemplo 3

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

AB a > b

0

7

5

9

3

1

10

M =

1 3 10

0 0 0 07 1 1 05 1 1 09 1 1 0

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)}.

M =

a b

3 1 09 0 11 1 1


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 comopuntos del plano, unidos por arcos dirigidos si aiaj . La grfica resultante para esta relacin se llama ungrafo 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 dela figura 2.

a

c

d

m

Figura 2.

Ejemplo 6

Determinar la relacin representada por el grafo de la figura 3.

1

2

3

4 5

Figura 3.

Puesto que aiaj 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

ReflexivaUna relacin en un conjunto A es reflexiva si (a, a) , es decir, aa, a . es reflexiva si cadaelemento a A est relacionado consigo mismo.



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 relacinirreflexiva tiene al menos un cero en la diagonal principal.

Ejemplo 7

El siguiente grafo muestra una relacin reflexiva.

c

a

d

b

Figura 4.

SimtricaUna 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) AA |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

Si M =

1 1 01 0 1

0 1 0

, entonces MT =

1 1 01 0 1

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.


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 arcodesde 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 ai. 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 elementode 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.

TransitivaUna 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 longituddos desde a hasta c. es decir, que a2c implica que ac. 2 , siendo un subconjunto de AA.

Cualquier par de nodos conectados por un arco deben estar conectados por una trayectoria de longitud2.

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

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

1 2 3

1 1 1 12 0 0 13 0 0 1

(MR)2

= MR R es transitiva

1

2

3



Ejemplo 12

a b

c d e

1 2

3 4

5

Transitiva AntisimtricaTransitiva

IrreflexivaSimtrica

No transitiva

0 1 0 1

1 0 1 1

0 1 0 0

1 1 0 0

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 131 0 0

0 1 1

0 1 1

Relacin de equivalencia

1 0 1

0 1 0

1 0 1

Reflexiva, simtrica, no transitiva

2.5 Operaciones entre Relaciones

As como es posible manipular nmeros y frmulas usando las reglas del lgebra, tambin es posibledefinir operaciones que permitan manipular relaciones. Una vez definidas ciertas operaciones se puedeoperar 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: AB

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)}.


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 interseccinde 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 delas 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:b1a ab

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

Ejemplo 15

SeanA = {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 AB, donde,

AB = {(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 relacininversa est dada por 1 = {(x, 1), (y, 1), (y, 5), (x, 7), (y, 7), (x, 9)}.



Composicin de Relaciones

Se pueden crear nuevas relaciones a partir de otras existentes, una forma de hacer esto esmediante 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:

b

x

b

u

b

y

b

w

b

z

S

A B CFigura 6. S

De la figura anterior se deduce que la composicin de relaciones consiste en relacionar elementos de Acon 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)}.

b1

b2

b3

b4

b

1

b

2

b

3

b

4

b

2

b

3

A B C

S

Figura 7.


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 relacionespara 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 ysea S una relacin de B en C. se representa por una matriz M1mn; S se representa por la matrizM2np, 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 locual permite escribir:

M3 = M1 M2

Para determinar ms fcilmente como est definida esta operacin, se puede considerar el esquema de lasdos 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 siy solo si k {1, ..., n} tal que aibj y bkScj .

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.

a1

a2

...

ai

...

am

b1

b2

...

bk

...

bn

c1

c2

...

cj

...

cp

S

Figura 8.

1

+/ 0 1

0 0 1

1 1 1

/ 0 1

0 0 0

1 0 1



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 unarelacin de B en C. S = {(a, a), (a, c), (a, d), (b, a), (c, b), (c, d)}, por lo tanto:

M =

(1 1 00 1 0

), MS =

1 0 1 11 0 0 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

MS = M MS =

(1 1 00 1 0

)

1 0 1 11 0 0 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)

)

=

(1 1 0 0 0 0 1 0 0 1 0 00 1 0 0 0 0 0 0 0 0 0 0

)=

(1 0 1 11 0 0 0

)Ntese que esta ltima matriz es equivalente a la matriz de la relacin representada en el esquema anterior.

ba

bb

b

a

b

b

b

c

b a

b b

b c

b d

SA B C

ba

bb

b a

b b

b c

b d

SA C

Figura 9. S

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

Teorema 4

Sean y S dos relaciones en A, entonces se cumple que:1. MS = M MS2. MS = M MS3. MS = M MS4. (M)

n = M... = M M . . . (n veces)


Producto Lgico de Matrices 27

Ejemplo 18

Sean M =

1 0 11 0 01 1 1

y MS =

0 1 11 1 00 1 0

, se tiene entonces,

MS =

1 1 11 1 01 1 1

, MS =

0 0 11 0 00 1 0

M MS =

1 1 11 1 01 1 1

, M MS =

0 0 11 0 00 1 0

Ejemplo 19

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

MS = M MS = M MS =

2 1 00 0 10 0 0

Ejemplo 20

3

2

1

A

c

b

a

B

z

y

x

C

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

M =

a b c

1 0 1 0

2 1 0 1

3 0 0 0

MS =

x y z

a 0 1 0

b 1 0 0

c 0 1 1

MS =

x y z

1 1 0 0

2 0 1 1

3 0 0 0

M MS =

x y z

1 1 0 0

2 0 2 1

3 0 0 0

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



2.7 Trayectorias y Relaciones

La idea de una trayectoria en un digrafo tiene muchas interpretaciones, dependiendo de la aplicacin que estsiendo modelada. Por ejemplo, si el digrafo es un modelo de una red de comunicacin, las trayectorias en eldigrafo mostrarn las posibles rutas para mensajes entre diferentes computadores. Hay tres problemas que surgenal 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 finitapi = a, x1, x2,. . .xn1, b que se inicia en a y termina en b, y tal que ax1, x1x2,. . . , xn1b.

Una solucin al primer problema de determinar cules nodos estn conectados por trayectorias a otros nodospuede ser establecida en dos formas: la primera analizando visualmente el grafo y determinando la trayectoriay la segunda en trminos de la matriz de la relacin que representa los arcos del digrafo. El primer mtodo noes prctico cuando el grafo tiene muchos nodos y arcos, razn por la cual en esta seccin, se har el estudio delsegundo 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 xny y significa que existe una trayectoria de longitud n de x a y en , o xest 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 mismada 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 xy indica que existe alguna trayectoria en de xa 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.a2b significa que a y b tienen un conocido en comn.anb significa que a conoce a x1, que conoce a x2,. . . ,que conoce a xn1, que conoce a b.


Trayectorias y Relaciones 29

Ejemplo 22

El siguiente grafo representa un conjunto de vuelos con escala intermedia.

3

1

4

2

6

5

Figura 10.

Luego:

125 porque 12 y 25

124 porque 12 y 24

225 porque 24 y 45

226 porque 25 y 56

325 porque 34 y 45

426 porque 45 y 56 3

1

4

2

6

5

Grafo de la relacin 2

Ejemplo 23

Para el grafo de la figura 11 determinar .

1

3

2

4

Figura 11.

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

M =

1 2 3 4

1 1 1 1 12 1 1 1 13 0 0 0 14 0 0 0 0

Ejemplo 24

1 2

3 4

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

M =

1 2 3 4

1 0 1 1 12 0 0 0 03 0 1 1 14 0 0 0 0



Teorema 5

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

knj , 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 n veces

Definicin 2.10

xy si y solo si xy o x2y o x3y o . . .

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

M = M M2 M3 . . . Mn

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 sedefine como xy si y solo si x = y o xy.

En otras palabras esto indica que un nodo y es alcanzable desde x si y es x o existe una trayectoria de cualquierlongitud 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 M2 . . . Mn


Trayectorias y Relaciones 31

Ejemplo 25

Para la relacin representada por el siguiente grafo, determinar cules parejas de nodos estn unidas portrayectorias de longitud 2 arcos.

a

b

c

d

e

Figura 12.Solucin

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:

M =

1 1 0 0 00 0 1 1 00 0 0 1 10 0 0 1 00 0 0 0 0

M2 = M M =

1 1 0 0 00 0 1 1 00 0 0 1 10 0 0 1 00 0 0 0 0

1 1 0 0 00 0 1 1 00 0 0 1 10 0 0 1 00 0 0 0 0

=

1 1 1 1 00 0 0 1 10 0 0 1 00 0 0 1 00 0 0 0 0

=

matriz decaminos delongitud 2

Ejemplo 26

Encontrar la matriz de alcance (conectividad) para el digrafo de la figura 13.

1

3

2

4

Figura 13.

SolucinLa matriz de la relacin en el digrafo es:

M =

0 1 0 00 0 1 01 0 0 01 0 0 0

a partir de ella se pueden calcular otros productos:



M2 = (M)2= M M =

0 0 1 01 0 0 00 0 1 00 1 0 0

, M3 = (M)3 = M2 M =

1 0 0 00 1 0 00 0 1 00 0 1 0

M4 = (M)4= M3 M =

0 1 0 00 0 1 01 0 0 01 0 0 0

La matriz de relacin de conectividad es

M = M M2 M3 M4

=

0 1 0 00 0 1 01 0 0 01 0 0 0

0 0 1 01 0 0 00 1 0 00 1 0 0

1 0 0 00 1 0 00 0 1 00 0 1 0

0 1 0 00 0 1 01 0 0 01 0 0 0

=

1 1 1 01 1 1 01 1 1 01 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 Mn

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

v5

v1

v4

v2

v3 M =

0 0 0 1 1

0 0 1 0 0

0 1 0 0 0

0 1 1 0 1

1 1 0 0 0

Figura 14.

M2 = M M =

0 1 1 0 10 1 0 0 00 0 1 0 01 2 1 0 00 0 1 1 0

=

Los valores diferentes de 0, indican cuntas trayectorias delongitud 2 existen entre cada par de nodos

M3 = M2 M =

1 2 1 0 00 0 1 0 00 1 0 0 00 1 2 1 00 2 1 0 1

=



Algoritmo de Warshall 33

M4 = M3 M =

0 1 2 1 00 1 0 0 00 0 1 0 00 3 2 0 11 2 2 0 0

=


M5 = M4 M =

0 3 2 0 10 0 1 0 00 1 0 0 01 3 3 0 00 2 2 1 0

=


T 5 = M +M2 +M3 +M4 +M5 =

1 7 6 2 20 2 3 0 00 3 2 0 02 10 9 1 22 7 6 2 1

=

el elemento de la i-sima fila y j-simacolumna indica el nmero de trayecto-rias de longitud 5 o menor entre vi yvj

Si un elemento de esta matriz no es nulo, queda claro que vj es alcanzable o accesable desde vi mediante unatrayectoria 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 matrizde adyacencias, o sea usando

M = M1 M2 Mn

Stephen Warshall propuso en 1962 el siguiente procedimiento para hallar la matriz de alcanzabilidad a partir dela matriz de adyacencias de G.

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

Procedimiento

W = Mpara k = 1 hasta n

para i = 1 hasta npara 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 vusando 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 usandoalgn subconjunto de vrtices v1, . . . , vk+1 como vrtices intermedios.



De esta definicin se deriva que W (n) = M = matriz de alcanzabilidad o accesibilidad. Si consideramos lasrelaciones 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

3 4

La matriz de adyacencias es

M =

1 2 3 4

1 0 1 0 02 0 0 1 03 1 0 0 04 1 0 1 0

Figura 15.

En este momento W = M y W ser modificado mediante el proceso iterativo que usa la frmula: nuevoW (i, j) = W (i, j) [W (i, k) W (k, j)]

Proceso iterativo

Primera iteracinPara 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



Se ha obtenido la siguiente matriz

W (1) =

1 2 3 4

1 0 1 0 02 0 0 1 03 1 1 0 04 1 1 1 0

Los unos de esta matriz indican cules parejas de nodos estncomunicados directamente por un arco o usando al nodo v1como nodo intermedio.

Segunda Iteracin

Para hallar W (2) partimos con todas las trayectorias encontradas en W (1) y establecemos las trayectoriasque 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:

W (2) =

1 2 3 4

1 0 1 1 02 0 0 1 03 1 1 1 04 1 1 1 0

Los unos de esta matriz indican cuales parejas de nodos estncomunicados directamente por un arco o por una trayectoriaque usa los nodos v1 y v2 como nodos intermedios

Tercera IteracinPara k = 3 y usando los valores de W (2), ejecutamos el mismo proceso iterativo y se obtiene:

W (3) =

1 2 3 4

1 1 1 1 02 1 1 1 03 1 1 1 04 1 1 1 0

Los unos de esta matriz indican cuales parejas de nodos estnconectados directamente por un arco o por una trayectoriaque usa los nodos v1, v2 y v3 como nodos intermedios.

Cuarta IteracinPara k = 4 y usando los valores de W (3) y ejecutando el mismo proceso iterativo se obtiene:

W (4) =

1 2 3 4

1 1 1 1 02 1 1 1 03 1 1 1 04 1 1 1 0

= Matriz de alcanzabilidad

Obsrvese que W (3) = W (4) porque el nodo 4 es un nodo fuente, l no recibe ningn arco, entonces no sepueden establecer nuevas trayectorias. El proceso se detiene cuando:

1. W k1 = W k

2. W k = matriz de unos

3. W k = Wn

Trayectorias de acceso o alcanzabilidad

W (4)(1, 1) = 1 Trayectoria de acceso: 1 2 3 1W (4)(1, 2) = 1 Trayectoria de acceso: 1 2W (4)(1, 3) = 1 Trayectoria de acceso: 1 2 3W (4)(2, 1) = 1 Trayectoria de acceso: 2 3 1W (4)(2, 2) = 1 Trayectoria de acceso: 2 3 1 2W (4)(2, 3) = 1 Trayectoria de acceso: 2 3W (4)(3, 1) = 1 Trayectoria de acceso: 3 1W (4)(3, 2) = 1 Trayectoria de acceso: 3 1 2W (4)(3, 3) = 1 Trayectoria de acceso: 3 1 2 3W (4)(4, 1) = 1 Trayectoria de acceso: 4 1W (4)(4, 2) = 1 Trayectoria de acceso: 4 3 1 2W (4)(4, 3) = 1 Trayectoria de acceso: 4 3




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

x2

16+y2

81= 1

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 queconforman 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 ,

M =

1 0 1 1

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

M =

x y z

a 1 0 1b 1 1 1c 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 elconjunto 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 elconjunto de parejas de y trazar el grafo.

10. Sea A = {1, 2, 3, 4}. Encontrar la relacin en A determinada para la siguiente matriz:

M =

1 1 0 10 1 1 00 0 1 11 0 0 0

11. Dado el grafo de la figura 16, determinar:

a) M.

b) Conjunto de parejas.

c) Dominio y codominio de .



5

4

3

1

2

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, asimtricao transitiva.

1

2

5

4

3

1

3

2

4

5

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 relacinde equivalencia.

M =

1 0 1

0 1 1

0 1 1



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

3

1

4

5

2

6

7

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) S1

20. Aplicar el algoritmo de Warshall para hallar la matriz de alcanzabilidad del siguiente grafo

1

4

2

5

3

Figura 19.


Cap

tulo

3 CONEXIDAD

El concepto de conexidad en la teora de grafos es uno de los conceptos ms importantesy de mayor aplicabilidad. Para desarrollar este concepto se hace uso de otros que ya fuerontratados 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 requiereque el grafo o red inicial sea conexa, es conveniente establecer un algoritmo que determine siun 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 hastay 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 mspiezas. 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 trayectoriadesde 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 desdeun nodo al otro.

Sea M una matriz de adyacencias del grafo G donde cada elemento mij de M es de la forma

mij =

{1, si existe el arco (i, j)

0, si no existe el arco (i.j)

39

40 CONEXIDAD

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

En al menos una de las matrices M,M2, . . . ,Mn1 habr una entrada no cero en la (i, j) esimaposicin si existe una trayectoria entre i y j.

Al formar la matriz C = M + M2 + M3 + . . . + Mn1, sta tendr una entrada cero para cualquiernodo 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 = MHacer 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 + 1Si 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

2

4

5 6

3

Figura 1.


Algoritmo para Conexidad 41

Solucin

Paso 0. Matriz de adyacencias. n = 6.

M =

0 1 0 1 0 01 0 1 0 0 00 1 0 0 1 11 0 0 0 1 00 0 1 1 0 10 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 .

C =

0 1 0 1 0 01 0 1 0 0 00 1 0 0 1 11 0 0 0 1 00 0 1 1 0 10 0 1 0 1 0

+

2 0 1 0 1 00 2 0 1 1 11 0 3 1 1 10 1 1 2 0 11 1 1 0 3 10 1 1 1 1 2

=

2 1 1 1 1 01 2 1 1 1 11 1 3 1 2 21 1 1 2 1 11 1 2 1 3 20 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 +M3.

C =

2 1 1 1 1 01 2 1 1 1 11 1 3 1 2 21 1 1 2 1 11 1 2 1 3 20 1 2 1 1 2

+

0 3 1 3 1 23 0 4 1 2 11 4 2 2 5 43 1 2 0 4 11 2 5 4 2 42 1 4 1 4 2

=

2 4 2 4 2 24 2 5 2 3 22 5 5 3 7 64 2 3 2 5 22 3 7 5 5 62 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 conjuntode arcos) es simtrica, entonces, es simtrica y transitiva. Asumiendo que cada vrtice est conectadoa si mismo por una trayectoria de longitud cero, entonces es reflexiva. Luego es una relacin deequivalencia.

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 construirsubgrafos de G, los cuales se llaman componentes de conectividad o simplemente componentes conexasdel grafo.


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 nodoni 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 formaCni .

Ejemplo 2

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

1

2

3

4

6

5

Figura 2.

Definicin 3.6

El nmero de componentes de un grafo G es llamado el nmero de conectividad de G y es notadopor 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 elsiguiente:

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 msvecinos. Esto significa que se ha encontrado una componente completa. Luego se salta a la siguientecomponente y se ejecuta el mismo procedimiento. Como el grafo es finito, entonces eventualmente todoslos nodos son alcanzados.


Algoritmo para Grafos no Dirigidos 43

ALGORITMOInicio

N NC 0mientras N 6= haga

inicioEscoger n N

Encontrar todos los nodos conectados a n y guardarlos en WRemover todos estos nodos de N , es decir, hacer N = N WC = C + 1

TerminarTerminar

Ejemplo 3

Aplicar el algoritmo anterior al grafo de la figura 3.

1

4

2

3

5

8

6

9

7

10b

Figura 3.

SOLUCIN

N = {1, 2, . . . , 10} C = 0Primera iteracin:N 6= continuarEscoger n = 5 arbitrariamenteW = {5, 6, 7, 8, 9} nodos conectados a n (componente)N = N W = {1, 2, 3, 4, 10}C = 0 + 1 = 1

Segunda iteracinN 6= continuarEscoger n = 1 arbitrariamenteW = {1, 2, 3, 4} nodos conectados a n (componente)N = N W = {10}C = 1 + 1 = 2

Tercera iteracinN 6= continuarEscoger n = 10 arbitrariamenteW = {10} nodos conectados a n (componente)N = N W = C = 2 + 1 = 3

Cuarta iteracinN = PararNo se pudieron visitar todos los nodos, entonces el grafo no es conexo.


44 CONEXIDAD


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

0 0 1 0 00 0 0 1 01 0 0 0 10 1 0 0 10 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.

a

b

d

c

e

Figura 5.

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

d

a

c

b

e

fFigura 6.


Cap

tulo

4 CIRCUITO EULERIANO

Cuando se posee una red no dirigida conexa se puede disear un circuito que recorra todossus nodos, partiendo de un nodo especfico y regresando a l, pero sin pasar ms de una vezpor 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 porcada 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 esllamado El Problema del Cartero o Problema Chino del Cartero el cual apareci formulado por primeravez por M. K. Kwan en el Chinese Mathematical Journal. Sus orgenes se remontan a 1736 cuandoLeonard 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 pertenecientea Rusia con el nombre de Kaliningrado es atravesada por el ro Pregel o Pregolia. La parte central de laciudad 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 pordos puentes, uno hacia cada orilla.

45


Figura 1. Puentes de Knigsberg

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

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

C

B

A

D

Figura 2.

Bajo esta simplificacin el problema se resuma en coger un lpiz y a partir de un nodo del grafo y sinlevantarlo, tratar de recorrer todo el grafo sin repetir arco. Esto equivaldra a atravesar fsicamente lossiete puentes del problema, donde el concepto recorrer el grafo es pasar todos los arcos solamente unavez 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 siguientesteoremas:

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.


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 nodoses par.

Corolario

Un grafo conexo contiene una trayectoria euleriana, pero no un ciclo euleriano, si y solo sexactamente dos nodos tienen grado impar. La trayectoria debe comenzar en un nodo impar yterminar 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 impary el grafo podr cruzarse pero no se lograr regresar al punto de partida (figura 3a). Si se agregaun nuevo arcoAC, solamente los nodos B y D sern impares y se podr cruzar el grafo pero no sepodr 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 serrecorrido y regresar al nodo de partida (figura 3c).

C

B

A

D

C

B

A

D

C

B

A

D

a) b) c)Figura 3.

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

De acuerdo a estos teoremas, si el grafo es par entonces la solucin ptima al problema del carteroes 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 circuitoy 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 vanusando.

3. Partiendo de un nodo origen cualquiera se selecciona un arco no usado que sea incidente a ese nodoorigen. 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 anteriorusado. As el circuito se construye arco por arco, hasta que eventualmente se regresa al nodo origen.



El siguiente algoritmo se basa en los conceptos anteriores y permite hallar un circuito de Euler de longitudmnima 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 losnodos 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 = conjuntode arcos que van a formar el ciclo parcial. Hacer V = conjunto de arcos que formanciclos parciales empezando en s.

b. Escoger cualquier arco entre t y q que est sin usar, marcarlo como usado y adicionarloa 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 quedavaco. Encontrar un nodo t que est visitado en V pero que tenga arcos incidentes nousados. 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.

1

2

3 4

5

4

5

2

3

7

3

6

Figura 4.

paso 0. La matriz de distancias es

D =

0 4 2 4 0 5 3 62 5 0 3 7 3 3 0 6 7 0


Algoritmo de Euler 49

El grado de los nodos es:nodo 1 grado 2nodo 2 grado 4nodo 3 grado 4nodo 4 grado 2nodo 5 grado 2No 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 siguienteprocedimiento:



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 3 4

5678

9

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 nodoinicial y N = {1, 2, 3, 4, 5, 6, 7, 8, 9}

Paso X C D |A(G)| > 0 A(G)1 9 {9}2 si3 94 {9, 6, 7, 9}5 11 3 = 86 {9, 6, 7, 9}2 si3 64 {6, 3, 4, 5, 6}5 8 4 = 46 {9, 6, 3, 4, 5, 6, 7, 9}2 si3 74 {7, 2, 1, 8, 7}5 4 4 = 06 {9, 6, 3, 4, 5, 6, 7, 2, 1, 8, 7, 9}2 no parar


Algoritmo de Euler 51


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

b

cd e

f gFigura 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 eFigura 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 porsemana para informar sobre el estado de dichas vas. El circuito vial es el de la figura 9

1

2

3 4

5

67

10 12

14

18

1110

9

20

18

25

Figura 9.



El ingeniero tiene su sede en la ciudad 1 y debe planear su recorrido en forma tal que recorra todaslas 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 debellegar a todas las otras estaciones; cada estacin la replica a la estacin ms cercana, hasta que laseal regresa a R1. Determinar la trayectoria seguida por la seal de prueba si la red de repetidorases la mostrada en la figura 10.

R1

R2

R3R4

R5 R6

20

30

26

3518

30

3032

24

35

72

80

Figura 10.


Cap

tulo

5 CICLO HAMILTONIANO

Cuando se tiene un grafo conexo no dirigido G = (N,A) puede ocurrir que se desea hacerun recorrido por el grafo, que pase por todos lo nodos, sin repetir nodo y regresar al nodo departida. 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 RowanHamilton (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 nodoso el costo de recorrer dichas distancias, es de inters hallar un circuito que recorra todos losnodos una sola vez, y que tenga distancia mnima o costo mnimo. Este problema ha sidoformulado 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 recorratodos los nodos, es llamado hamiltoniana. Un grafo es llamado hamiltoniano si contiene un ciclohamiltoniano.

No hay una regla simple para determinar la existencia de un circuito hamiltoniano como si la hay paracircuitos eulerianos. Es cierto que un grafo con circuito hamiltoniano es conexo, pero no cada grafo conexotendr un circuito hamiltoniano.

Si un grafo representa un conjunto de ciudades a ser visitadas, luego una trayectoria que visite cadaciudad exactamente una sola vez es un circuito hamiltoniano. Asumiendo que cada ciudad est conectadapor 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 eshamiltoniano.

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

5

2

4

3

Figura 1.

Obsrvese que para cualquier par de nodos que se escoja, se cumple que la suma de los grados esn 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)| = Nbeginpaso 4. Escoger z {N(G)N(P )}. P trayectoria maximal que contiene a N(P ) y a zpaso 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

x v t w y

u

Figura 2.SolucinEl 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} no4 u {u, t, w, y, v, x}5 {u,w, y, v, x, t, u} si6 {u,w, y, v, x, t, u} parar


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 carreterasque unen cada par de ciudades. El valor asociado a cada arco d(x, y) 0 es la distancia entre ellas. Unagente viajero desea escoger una ruta que le permita visitar cada ciudad una sola vez y retornar a laciudad de origen cubriendo el mnimo de distancia.

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

Un circuito hamiltoniano con la menor longitud total es llamado un ciclo hamiltoniano ptimo y esuna 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.

a

b

c

2

215

4

4Figura 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 econmicosera 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 solucinptima 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 agenteviajero si la solucin existe.

Para hallar una solucin aproximada al problema del agente viajero se dispone de diversos algoritmoscomo los de Bellmore-Nemhauser (1968), Held-Karp (1970), Garfinkel-Nemhauser (1972), Little-Murty(1973) y o

introducción a la teoria de grafos

Documents