Teor´ de Grafos ıa
Por: Lic. Wilber Ramos Lov´n o 23 de agosto de 2006

II

Pr´logo o
Este libro va dirigido a aquellos que est´n interesados en conocer una parte de la e matem´tica finita y, m´s concretamente, al alumnado de cualquier ingenier´ inform´tica. a a ıa a No hemos tratado de ser exhaustivos en los temas tratados, si bien, el planteamiento del contenido seleccionado en este libro se ha intentado realizar de forma rigurosa a la vez que sencilla para el lector. Las actuales recomendaciones curriculares en inform´tica se˜alan a n que, la presencia de parte de las matem´ticas necesarias para el ingeniero inform´tico a a ha sufrido un proceso de redireccionamiento hacia las estructuras discretas. As´ aunque ı, no existe total coincidencia en el papel que debe jugar la matem´tica tradicional, todos a coinciden en resaltar la importancia que en ciencia de la computaci´n tienen las estructuras o discretas. En ese sentido podr´ ıamos decir que las estructuras discretas son las matem´ticas a de la inform´tica, aunque no las unicas. De hecho, la matem´tica discreta, considerada a ´ a n como disciplina independiente, ha nacido hace muy pocos a˜os como consecuencia de la aparici´n del computador que, al fin y al cabo, es una m´quina finita. Son muchos o a los t´picos que pueden clasificarse dentro de la materia de matem´tica discreta. Podemos o a considerar, por ejemplo, los t´picos relacionados con la teor´ de conjuntos, la l´gica b´sica, o ıa o a e o e las t´cnicas de demostraci´n, los fundamentos de conteo, la aritm´tica entera y modular, los grafos, los ´rboles o la probabilidad discreta. De entre ellos, existen ciertos t´picos que a o por sus caracter´ ısticas pueden, tambi´n, englobarse dentro de otras disciplinas o materias. e Por ejemplo, los conceptos relacionados con la teor´ de conjuntos pueden formar parte ıa del ´lgebra, la l´gica b´sica y las t´cnicas de demostraci´n formar´ parte de la l´gica a o a e o ıan o considerada como materia, y lo mismo ocurre con la probabilidad discreta que ya por s´ misma puede considerarse una disciplina. Todo ello nos ha llevado a considerar en ı este libro conceptos relacionados con los grafos, la aritm´tica entera y modular, y los e fundamentos de conteo.

III

Cr´ditos e Teor´ de Grafos ıa Ramos Lov´n, Wilber o

La edici´n de este libro fue dividida en: o Dise˜ o y presentaci´n a cargo de: n o Edici´n de texto a cargo de: o Producci´n de gr´ficos a cargo de: o a Revisi´n t´cnica a cargo de: o e Curitunay Casani, Wiliams Quintanilla Yucra, Wiliham Bust´ Belizario, Paul ıos Samill´n, Pablo a

COPYRIGHT c 2006. TODOS LOS DERECHOS RESERVADOS. Queda proo hibida la reproducci´n total o parcial del texto d la presente obra bajo cualesquiera formas, electr´nica o mec´nica, incluyebdo fotocopiado, almacenamiento en alg´n sistema de reo a u cuperaci´n de informaci´n, o grabado sin el consentimiento previo y por escrito de los o o editores.

IV

´ Indice general
. Pr´logo o . Cr´ditos e 1. Conceptos fundamentales 1.1. Definiciones b´sicas . . . . . . . . . . . a 1.1.1. Definici´n . . . . . . . . . . . . o 1.1.2. Definici´n . . . . . . . . . . . . o 1.1.3. Observaci´n . . . . . . . . . . . o 1.1.4. Definici´n . . . . . . . . . . . . o o 1.1.5. Observaci´n . . . . . . . . . . . o 1.1.6. Definici´n . . . . . . . . . . . . 1.2. Ejemplos de modelado de grafos . . . 1.3. Representacion num´rica de los grafos e 1.3.1. Matriz de adyacencia . . . . . . 1.3.2. Lista de adyacencia . . . . . . 1.3.3. Matriz de Incidencia . . . . . . 1.3.4. Matrices Figurativas . . . . . . 1.4. Relaciones de Adyacencia . . . . . . . 1.4.1. Definici´n . . . . . . . . . . . . o 1.4.2. Definici´n . . . . . . . . . . . . o 1.4.3. Definici´n . . . . . . . . . . . . o 1.4.4. Definici´n . . . . . . . . . . . . o 1.4.5. Definici´n . . . . . . . . . . . . o 1.5. Vecindades de conexiones . . . . . . . 1.5.1. Definici´n . . . . . . . . . . . . o o 1.5.2. Definici´n . . . . . . . . . . . . 1.5.3. Definici´n . . . . . . . . . . . . o 1.5.4. Definici´n . . . . . . . . . . . . o 1.5.5. Definici´n . . . . . . . . . . . . o 1.5.6. Definici´n . . . . . . . . . . . . o V III IV 1 1 1 1 2 4 4 5 5 11 11 13 13 14 15 15 15 16 16 18 18 18 18 19 19 19 21

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

´ INDICE GENERAL 1.5.7. Definici´n . . . . . . . . . . . . . . o 1.5.8. Definici´n: . . . . . . . . . . . . . . o Trayectoria de un grafo . . . . . . . . . . 1.6.1. Definici´n . . . . . . . . . . . . . . o 1.6.2. Definici´n . . . . . . . . . . . . . . o Grafos conexos - Componentes f-conexas . 1.7.1. Definici´n . . . . . . . . . . . . . . o 1.7.2. Definici´n . . . . . . . . . . . . . . o 1.7.3. Definici´n . . . . . . . . . . . . . . o 1.7.4. Definici´n . . . . . . . . . . . . . . o 1.7.5. Observaci´n: . . . . . . . . . . . . o Algunos resultaos . . . . . . . . . . . . . . 1.8.1. Proposici´n . . . . . . . . . . . . . o 1.8.2. Colorario . . . . . . . . . . . . . . 1.8.3. Proposici´n . . . . . . . . . . . . . o 1.8.4. Teorema . . . . . . . . . . . . . . . 1.8.5. Corolario . . . . . . . . . . . . . . 1.8.6. Corolario . . . . . . . . . . . . . . 1.8.7. Algoritmo de Fleury . . . . . . . . 1.8.8. Teorema . . . . . . . . . . . . . . . 1.8.9. Colorario . . . . . . . . . . . . . . 1.8.10. Teorema . . . . . . . . . . . . . . . 1.8.11. Corolario . . . . . . . . . . . . . . 1.8.12. Corolario . . . . . . . . . . . . . . Un modelo de administraci´n de proyectos o 1.9.1. Definici´n . . . . . . . . . . . . . . o 1.9.2. Definici´n . . . . . . . . . . . . . . o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 25 25 25 27 27 28 28 29 29 30 32 32 32 32 33 34 35 37 38 38 38 38 38 39 40 42 43

1.6.

1.7.

1.8.

1.9.

.

Lista de Ejercicios

VI

Cap´ ıtulo 1

Conceptos fundamentales
1.1.
1.1.1.

Definiciones b´sicas a
Definici´n o

Una familia enumerable es una colecci´n enumerable de objetos iguales o diferentes. o * El mayor n´mero p de elementos iguales en una familia enumerable le llamamos u grado de multiplicidad. * Una familia enumerable con p = 1 se llama conjunto. * En lo que sigue, consideraremos s´lo familias finitas. o * El conjunto de partes de X sera denotado P(X). * Pk (X) = {u ∈ P (X) / |u| = k}. * La potencia cartesiana X k es el conjunto de toda la k -uplas ordenadas (x1 , x2 , . . . , xn ) donde xi ∈ X , 1 ≤ i ≤ k , 1 ≤ k ≤ |X|

1.1.2.

Definici´n o

Un grupo es una estructura G = (N, A) donde N es un conjunto finito y A es una familia cuyos elementos (no vacios) son definidos en funci´n de los elementos v de N , en o dos formas posibles: 1.1.2.1 Si la familia A de grado de multiplicidad p fuera tal que sus elementos a ∈ P (N ), G ser´ llamado un p-hipergrafo no orientado. a 1.1.2.2 Si la familia A de grado de multiplicidad p es constituida por pares de elementos no a vacios de P (N ) de la forma ai = (a− , a+ ), G ser´ llamado un p-hipergrafo orientado. i i * Los elementos de N son llamados nodos (v´rtices) y el valor n = |N | es el orden de e la estructura. 1

2

Teor´ de Grafos ıa * La familia A puede ser entendida como una relaci´n o conjunto de relaciones de o adyacencia cuyos elementos son llamados en general conexiones; en particular, en las estructuras no orientadas las a ∈ A son conocidas como aristas y en las orientadas como arcos. * Dos nodos que participan de una conexion son llamados adyacentes. * Al valor m = |A| lo llamaremos el tama˜o del grafo. n * Si m = 0, el grafo es llamado trivial. * La representaci´n din´mica de un grafo , tambi´n llamado grafo (confusi´n semio a e o intensional) es obtenido asociado a cada nodo un punto o una peque˜a area delimn itada por una frontera y a cada ligason un dise˜o capaz de representar la forma de n asociaci´n de los nodos que involucra la conexi´n. o o * Utilizaremos el termino grafo para designar estructuras que posean conexiones con un m´ximo de dos nodos involucrados y a menos que se indique lo contrario, con a grado de multiplicidad igual a 1.

Ejemplo 1: Los siguientes graficos representan aristas o arcos.

1.1.3.

Observaci´n o

a) Para G = (N, A) un p-hipergrafo no orientado, en particular, s´ ı: • Se verifica que todos los elementos de A pertenecen a P1 (N ) ∪ P2 (N ); G es llamado un multigrafo o p-grafo no orientado. • A fuese un subconjunto de P (N ), G sera 1-hipergrafo no orientado o hipergrafo simple. b) Para G = (N, A) un 1-hipergrafo orientado, en particular, s´ : ı • Se tuviera |a− | = |a+ | = 1 para todo i , G se denominara 1-grafo orientado o i i digrafo.

Teor´ de Grafos ıa

3

c) Una conexi´n que tiene apenas un nodo es llamado bucle o lazo. En las estructuras o no orientadas un lazo es un elemento de P1 (N ) y en las orientadas, una k-upla de elementos iguales, en grafos orientados un par ordenado de elementos iguales. d) Asociado a todo grafo orientado G = (N, A) existe un grafo G = (N, A ) en el cual todo arco a = (y, x) tiene en A un arco correspondiente a = (x, y): Al grafo G se le denomina el dual direccional de G. Ejemplos 2: A continuaci´n se presentan diversos tipos de estructuras de grafo: o
1 1 2 b 4 3 4 3-hipergrafo no orientado 1-hipergrafo orientado 3 c Multigrafo d a

2

1 2 6

3 4 Hipergrafo simple

5

Grafo simple

Grafo orientado

4

Teor´ de Grafos ıa

2-grafo orientado

Grafo orientado con un lazo

1.1.4.

Definici´n o

Dos grafos G1 = (N1 , A1 ) y G2 = (N2 , A2 ) son : a) Iguales cuando N1 = N2 y A1 = A2 . b) Isomorfos cuando existe una biyecci´n f : N1 → N2 que preserve las relaciones de o adyacencia, es decir, que para todos x, y ∈ N1 , (x, y) ∈ A1 ({x, y} ∈ A1 ) si y s´lo si o (f(x) , f(y) ) ∈ A2 ({f(x) , f(y) } ∈ A2 ), a la funci´n f se le denomina isomorfismo. o Ejemplo 3: Para los grafos G1 y G2 : d

es e e

a s

d

d

d

e

des e G1

¡ ¡ sc

dsb ¡ ¡ ¡

3s

d d

d£ g £ d g £ g d £ d g s ds 2 g 5 £ d

£

£ £

£g £ g

1 s

g

g g

s4

G2

La funci´n f : N1 → N2 definida por f(a) = 1 , f(b) = 2 , f(c) = 3 , f(d) = 4 , f(e) = 5 o da como resultado un isomorfismo y por tanto G1 es isomorfo a G2 .

1.1.5.

Observaci´n o

a) Diremos que un grafo es valorado sobre los nodos, (conexiones) cuando existen una o m´s funciones relacionando N(A) con un conjunto de n´meros. a u b) En la mayoria de las aplicaciones de grafos existen datos cuantitativos asociados a nodos o conexiones involucradas en el problema; los modelos correspondientes involucran, en esos casos, grafos valorados.

Teor´ de Grafos ıa

5

* En muchas situaciones hay inter´s en el particionamiento del conjunto de nodos, de e un grafo en subconjuntos que tengan ciertas propiedades importantes para el estudio que se va a realizar.

1.1.6.

Definici´n o

Un grafo G = (N, A) se denomina grafo k-partido si N se puede particionar en subconjuntos N1 , N2 , . . . ,Nk , tales que no haya dos nodos adyacentes en un mismo Ni . * Cuando K = 2 el grafo G es llamado bipartido. Ejemplo 4: La siguiente figura muestra un grafo bipartido y un grafo no bipartido. a s r
& sc s ¡e ¡ e

a

r

rr& & & rr rs d & $ & $$$ $ b s &$$ &$ $ˆ ˆ ˆ ˆˆˆ ˆˆˆs e

rr

&

c s ¡ sc (’ ’ (

¡ ¡

¡ ¡

¡ ¡

e

e

e

e

e

e

es b

Ejemplo 5: La siguiente figura muestra un grafo 3 -partido.

a s

’ ( ’( ’ ’ (’ b( ’ ’s f s ˜ 4 ’ ˜ 4 ˜ 4 ˜ ’ 4 ˜ ’ 4 ˜ 4 ’4 ˜s

( (

’

’ ’

se

d

1.2.

Ejemplos de modelado de grafos

La teor´ de grafos como sistema matem´tico abstracto, desempe˜a tambien un papel ıa a n importante en varios campos de las ciencias de la computaci´n, tales como la teor´ de la o ıa conmutaci´n y dise˜o l´gico, inteligencia artificial, lenguajes formales, gr´ficos por como n o a putadora, sistemas operativos, escritua de compiladores y organizaci´n y recuperaci´n de o o informaci´n. o

6

Teor´ de Grafos ıa En esta secci´n se presentar´ algunos ejemplos en losque se utilizan grafos. o a

Ejemplo 1: El siguiente grafo modela las rutas m´s importantes que unen, entre si las a ciudades principales del Per´. El n´mero o peso que se asocia a cada arista denota el costo u u del pasajin entre las dos ciudades. Un agente viajero como consecuencia de las limitaciones de presupuesto, podr´ estar interesado en visitar todas las ciudades a un costo m´ ıa ınimo partiendo de la opci´n central ubicada en la capital. o

Lima s

’ ’

 Arequipa’s ’

’ ’









Cusco s

Tacna’s
’

Ejemplo 2: Los grafos sirven con frecuencia a quienes hacen simulaci´n por como putadora se sistemas de tr´fico. Los modelos se utilizan para poner de manifiestos puntos a conflictivos actuales o futuros, y para sugerir y probar cambios propuestos a nuevos sistemas. En una ciudad, el sistema de calles se puede modelar como un grafo en el cual los cruces se representan como n´dos y los segmentos de las calles existentes entre los cruces o son las aristas. As´ el grafo es una abstraci´n de un sistema de calles de una ciudad, en el ı o cual las aristas estar´ etiquetadas con nombres de calles, densidades de tr´fico y cosas ıan a parecidas. Ejemplo 3: Hay muchos programas que constan de m´dulos que se invocan unos a o otros. Los grupos de llamadas representan los m´dulos mediante nodos. Una linea dirigida o que va del nodo x al nodo y indica que x invoca y. Cuando uno de los modulos invoca a otro, tiene que haber una comunicaci´n entre esos m´dulos a trav´s de una interfaz. La o o e interfaz suele ser una lista depar´metros. a Mediante el modelado de un programa a trav´s de un grafo de llamadas extendido, e que muestra las interfaces de los m´dulos, se puede investigar sobre la calidad global de o los programas.

Teor´ de Grafos ıa A

7

& a &

&

&

&

& c





  ~  & &

B

C
& & a & c &

D

c

c

E

F

G

Ejemplo 4: Durante el siglo XVII, la ciudad de K¨nigsberg (antes en Prusia Oriental; o llamada ahora Kalingrado, en Rusia) estaba dividida en cuatro zonas (incluida la isla de Kneiphof) por el rio Pregel. Siete puentes comunicaban estas regiones, como se muestra en la figura siguiente:

Figura 1.1: Puentes en K¨nigsberg o

Se decia que los habitantes hacian paseos dominicales tratando de encontrar una forma de caminar por la ciudad cruzando cada puente exactamente una vez y regresando al punto donde se hab´ iniciado el paseo. ıa Con el fin de determinar si existia o no dicho circuito, en 1736 el matem´tico suizo a Leonhard Euler, represent´ las cuatro zonas de la ciudad y los siete puentes con el multio grafo, que se muestra en la figura siguiente:

8 c s rr

Teor´ de Grafos ıa

rr

a s s ¨ ¨¨ ¨

rr

rr ¨¨

¨¨

rrs d ¨¨

b

Y as´ se di´ inicio a la Teor´ de Grafos. ı o ıa Ejemplo 5: Un grafo dirigido es una forma natural de describir, representar y analizar proyectos complejos que consten de muchas actividades relacionadas entre si. Este proyecto podr´ ser por ejemplo, el dise˜o y construcci´n de una presa hidroel´ctrica, o el dise˜o ıa n o e n y construccci´n de una casa. o Consideremos una compa˜´ constructora de edificios que fabrica casas prefabricadas; nıa las casas se trasladan y se asientan sobre cimientos de hormig´n en las parcelas adquirio das al efecto. La colocaci´n de una casa prefabricada sobre un cimiento de hormig´n en o o una cierta parcela implica descomponer el proyecto en una serie de actividades o tareas relacionadas entre si, segun se muestra en la siguiente tabla:

Teor´ de Grafos ıa Borde a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 a17 a18 a19 a20 a21 a22 a23 a24 a25 a26 a27 a28 Actividad Selecci´n y adquisici´n del terreno o o Selecci´n del dise˜o del edificio o n Obtenci´n del permiso de edificaci´n o o Admisi´n de ofertas de subcontratos o Selecci´n de subcontratos o Excavasi´n de s´tanos o o Construcci´n de s´tano o o Petici´n de puertas y ventanas o Env´ y recepci´n de puertas y ventanas ıo o Tender muros y tejado Rozar para fontaner´ ıa Rozar para cableado el´ctrico e Cubrir tejados Recibir puertas y ventanas Dise˜o de promoci´n plubicitaria n o para la venta del inmueble Publicidad Instalaci´n de barrera de vapor o y aislamiento Impermeabilizaci´n o Pintura de interiores Instalaci´n de armarios o Instalaci´n de alfombras y pisos o Instalaci´n de luminosos o Isntalaci´n de sanitarios y equipo o de calefacci´n o Instalaci´n de cubiertas exteriores o Pinturas de exteriores Traslado de la casa al solar Realizaci´n de conexiones: retoques o Ajardinamiento de la parcela Actividades previas (a1 , a2 ) (a1 , a2 ) (a4 ) (a3 , a5 ) (a6 ) (a1 , a2 ) (a8 ) (a3 , a5 ) (a10 ) (a10 ) (a10 ) (a9 , a11 , a12 ) (a2 ) (a3 , a15 ) (a13 , a14 ) (a17 ) (a18 ) (a19 ) (a19 ) (a19 ) (a19 ) (a13 , a14 ) (a24 ) (a20 , a21 , a22 , a23 , a25 ) (a7 , a26 ) (a7 , a26 ) Duraci´n o (d´ ıas) 2 5 1 14 2 1 7 3 10 12 5 3 4 7 3 14 2 5 3 3 5 2 6 2 3 1 2 4

9

La descripci´n del proyecto se puede representar mediante un sencillo grafo dirigido, o que se denomina red de informaci´n. Los nodos representan sucesos y los arcos o son las actividades. Adem´s, a cada arco del grafo se le asignaun valor ponderado a (tiempo), que es el tiempo necesario para terminar esa actividad. Algunas actividades especiales (los arcos discontinuos) de al figura representan mudas. La naturaleza y prop´sito de las actividades mudas se describiran m´s adelante. o a

a20
3

10

7

a8
3 10

a9

19

22 D6
0

a23
6

a28
20

4

0

D7

3

a3
1 14 2

5

a10
12

9

a11
5

11

a14
7

12

a17
2

13

a18
5

15

a19
3

16

a22
2

18

D5
0

a26
1

21

a27
2

23

a1

2

a4
1 D1 0 4

a5

a12

3

a13
D3 0 10
4

D8 0
5

a21
2

D4
0

24

a24

17

a2

5

a6
D2 2
0 1

14

a25
3

a7
8
3 7

a15
6

a16
14

Teor´ de Grafos ıa

Red de planificación para la construcción de una casa

Teor´ de Grafos ıa

11

1.3.

Representacion num´rica de los grafos e

La representaci´n gr´fica no es la adecuada para implementar en un computador datos o a sobre una estructura de grafo, as´ que, ser´ necesaria una representaci´n num´rica con el ı a o e cual el computador pueda trabajar. Un grafo se puede representar num´ricamente de divere sas maneras, y las m´s adecuada depende de la aplicaci´n. Estas representaciones procua o ran necesidades de busqueda y almacenamiento (de car´cter esencialmente algor´ a ıtmico) o necesidades algebraicas o combinatorias.

1.3.1.

Matriz de adyacencia

Las diversas representaciones matriciales de estructuras de grafo esta habitualmente asociado a la necesidad de realizaci´n de c´lculos que involucran datos estructurales. o a Dado un grafo orientado G con n-nodos numerados v1 , v2 , . . . , vn (esta numeraci´n o define una ordenaci´n arbitraria en el conjunto de nodos) se puede definir la matriz o A de orden n ∗ n, donde: < A >ij = 1 si (vi , vj ) ∈ A 0 si (vi , vj ) ∈ A

que denominaremos matriz de adyacencia. Si un grafo orientado G tiene matriz de adyacencia A entonces AT es la matriz de adyacncia del dual direccional de G. La matriz de adyacencia de un grafo no orientado se puede representar en su forma triangular (superior o inferior) en vista que no hay distinci´n entre los dos sentidos o posibles para cada arista. Como limitaciones, cabe observar que ella no es adecuada para la reprsentaci´n de o hipergrafos en general. Con p-grafos podr´ tambi´n haber dificultades: en este caso a e los valores atribuidos a las posiciones no nulas ser´n los ordenes de multiplicidad a de los arcos o aristas y la matriz, por tanto, solamenete ser´ formada apenas por ıa valores 0 y 1. Tenga presente que muchos de la teor´ est´n basados en la posibilidad ıa a de ver la matriz de adyacencia como matriz booleana.

12 Ejemplo 1:
 d s   s  d

Teor´ de Grafos ıa

1 T d

d

5

s

d d

Digrafo

d ‚ d s3 d d ‚s d ©

2 T d

4

  A=  



1 0 0 1 0

0 1 0 1 1

0 1 0 0 0

0 0 0 0 0

1 0 1 0 0

     

Matriz de adyacencia

Ejemplo 2:

2s

s  1

 s3

Grafo simple Ejemplo 3:
 s3

4 s

 1 − − −  1 0 − −   A=  0 1 0 −  1 0 1 0 Matriz de adyacencia



2s d d

s  1

d

3 -hipergrafo no orientado

4ds

 1 − − −  1 0 − −   A=  0 3 0 −  0 1 1 0  Matriz de adyacencia

Otra de las desventajas de usar matriz de adyacencia para representar un grafo se debe a que este tipo de representaci´n hace dif´ almacenar informaci´n adimeno ıcil o sional acerca del grafo, por ejemplo, si es precio incuir informaci´n aceca de los nodos, o ser´ preciso representarla mediante alguna estructura adicional de almacenamiento. a

Teor´ de Grafos ıa

13

1.3.2.

Lista de adyacencia

Esta forma es la m´s conveninte para la entrada de datos por la simplicidad y a “econom´ ıa”de su representaci´n. o Es construida como un conjunto de listas de nodos, cada lista esta formada por un nodo y por un conjunto de nodos que reciben de ´l un arco o que con ´l comparten e e una arista.

Ejemplo 1: Nodos Origen Destino a b b ac c adef af d e a ce f Nodos Destino Origen a bcd b a c bf c d e cf cd f

b

y

X a ‘V y V VV VV VV Gcd ØØ ØØ ØØ ÓØØ eo

Gd 6 

f

Digrafo Ejemplo 2: s ¡e ¡ e

Listas de adyacencia

a

e sf e ¡ e ¡e ¡ e ¡ e ¡ e ¡ e ¡ ds ¡ ese e  e ¡   c  ¡ e s s b ¡ ¡

Nodos a bcf b ace c abd d efc e dfb f dea

La matriz de adyacencia no es la m´s “econ´mica”de las formas de representaci´n a o o 2 posiciones en memoria, en cuanto a la lista de adyacencia de grafos; ella ocupa n utiliza apenas n + m posiciones.

1.3.3.

Matriz de Incidencia

La matriz de incidencia B, es una matriz de orden n ∗ m donde a cada fila le corresponde un nodo y cada columna una conexi´n. o

14

Teor´ de Grafos ıa Para G = (N, A) orientado y sin lazos, la matriz de incidencia se define por:

∃ ak = (vi , vj ) ⇔

< B >ik = +1 y < B >jk = −1 < B >γj = 0 , ∀ γ = i, γ = j

Para G = (N, A) no orientado, se define por:

∃ ak = (vi , vj ) ⇔

< B >ik = < B >jk = −1 < B >γj = 0 , ∀ γ = i, γ = j

Ejemplo 1: as 2 c s' E sd 



1
   3  

4
  ~s c

c

5

a b c d

1 +1 −1 0 0

2 +1 0 −1 0

3 +1 0 0 −1

4 0 +1 0 −1

5 0 0 −1 +1

b

La matriz de incidencia tiene la desventaja de crecer con el n´mero de conexiones u que tenga el grafo. Presenta, por ejemplo, inter´s en la representaci´n de hipere o grafos y de p -grafos valorados; tambi´n es utilizada en la formulacion de modelos de e programaci´n matematica, (en particular, de programaci´n entera) que involucran o o estructura de grafo; es tambi´n usada en la determinaci´n de grafos de intersecci´n e o o y de grafos adjuntos.

1.3.4.

Matrices Figurativas

Se trata de matrices en las cuales los nodos , o las conexiones , son representadas por cadenas de caracteres. Son usadas en problemas de enumeraci´n combinatoria de o sub-estructuras de grafos. Los ejemplos m´s comunes son llamadas matrices latinas, a por ejemplo:

Teor´ de Grafos ıa
1 2 a 8 3 6 c 7 d 4 5 b b c d db dc Representación por nodos a b c d a b c d 4 6 a 1 b 2 c 8 d 3 5 7 a aa ab ac ad bd cd

15

Representación por arcos

1.4.
1.4.1.

Relaciones de Adyacencia
Definici´n o

En un grafo orientado G = (N, A) se dice que y ∈ N es sucesor de x ∈ N, cuando existe (x, y) ∈ A. Una definici´n dual direccional correspondiente es la de antecesor; luego, o habiendo (x, y) ∈ A, x es antecesor de y. * Los conjuntos de sucesores y de antecesores de un nodo x son denotados, respectivamente, Γ+ (x) y Γ− (x) y corresponden a los conjuntos de elementos no nulos de la fila y de la columna asociadas a x en la matriz de adyacencia del grafo.

1.4.2.

Definici´n o

Vecino o nodo adyacente de un nodo x, en un grafo orientado o no, es todo nodo que participa de una conexi´n con x. o * El conjunto de los vecinos de x ∈ N es denotado Γ(x). Ejemplo 1: * La informaci´n contenida en los conjuntos de sucesores o antecesores, o de vecinos, o equivale a la contenida en el conjunto de conexiones. Por tanto , se puede representar 1-grafo orientado como G = (N, Γ+ ) o G = (N, Γ− ), y un 1-grafo no orientado por G = (N, Γ). * Estos conceptos pueden ser entendidos a subconjuntos de nodos, por ejemplo, si tenemos que A ⊆ N : Γ+ (A) = x∈A Γ+ (x)

16

Teor´ de Grafos ıa

x

x

x

x

* Cabe observar que la notaci´n utilizada es abreviada; trat´ndose, de hecho, de como a ponentes entre conjuntos, la notaci´n correcta es el tipo Γ({x}). o * Las nociones de sucesor y de antecesor pueden ser aplicadas iterativamente, llevando a conceptos que implican la conexi´n directa o indirecta entre nodos en grafos o orientados. Los conjuntos as´ obtenidos son conocidos como clausuras transitivas. ı

1.4.3.

Definici´n o

Un nodo y es alcanzable a partir de un nodo x, cuando existe en el grafo considerado una secuencia de sucesores que se inicia en x y llega a y.

1.4.4.

Definici´n o

La clausura transitiva directa Γ+ (x) de un nodo x es el conjunto de los nodos alcanzables apartir de x y que la clausura transitiva inversa Γ− (x) de x es el conjunto de los nodos o partes de los cuales x es alcanzable.

* Las dos definiciones anteriores son duales direccionales; presentamos a continuaci´n o el proceso iterativo que conduce a la determinaci´n de Γ+ (x). Por coherencia con la o idea de alcanzable, se acepta, que el nodo origen como alcanzable a partir de cero etapas:

Teor´ de Grafos ıa

17

Γ0 (x) = {x} Γ+1 (x) = Γ+ (x) Γ+2 (x) = Γ+ (Γ+1 (x)) . . . Γ+n (x) = Γ+ (Γ+(n−1) (x)) n Γ+ (x) = k=0 Γ+k (x)

Ejemplo 1:

x

x

* Es claro que, si y ∈ Γ+ (x), y es un descendiente de x; si y ∈ Γ− (x), y es un ascendiente de x. * La noci´n de clausura transitiva est´ conceptualmente asociada a las ideas de comuo a nicaci´n y de control. Si definimos un grafo G = (N, A) considerado o N = {Habitantes de Arequipa} y A = {(x, y)/x conoce a y}, la clausura transitiva directa de una persona k ser´ el conjunto de todas las personas que podr´n a a tomar conocimiento de una informaci´n que k disponga, a trav´s de comunicaci´n o e o de persona a persona (o sea, sin el uso de los medios de comunicaci´n de masa). La o noci´n puede ser usada por tanto, para estudiar el efecto de la comunicaci´n informal o o conocida como “tele-cipo”.

18

Teor´ de Grafos ıa

1.4.5.
+

Definici´n o

Se denomina grafos transitivos directos o inversos de un grafo G = (N, A) a los grafos − G = (N, Γ+ ) y G = (N, Γ− ). * En los grafos no orientados las definiciones anteriores no ofrecen mayor inter´s, en e vista del concepto, m´s abrangente, de conexidad que ser´ discutido m´s adelante. a a a

1.5.

Vecindades de conexiones

Las definiciones que a continuaci´n se dan son, expl´ o ıcitamente para grafos sin lazos.

1.5.1.

Definici´n o

a) Dos conexiones que parten de un nodo se denomina adyacentes. b) Una conexi´n es incidente en un nodo si ella es constituye es uno y apenas uno de o sus extremos. En un grafo orientado, un arco incide exteriormente en x ∈ N si x es su extremo inicial e interiormente si x fuera su extremo final. c) Para un conjunto A ⊂ N , se dice que un arco incide, exterior o interiormente, en A, si ´l incide de la misma forma en un x ∈ A. e * Si el grafo fuera no orientado, s´lo diremos que una arista incide en A ⊂ N . o * Los conjuntos de arcos incidentes exteriores e interiores en A ⊂ N son denotados, + − respectivamente, ω(A) y ω(A) y sus cardinalidades son respectivamente el semigrafo + − exterior δ(A) y el semigrafo interior δ(A) . * En grafos no orientados, el conjunto de aristas incidentes en A ⊂ X ser´ denotado a ω(A) .

1.5.2.

Definici´n o

El grafo δ(x) de un nodo es el n´mero total de conexiones que en ´l inciden. u e
+ − * En grafos orientados, tenemos evidentemente, δ(x) = δ(x) + δ(x) y en grafos no orientado δ(x) = |ω(x) |. Se trata de una definici´n no orientada valida para p-grafos en o general.

* Un grafo no orientado en el cual δ(x) = k para todo x ∈ N es llamado regular (de grado k).
− + * Llamamos a un grafo orientado en el cual δ(x) = k (δ(x) = k) para todo x ∈ N , exteriormente regular (interiormente regular) (de semigrado k).

Teor´ de Grafos ıa

19

* Para 1-grafo, las cardinalidades de los conjuntos de sucesores (antecesores) de un nodo son iguales a los conjuntos de conexiones exteriormente (interiormente) incidentes que les corresponden.

1.5.3.

Definici´n o

Un grafo G = (N, A) ser´ sim´trico si y s´lo si: a e o (vi , vj ) ∈ A ⇒ (vj , vi ) ∈ A, ∀ vi , vj ∈ N * La matriz de adyacencia de G ser´ una matriz sim´trica; se puede entender, por a e tanto, un grafo sim´trico como equivalente a un grafo no orientado, del punto de e vista estructural (a menos de una eventual asim´trica de valoraci´n). e o

1.5.4.

Definici´n o

Un grafo G = (N, A) ser´ antisim´trico si y s´lo si: a e o (vi , vj ) ∈ A ⇒ (vj , vi ) ∈ A, ∀ vi , vj ∈ N * La noci´n es por tanto, orientada y un grafo antisim´trico no poseer lazos. La relaci´n o e o asociada a A puede ser de orden total o parcial (paternidad, edad, jerarqu´ sucesi´n ıa, o en el tiempo, etc.). Ejemplo 1:

q •‡FF  FFF  FF  FF   FF  FF  # ×o G• •

• •o
 •  •  • G•  •

Gq • •F  FFF   F  FF   FF   FF   FF   # × G• •

Grafo sim´trico e

Grafos

anti-sim´tricos e

1.5.5.

Definici´n o

Un grafo G = (N, A) ser´ completo si existe al menos una conexi´n asociada a cada a o par de nodos. * En el caso no orientado significa exactamente una conexi´n. o

20

Teor´ de Grafos ıa * El grafo completo poseer´ todos los nodos, es decir G = N, P2 (N ) . Evidentea mente, todas las estructuras de ese tipo con un mismo orden ser´n isomorfos; ellas a son conocidas como cliques y se denotan kn . * Los grafos bipartidos no orientados con el mayor numero posible de aristas, son llamados diques bipartidos y se denotan con kp,q , y el n´mero de aristas ser´ por u a tanto p.q . Ejemplo 2: s ¡e s d s s ƒ £g £ gƒ s £ g ƒ  £ g ƒs ˜ v ˜ 44  v £ 4 g  ˜ £ 4 ˜s vs g

k1 Ejemplo 3:

s

s

k2

s

¡ s

¡ ¡

e

e

k3

es

d d ds s

k4

k5

¨¨ s rr

¨¨ rr

¨¨

s

k1,3

rrs

s

s d s

d

d d

d

s

k2,2

ds

s $$ $$$&& $ s ˆ ˆˆˆ & & ˆˆs $ & $$ $ &$  $ˆ s ˆ ˆ ˆ ˆ s ˆ

k2,3

* Los cliques y cliqes bitardas tienen una gran importancia teor´ por las caracter´ ıa ısticas que confieren a los grafos, en los cuales figuren como subestructuras. Ejemplo 4:

Grafos orientados completos

Teor´ de Grafos ıa

21

* Los grafos orientados completos antisim´tricos son llamados grafos de torneo, por e que representan el resultado de campeonatos en deportes que no admiten empates (voley).

1.5.6.

Definici´n o

El grafo complementario G es aquel que posee el mismo conjunto de nodos y las conexiones no existentes en el grafo G = (N, A). ∗ G = (N, N x N − A) para G orientado ∗ G = (N, P2 (N ) − A) para G no orientado * Observe que el universo del conjunto de conexiones corresponde a las aristas de un clique, en el caso no orientado y los arcos de un grafo con todos los arcos posibles, inclusive los lagos, en el caso orientado (este grafo es llamado grafo cheio). Por otro lado, es frecuente que no se consideren los lagos en el caso orientado (como hacemos aqu´ con lo que el universo de referencia para la definici´n de un grafo ı), o complementario pasara a ser el grafo completo sim´trico. En el caso no orientado, la e definici´n deja explicitamente de considerar los lazos, al excluir P1 (N ) del universo o de referencia. Ejemplo 5:

•i r

A• r

•t

S •

•Ø G

S•Ø

•uj G

' •

1.5.7.

Definici´n o

Llamamos subgrafo a una sub-estructura G = (N , A ) tal que: N ⊆ N y A’ ⊆ A ∩ P2 (N ) (en el caso no orientado), o A’ ⊆ A ∩ (N × N ) (en el caso orientado)

22

Teor´ de Grafos ıa

Ejemplo 6: La figura nos muestra un grafo dirigido G y dos de sus subgrafo, G1 y G2 . e e e s s s
ƒ ƒ c w sd ƒ s bs ƒ T  ƒ  ƒ  ws ƒ G ƒ ƒ

bs

c s

T s

a G

a G1

a G2

ƒ w sd ƒ     G s

ƒ

Ejemplo 7: El llamado Locura Instantanea es un juego de ingenio que consiste en cuatro cubos cuyas caras estan pintadas con uno de los colores rojo (R) , blanco (B) , verde (V) o amarillo (A) , como se indica en la figura.

A B R V A B 1 A

A A A A A 2

R R V B A V 3 B

B R B V A 4

Hay diferentes versiones de este juego , pues depende de los colores utilizados en cada cara . El objetivo del juego es colocar los cubos en una columna de cuatro de modo que aparezcan los cuatro colores (diferentes) en cada uno de los cuatro lados de la columna. En primer lugar , se calculara el numero de ordenaciones posibles: Hay tres formas distintas de colocar el primer cubo. Si se coloca el cubo 1, por ejemplo, no hay diferencia de colocar la cara roja o la cara blanca opuesta sobre la mesa, como hay tres pares de caras opuestas, habra tres formas, como m´ximo de colocar el primer cubo en la base de la columna. a

Teor´ de Grafos ıa Hay 24 formas distintas de colocar el segundo cubo sobre el primero.

23

Aunque se repiten algunos colores, ning´n par de caras opuestas tienen el mismo u color, por lo tanto, se tiene seis formas de colocar el segundo cubo sobre el primero. Luego podemos estar el segundo cubo sin cambiar la cara de arriba del primer cubo o la cara de abajo del segundo, con cuatro rotaciones posibles podemos colocar; el segundo cubo arriba del primero de (3)(2)(4) = 24 formas. S´ continuamos con este razonamiento vemos que hay (3)(24)(24)(24) = 41472 posibilı idades por considerar. ¡Y podr´ no haber soluci´n! ıa o

Como entender´, es poco pr´ctico intentar la soluci´n por el m´todo de ensayo y a a o e error. ¡Es posible encontrar una soluci´n, si la hay utilizando grafos! o Al intentar resolver el rompecabezas nos damos cuenta de la dificultad de mantener el registro de colores en las caras opuestas de los cubos y de los colores de las columnas. Un o multigrafo etiquetado nos ayuda a visualizar la situaci´n.
4 R 1 3 B

4

3

2

1 1

4

2

Por ejemplo, el cubo 1 tiene un par de caras opuestas pintadas de amarillo(A) y verde(V), de modo que se traga una arista que conecte A y V y se etiqueta con 1 por el cubo 1.

A

2

V 4

A partir del multigrafo vemos que hay un total de 12 aristas en cuatro conjuntos de 3, seg´n las etiquetas de los cubos . En cada nodo , el numero de aristas incidentes a (o de) u dicho nodo cuentan el numero de caras en los cuatro cubos que tienen ese color . (cortamos un lazo dos veces) . Por lo tanto , para los cuatro cubos se tienen 5 caras (R) , 7 (B) o (V) y 6 (A). Con los cuatro cubos apilados en una columna, examinamos dos lados opuestos de la columna. Esta disposici´n da cuatro aristas del multigrafo, donde cada etiqueta aparece o una sola vez. Como cada color aparecer´ una sola vez en un lado de la columna cada color a debe aparecer dos veces como extremo de estas cuatro aristas. Si podemos obtener el mismo resultado para los dos otros lados de la columna, habremos resulto el rompecabezas.

24 Esta informaci´n la proporcionan los siguientes subgrafos: o Rs 4 s s

Teor´ de Grafos ıa

3

sB

Rs 2 3 s 1

sB

4 s A

V

A

V

1

2

(Se necesita que el segundo subgrafo no use ninguna de las aristas del primer subgrafo). La siguiente figura muestra la forma de acomodar los cubos, como le indican los subgrafos:

* Tenga presente, que la soluci´n de la mayoria de los problemas de aplicacion de la o teoria de grafos esta relacionada a la busca de un determinado tipo de subestructura.

Teor´ de Grafos ıa

25

1.5.8.

Definici´n: o

G = (N, A ) es llamado grafo parcial de G = (N, A) si A ⊂ A. * La definici´n es v´lida para grafos orientados o no y corresponde a un grafo obtenido o a por la supresi´n de conexiones del grafo original. Algunos autores llaman a G un o sub-grafo generador. Ejemplo 8: La figura muestra al grafo parcial G de G. s s d T d Es T d d s T Es d

d

* Las dos definiciones anteriores, aplicadas de modo trivial o no, corresponden a la noci´n de sub-estructura. El grafo original G, asociado a una subestructura, es llamado o un supergrafo de esa sub-estructura.

© s

d d d

d Es d

d ‚ ds 

d

s

E s

d ‚ ds 

1.6.
1.6.1.

Trayectoria de un grafo
Definici´n o

Un recorrido o itinerario o cadena, es una familia de conexiones sucesivamente adyacentes. * Una cadena ser´ cerrada si la ultima conexi´n de la sucesi´n fuera adyacente a la a ´ o o primera y abierta en caso contrario. (Una cadena abierta puede contener subtrayectorias cerradas).

26

Teor´ de Grafos ıa Ejemplo 1: En la siguiente figura, las cadenas estan destacadas en lineas continuas.
2 G1 • zz 1 1 zz z 1 1 zz zz 1 1 }z 3 •—h z h 1 1 zz hhh hh 1 1 zz z hh 1 1 zzz h }z G • • 4 5

•1 y1

y •h

z h3 z z z•—hhh hh z hh z hh z h z }• • • • • • • •G• • h

h

h

z

Ga z•

•h

h

h

h z

•z

z

z

hzz zhh

z h

z

z•

h

h

•

(a) •• • • • • • • •• zz • y

(b)
G1 {• {{ 1 { {{ 1 {{ { 1 y1 • •h {{{ { { 1 1  {{  1 1 {{{   G• •}{

(c) •• • • • • • • m•• 1 m mm
1 1

zz zz zz z • 1 •• • • ••z • • •• z z zz 1 zz zz 1 zz •• • • • • • • ••

(d)

(e)

•

mmm mmm mmm 1 mmm •m • 1 1   1 1   1 1  • • • • • • • •

(f)

•

La notaci´n es hecha indicando la sucesi´n a trav´s de los nodos, las conexiones o o o e de nodos y conexiones alternados, o apenas los nodos inicial y final, cuando eso fuera suficiente. Por ejemplo, la cadena (a) puede ser expresada de las siguientes formas : a a a a

= (1, 2, 3, 4, 5, 3) = ((1, 2), (2, 3), (3, 4), (4, 5), (5, 3)) = (1, (1, 2), 2, (2, 3), 3, (3, 4), 4, (4, 5), 5(5, 3), 3) = 1,3

En un grafo no valorado, el tama˜o de una cadena es el n´mero de conexiones n u por ella utilizadas ( contando las repeticiones ). Para el caso de grafos valorados , ser´ necesaria la generalizaci´n de distancias. a o Una cadena es simple si no repite conexiones ( por ejemplo b , d ) y es elemental o a sino repite nodos (por ejemplo b y e ). La segunda noci´n es m´s restrictiva: toda cadena elemental es simple, pero lo rec´ ıproco no es verdadero. Un ciclo es una cadena simple y cerrada (por ejemplo
c)

Se denomina la cintura (gi y th ) g(G) de un grafo al tama˜o del menor ciclo que n el presente. Un camino es una cadena en un grafo orientado, en el cual la orientaci´n de los arcos o es siempre la misma, a partir del nodo inicial. (por ejemplo b ).

Teor´ de Grafos ıa Un circuito es un camino simple y cerrado en un grafo orientado.

27

1.6.2.

Definici´n o

Una cadena abierta o cerrada, es euleriano cuando utiliza cada conexi´n del grafo una o unica vez y hamiltoniano cuando utiliza cada nodo del grafo una unica vez. ´ ´ * Si la restricci´n de unicidad es relajada, la cadena se dice pre-eureliano o preo hamiltoniano. * Un grafo es llamado eureliano(hamiltoniano) si tiene una cadena cerrada eureliano (hamiltoniano). * Absolver la inquietud de los habitantes de K¨nigsberg (Ej. 4 sec. 2) consite en o averiguar si dicho grafo es eureliano .

1.7.

Grafos conexos - Componentes f-conexas

El concepto de conexidad esta relacionada a la posibilidad de llegar de un nodo a otro en un grafo a trav´s de las conexiones existentes. Esto es, el estado de conexi´n de e o un grafo y adquiere aspectos diferentes conforme al grafo sea orientado o no. La idea de llegar est´ relacionada con la de alcanzable (def. 4.3)la cual puede ser usada con inter´s, a e especialmente en grafos orientados. Podemos ilustrar lo que acontece, considerando un grafo trial G = (N, φ) y adicion´ndole sucesivamente conexiones: a Conexidad en grafos no orientados:

• • G0

• •

• • G1

• •

• • G2

• •

•

~• ~~ ~~ ~~ • •

~• ~~ ~~ ~~ • •

•

G3

G4

Los grafos anteriores a G3 no admiten llegar de un nodo dado a cualquier otro nodo . En G3 y G4 ello siempre es posible, G3 es minimal en relaci´n a esa propiedad (como se o podra observar en grafos orientados, al suprimir cualquier arista).

28 Conexidad en grafos orientados:

Teor´ de Grafos ıa

•
 •

• • G1

•
 •

•
G•

• c ~~ ~~ ~  ~ G• •~ G3

•

•o

• c ~~ ~~ ~  ~ G• •~ G4

• cy ~~ ~~ ~  ~ G • •~ G5

•o

G2

La propiedad de llegar de un nodo a cualquier otro s´lo se da en G5 . o Observe que, tanto G4 como en G5 ning´n par de nodos es mutuamente no alcanzable u (al menos una de las dos direcciones es viable). Esto ya no ocurre en G3 , donde los dos nodos de la derecha son mutuamente inalcanzables. Esas diferncias, tienen gran importancia en grafos orientados y caracterizan a los llamados tipos de conexidad.

1.7.1.

Definici´n o

Un grafo (orientado o no) es conexo s´ para cualquier pareja de nodos del grafo se ı puede llegar al otro nodo partiendo de cualquiera de ellos. Ejemplo 1: Los siguientes grafos son no conexos:
•   

• • • • •

• • •

•
& •

7• P P•

•

•

• G1

•r G3

• {{ {{ { {{ {{ { {{ {{  G• •}{ G4

•o

G2

1.7.2.

Definici´n o

Un digrafo en el cual todo par de nodos es unido por al menos una cadena se denomina simplemente conexo o s-conexo.

Teor´ de Grafos ıa Ejemplo 2: Los siguientes grafos son s-conexos: •GG q • y • GG  GG  GG  GG  GG  G#  • o •cc c • cc  cc  cc  1  •cc cc cc cc 1

29

•o

•

• cy     •cc cc cc cc 1 •

y •           G• •

•o

1.7.3.

Definici´n o

Un digrafo en el cual, en todo par de nodos, al menos uno es alcanzable a partir del otro, se denomina semi-fuertemente conexo o sf-conexo. * Por tanto, en un digrafo sf-conexo G = (N, Γ+ ) se tendr´;∀x, y ∈ N : x ∈ Γ+ (y) y/o a + (x). y∈Γ * Por tanto, un digrafo es sf-conexo si y solo si para todo par de nodos existe un camino en al menos uno de los dos sentidos posibles. Ejemplo 3: Los siguientes d´ ıgrafos son sf-conexos:

•

•

 •

c •          • •o

•RR

i •RR RR  RRR RR RR  RR RR  RR  RR R%  % o • • G

i •RR  RRR RR  RR   RR   % o • •

1.7.4.

Definici´n o

Un digrafo en el cual toda pareja de nodos son mutuamente alcanzables se denomina fuertemente conexo o f-conexo. * Por tanto, todo par de nodos est´n comunicados por un par de caminos de sentidos a opuestos. * Por tanto, en un digrafo f-conexo G = (N, Γ+ ) se tendr´: a ∀ x, y ∈ N : x ∈ Γ+ (y) ∧ y ∈ Γ+ (x) o tambi´n : e + (x) = Γ− (x) = N ∀ x∈N : Γ

30 Ejemplo 4: Los siguientes digrafos son f-conexos:

Teor´ de Grafos ıa

•ˆII  III II  II   II  II  I Ö G • •

•o

• cy           G • •

u •@ f ||" @ ff || """ @@@ fff ff || 2p ~I|| """ @@@ •I @@ rrr• II "" r  @ II "" rrrr@  @ I$ "" rr G •yr •

1.7.5.

Observaci´n: o

a) Se puede afirmar, tanto por las definiciones como por algunos de los ejemplos, que todo digrafo f-conexo es tambi´n sf-conexo y s-conexo y que todo digrafo sf-conexo e es tambi´n s-conexo. En vista de esto, se establece la siguiente categorizaci´n de e o conexidad, las cuales constituyen una partici´n del conjuntode los digrafos: o C3 C2 C1 C0 = = = = digraf os digraf os digraf os digraf os que que que que son f − conexos son sf − conexos y que no son f − conexos son s − conexos y que no son sf − conexos no son s − conexos

b) Las propiedades de los digrafos de las categor´ C1 y C2 ameritan una discusi´n ıas o e en detalle por el inter´s en la presencia, en esos casos, de nodos privilegiados. La discusi´n de C3 est´ asociada con el concepto de conexidad. o a c) Para un digrafo G y su complemento G, se tiene: G ∈ C0 ⇒ G ∈ C3 G ∈ C1 o G ∈ C2 ⇒ G C 0 G ∈ C3 ⇒ G Ci , i = 0, 1, 2, 3 * La f-conexidad implica alcanzabilidad rec´ ıproca, lo que correponde a una relaci´n o sim´trica. Por otro lado, todo nodo es alcanzable de si mismo, lo que implica ree flexividad; y si Z ∈ N es alcanzable de y ∈ N y este es alcanzable de x ∈ N , entonces z es alcanzable desde x; luego la alcanzabilidad es transitiva. Por tanto la relaci´n de alcanzabilidad es una relaci´n de equivalencia sobre los nodos de un dio o grafo G = (N, A), lo que implica que ella defina una partici´n S = {S1 , S2 , . . . , Sγ } o del conjunto de nodos N . Los subgrafos correspondientes a los Si son denominadas componentes f-conexas maximales o simplemenete, componentes f-conexas.

Teor´ de Grafos ıa Si un grafo es f-conexo, la partici´n contendr´ apenas un elemento S = {N }. o a

31

Ejemplo 5: El grafo de la derecha es el mismo que el de la izquierda, pero con los nodos dispuestos de modo que se evidencia su pertenencia a la componente f-conexa correspondiente.

* La relaci´n de sf-conexida no es reflexiva, por tanto, las componentes sf-conexas no o corresponden a una participaci´n del conjunto de nodo N . o Ejemplo 6: En el siguiente grafo se muestra las componentes sf-conexas.

32

Teor´ de Grafos ıa

1.8.
1.8.1.

Algunos resultaos
Proposici´n o

Si G = (N, A) multigrafo entonces δ(v) = 2|A| v∈N Prueba Al considerar cada arista {a, b} del grupo G encontramos que la arista contribuye con una unidad a δ(a) y a δ(b) y en consecuncia, con dos unidades a δ(v) v∈N As´ ı δ(v) = 2|A| v∈N 1.8.2.

Colorario

Para cualquier multigrafo el n´mero de nodos de grado impar debe ser par. u δ(v) +
P ar Impar

δ(v) = 2|A|

Ejemplo 1: ¿Es posible tener un grupo 4-regular con 10 aristas? De acuerdo con la Prop.8.1: 4|N | = 2(10) de donde tenemos que el grafo solicitado tiene 5 nodos: s 4˜ 4 ¢f ˜ 4 ¢ f ˜ 4 ˜ 4 ¢ f ˜ s 4 ˜ s f ¢ ˜ 4 ¡ e˜ 4¡ e ˜ ¢ f 4 ¡ ˜¢ e f4 ˜ 4 ¡ e ¢ ˜4 f e ¢ 44 ˜˜ f ¡ ˜¡ e4 s fs ¢

1.8.3.

Proposici´n o

En un digrafo G = (N, A), todo nodo del digrafo se encuentra exactamnte en una componente fuerte.

Teor´ de Grafos ıa Prueba

33

Las componentes f-conexa son subgrafos definidos en alg´n elemento e la partici´n u o definida por la relaci´n de alcanzabilidad en N, es decir, que todo nodo del digrafo se o encuentra exactamente en una componente f-conexa.

1.8.4.

Teorema

Sea G = (N, A) un grafo o multigrafo no dirigido sin nodos aislados. Entonces G tiene un ciclo euleriano s´ y solo s´ G es conexo y todo nodo de G tiene grafo par. ı ı Prueba (⇒) Sea G euleriano. Entonces existe un ciclo que pasa por todo nodo v ∈ N, entonces para un par de nodos cualesquiera x y y existe una cadena simple que puede llegar de x a y; por tanto G es conexo. Por otro lado, al intentar recorrer en el ciclo euleriano podremos escoger un nodo y de ah´ proseguir atravesando los dem´s nodos, ı a borrando las aristas utilizadas, al atravesar un nodo x, su grado δ(x) disminuir´ en a dos unidades; luego, todos los nodos intermediarios en la cadena deber´n tener grado a par, o ser´ imposible anular todos sus grados al final de este proceso. El nodo inicial a tambi´n deber´ tener grado par, en vista que el uso de una de sus aristas adyacentes e a al inici´ lo dejar´ con grado viginte impar, lo que permitir´ su anulaci´n al final del o a a o proceso. (⇐) Sea G conexo, con todos sus nodos de grado par.Procederemos por inducci´n o en el n´mero de aristas. Se el n´mero de aristas de G es 1 ´ 2, entonces G debe ser: u u o
# '$  s

s "! &%s s 

o

o

que evidentemente son eulerianos. Ahora supongamos que G es euleriano para cuando hay menos de n -aristas. Luego, si G tiene n -aristas, seleccionamos un nodo c en G con punto inicial para construir un ciclo euleriano. Como G es conexo y cada nodo tiene grado par, existe al menos un ciclo que contenga a c. Si tiene todas las aristas de G, hemos terminado. Si no, eliminamos las aristas del ciclo en G, asegur´ndose de eliminar cualquier nodo qe haya quedado aislado. El sub-grafo restante a K tiene todos los nodos de grado par y si es conexo, hemos terminado ¿por qu´?. Si e K no es conexo, cada componenete de K es conexo y tendr´ un ciclo euleriano ¿por a qu´? e

34

Teor´ de Grafos ıa

2

1

Adem´s cada uno de estos ciclos eulerianos tiene un nodo que esta en . En cona secuencia, podemos partir de c y recorrer hasta llegar al nodo c 1 que est´ en el a ciclo euleriano de una componente de K, entonces se recorre este ciclo euleriano y al regresar a c1 , continuamos en hasta llegar a un nodo c2 que est´ en el ciclo a euleriano de la otra componente de K. Com el grafo G es finito, podemos continuar este proceso hasta construir un ciclo euleriano para G.

1.8.5.

Corolario

Si G es un grafo o multigrafo no dirigido sin nodos aislados, entonces podemos construir una cadena abierta euleriana en G si y s´lo si G es conexo y tiene exactamente dos o nodos de grado impar.

Prueba Si G es conexo y x y y son los nodos de G de grado impar, a˜adimos una arista {x, y} n a G. Ahora tenemos un grafo G conexo tal que todos sus nodos son de grado par. Por lo tanto, G tiene un ciclo euleriano C, cuando eliminamos la arista x, y de C, obtenemos un cadena abierta euleriana de x a y en G. Lo reciproco se deja como tarea. * Si regresamos al problema de los siete puentes de K¨nigsberg, nos daremos cuenta o que el multigrafo que lo representa es conexo, pero tiene cuatro nodos de grado impar. En consecuencia, no tiene ni un recorrido euleriano ni un ciclo euleriano. * Ahora que hemos visto, la soluci´n de un problema del siglo XVIII (que fue el inicio o de la teor´ de Grafos), la aplicaci´n contemporanea en el ´rea de las telecomunicaıa o a ciones. Pero primero hay que establecer la versi´n orientada del Teorema 8.4. o

Teor´ de Grafos ıa

35

1.8.6.

Corolario

Sea G = (N, A) un grafo o multigafo dirigido sin nodos aislados. El grafo G tiene un circuito euleriano dirigidi si y s´lo si G es conexo y δ + (x) = δ − (x) para todo x N. o Ejemplo 2: En la figura (a) tenemos la superficie de un disco de rotaci´n dividido en o ocho sectores de igual ´rea. En la figura (b) hemos colocado material conductor (sector a sombreado el ciculo interno) y no conducor (sectores sin sombrear) en el disco.

Cuando las tres terminales (mostrada en la figura) hacen contacto con los tres sectores dados, el material no conductorno produce u flujo de corriente y aparece y aparece u 1 en la pantalla de un dispositivo digital. Para los sectores con material conductor, se produce un flujo de corriente y aparece un 0 en la pantalla. Si el disco se rotara 45 grados (en sentido de las manecillas del reloj), en la pantalla se leer´ 110 (de arriba a abajo). As´ ıa ı, podemos obtener al menos dos (100 y 110) de las ocho representaciones binarias del 0 al 7. Pero ¿podemos representar los ocho n´meros binarios al rotar el disco? Para responder u esta pregunta, se construye un digrafo G = (N, A) donde N = {00, 01, 11, 11} y A se construye como sigue: Si b1 b2 , b2 b3 ∈ N ⇒ (b1 b2 , b2 b3 ) ∈ A. Esto produce el siguiente digrafo:

36
000

Teor´ de Grafos ıa

00 001 101 01 001 011 11 110 10 100

111

Se ve que este digrafo es conexo y que para todo x ∈ N , d+ = d− entonces por el (x) (x) Colorario 8.6, se tiene un circuito euleriano:
G 00 G 00 G 01 G 10 G 01 G 11 G 11

10 f

Al etiquetar cada arco a = (x , y) con la sucesi´n de tres bits b1 b2 b3 , donde x = b1 b2 y o y = b2 b3 , se determinan las ocho sucesiones de tres bits distintas (ver figura). As´ mismo, ı cualesquiera dos etiquetas de arcos consecutivos en el circuito euleriano son de la forma b1 b2 b3 y b2 b3 b4 . Partiendo del arco con etiqueta 100, a fin de obtener la siguiente etiqueta (000), concatenamos el ultimo bit de 000 , es decir, 0 , a la cadena 100. Entonces, la cadena resultante ´ 1000 proporciona 100 ( 100 0) y 000 (1 000 ). La siguiente etiqueta de arco es 001, por lo que concatenamosel 1 (el ultimo bit de 001) y obtenemos 10001, lo cual proporciona las tres ´ sucesiones de tres bits distintas 100 ( 100 01) , 000 (1 000 1) y 001 (10 001 ). Continuando de esta forma llegamos a la sucesi´n de ocho bits 10001011 (donde el ultimo 1 se envuelve) o ´ y estos ocho bits se acomodan en los sctores del disco giratorio como en la figura: A partir de la cual se obtiene el resultado de la figura (b). Al rotar el disco de la figura (b), se obtienen las ocho sucesiones de tres bits 100 , 110 , 111 , 011 , 101 , 010 , 001 y 000.

Teor´ de Grafos ıa

37

1.8.7.

Algoritmo de Fleury

* El algoritmo de Fleury obtiene un ciclo de Euler para un grafo conexo sin nodos de grado impar. * Una arista {x, y} es un puente en un grafo conexo G si al eliminar {x, y} se crea un grafo disconexo. * Sea G = (N, A) un grafo conexo con todos sus nodos de grado par. Paso 1: Se elige un nodo υ de N como nodo inicial para el ciclo. Sea π el ciclo por construir. Paso 2: Suponga que ya se ha construido π = (v , u , . . . w). Si en ω s´lo existe una arista o {w , z, se extiende π a π = (v , u , . . . w , z). Se elimina {w , z} de A y w de N . Si en w existen varias aristas, se elige una que no sea un puente {w , z}. Extienda π a π = (v , u , . . . w , z) y se elimina {w , z} de A. Paso 3:Repita el paso dos hasta que no sobren aristas en A. Fin del algoritmo. Ejemplo 3: Utilizando en algoritmo de Fleury en el grafo:

t ad

d

b t d

d

d

d

dtc

d

d

dt

et

d

ft d

d

d

d

d

dt g

d

d

dt

d

h

Se obtiene un ciclo euleriano π = (b , c , e , g , f , e , h , g , a , c , d , a , b) * Con respecto a las cadenas hamiltonianas surgen preguntas an´logas a las correa spondientes eulerianas. ¿Es posible determinar si existe una cadena hamiltoniana? y si existe ¿hay una manera eficiente de determinarla? Puede parecer sorprendente, pero la primera pregunat no ha sido resuelta de manera completa hasta la fecha. Sin embargo, daremos algunos resultados con base en los ejemlos. * Es claro que los lazos y las aristas m´ltiples no son muy utiles para determinar u ´ las cadenas hamiltonianas, ya que entre dos nodos s´lo puede utilizarse una arista. o Tambi´n es f´cil verificar que si un grafo G de n nodos tiene un ciclo hamiltoniano, e a entonces G debe tener al menos n aristas.

38

Teor´ de Grafos ıa

1.8.8.

Teorema

Sea G = (N, A) un grafo sin lazos, con |N | = n ≥ 2. Si δ(x) + δ(y) ≥ n − 1 para todos x , y ∈ N , x = y , entonces G tiene una cadena abierta hamiltoniana.

1.8.9.

Colorario n−1 2

Sea G = (N, A) un grafo sin lazos, con |N | = n ≥ 2. Si δ(x) ≥ G tiene una cadena abierta hamiltoniana.

, ∀x ∈ N entonces

1.8.10.

Teorema

Sea G = (N, A) un grafo sin lazos, con |N | = n ≥ 3. Si δ(x) + δ(y) ≥ n para todos x , y ∈ N no adyacentes, entonces G tiene un ciclo hamiltoniano. abierta hamiltoniana.

1.8.11.

Corolario n 2

Si G = (N, A) es un grafo sin lazos, con |N | = n ≥ 3 y si δ(x) ≥ entonces G tiene un ciclo hamiltoniano.

para todo x N ,

1.8.12.

Corolario

Si G = (N, A) es un grafo sin lazos, con |N | = n ≥ 3 y |A| ≥ 1 (n2 − 3n + 6) entonces 2 G tiene un ciclo hamiltoniano. * Los rec´ ıprocos de los resulatdos anteriores no son v´lidos; es decir, las condiciones a dadas son suficientes, pero no necesarias, para la conclusi´n. o

Teor´ de Grafos ıa Ejemplo 4: Considere el siguiente grafo: a t
  ht     

39







 



 t  b tc t  d 

gt t f 













 t





 



e

En este caso n = 8, cada nodo tiene grado 2 y δ(x) + δ(y) = 4 para cada pareja de nodos no adyacentes x, y. El n´mero de aristas tambi´n es 8. Por tanto, las premisas u e de 8.10, 8.11 y 8.12 no son satisfechos, pero ciertamente existen ciclos hamiltonianos para este grafo. El problema que se ha considerado tiene algunas variantes importantes. En un caso, las aristas pueden tener valores que representen una distancia, un costo o algo similar. Entonces el problema es determinar un ciclo hamiltoniano tal que la suma total de valores en la cadena sea minima. Por ejemplo, los nodos podrian representar ciudades; las aristas, l´ ıneas de transporte; y el valor de una arista, el costo del viaje. Esta versi´n del problema se conoce como el problema del agente viajero. o

1.9.

Un modelo de administraci´n de proyectos o

Recu´rdese que el ej.5-sec.2 trataba, a efectos de planificaci´n, acerca del modelado e o de un proyecto por medio de un grafo dirigido en el cual cada nodod representaba un suceso (un instrumento de tiempo) y cada arista dirigida era un actividad o tarea que fuera preciso realizar. El costo o valor num´rico asociado a una actividad es el tiempo nesesario e para desarrollar esa actividad. El digrafo tiene un suceso inicial y un suceso final, que se denominan fuente y sumidero. Uno de los objetivos primarios del modelado de un proyecto en esta forma es obtener las actividades cr´ ıticas o bien el camino o caminos cr´ ıticos del digrafo. La longitud de un camino cr´ ıtico es el camino m´s largo desde la fuente hasta el a sumidero.

40

Teor´ de Grafos ıa

En la d´cada de 1950 aparecieron dos enfoques b´sicos para la planificaci´n temporal, e a o planteamiento y control de proyectos: PERT (Program Evaluation an Review Technique o T´cnica de Evaluaci´n y Revisi´n de Programas) y CPM (Critical Path Method o M´toe o o e do del camino cr´ ıtico). Aunque en un principio exist´ diferencias fundamentales entre ıan los dos m´todos, el subsiguiente desarrollo de estos m´todos ha disipado esas diferencias. e e Consiguientemente, en lo que sigue no se distingue entre PERT y CPM. La construcci´n de una red de planificaci´n temporal est´ limitada por las reglas o o a siguientes: * Toda actividad debe ser represesntada por un unico arco (esto es, las actividades ´ son unicas). ´ C´mo m´ximo, una actividad puede salir de un nodo y terminar en otro (esto es, el o a grafo es simple). La segunda regla del uso de actividades mudas. Una actividad muda no requiere tiempo alguno para su terminaci´n, pero se necesita por que el grafo debe ser simple, y es o necesario modelar ciertas relaciones l´gicas. Como ejemplo, considere la actividad muda o D,de la figura del ej.5-sec.2. Dado que es preciso completar las actividades concurrentes a1 y a2 antes de que se puedan desarrollar las actividades a3 , a4 y a8 se tiende una actividad muda (que se denota mediante un arco discontinuo) con un tiempo 0 que va desde el suceso 2 hasta el 3. En general se puede demostrar que es posible evitar los multigrafos mendiante el uso de actividades mudas. El objetivo principal de la administraci´n de proyectos es determinar el camino cr´ o ıtico y producir una planificaci´n temporal que muestra los instantes de comienzo y finalizaci´n o o pora todas las actividades de la red. Para la determinaci´n de un ade estas actividades o temporales resultan utiles los siguientes conceptos: ´

1.9.1.

Definici´n o

El instante m´ ınimo de comienzo, T Ej , para cada suceso j, es el primer momento en que puede producirse ese suceso de tal manera que ya hayan finalizado todas las actividades entrantes de ese suceso. * El valor T Ej de cada suceso se genera efectuando una pasada hacia adelante en la red, desde la fuente hasta el sumidero. En t´rminos de la red esto correponde a la e asignaci´n de valores temporales a cada nodo (o suceso), de t al forma que el valor o que sea asigna a cada suceso es la cantidad de tiempo nesesaria para completar las actividades presentes a lo largo del camino m´s largo que lleve a ese suceso. Esto es, a se le asocia al suceso el valor que es el m´ximo, para todos los arcos entrantes de los a cortes de los arcos, m´s el tiempo asociado al nodo (suceso) en que tenga su origen a esa arista.

Teor´ de Grafos ıa

41

* Por definici´n, a la fuente se le asocia el valor cero. En nuestro ejemplo T E 2 = 5, o T E4 = 19.En general, el instante m´ ınimo para un suceso est´ dado por una longitud a m´xima desde la fuente hasta el suceso. a Para evitar la enumeraci´n de todos los posibles caminos desde la fuente hasta alg´n o u suceso j, se puede emplear una aproximaci´n que se representa en la forma siguiente: o

En donde puede ocurrir que haya varias actividades en el suceso j. Una actividad t´ ıpica desde alg´n suceso i hasta el suceso j tiene una duraci´n estimada de tij unidas de tiempo. u o Por consiguiente: T E1 = 0 T Ej = max{T Ei + tij } , j = 1 i Para todas las posibles actividades que entren en el suceso j. Para nuestro ejemplo: T E2 = = = T E3 = = = T E4 = = = T E5 = = = max{T E1 + t12 } max{0 + 5} 5 max{T E1 + t13 , T E2 + t23 } max{0 + 2, 5 + 0} 5 max{T E3 + t34 } max{5 + 14} 19 max{T E3 + t35 , T E4 + t45 } max{5 + 1, 19 + 2} 21

42

Teor´ de Grafos ıa

1.9.2.

Definici´n o

El tiempo m´ximo de finalizaci´n, T Li , es el ultimo mometo en que puede producirse a o ´ un suceso sin dar lugar a un retraso del proyecto. * El valor de T Li para cadasuceso se calcula efectuando una pasada hacia atr´s desde a el sumidero hacia la fuente. * El tiempo m´ximo de finalizaci´n asociado a cada suceso es el ultimo momento en a o ´ que puede finalizar una actividad sin dar lugar a un retraso en la fecha m´ ınima de finalizaci´n del proyecto (esto es, son los tiempos finales de terinaci´n asociados a o o aquellas actividades que no dan lugar a que aumente el valor TE del nodo sumidero). El valor del tiempo m´ximo de terminaci´n, TL, es el mayor valor que seguir´ pera o a mitiendo que todas las actividades que comiencen en ese nodo finalicen sin dar lugar a un aumento global del tiempo necesario. En t´rminos del grafo, se asigna a cada e nodo un valor que es el m´ ınimo, de entre todas las aristas salientes, del nodo de destino de esa arista. El valor TL del sumidero es igual a su valor TE. * En general, e tiempo m´ximo de finalizaci´n para cualquier suceso se puede cacular a o de la siguiente manera:

T Ls = T E s , donde s es el sumidero T Li = max{T Lj − tij } , i = s i Es preciso tomar el m´ ınimo por que al satisfacer la fecha final m´s temprana tambi´n a e se satisfacen las posteriores.

Lista de ejercicos
1.- Los turistas Jenssen, Leuzinger, Dufour y Medeiros se encuentran en un bar de Paris y comienzan a conversar. Las lenguas disponilbes son el ingl´s, el franc´s, el e e portugu´s y el alem´n; Jenseen habla todas, Leuzinger no habla apenas el portugu´s, e a e Dufour habla franc´s y alem´n y Medeiros habla ingl´s y portugu´s. e a e e a) Represente por medio de un grafo G = (N, A) todas las posibilidades de que uno de ellos dirija la palabra a otro, siendo comprendido. Defina N y A. u b) Represente por medio de un hipergrafo H = (N, A ) las capacidades ling¨isticas del grupo. ¿Cual es el significado de las intersecciones ai ∩ aj donde los ak ∈ A ? 2.- La figura muestra un grafo no dirigido que representa una secci´n de unos grandes o almacenes. Los nodos indican el lugar donde se localizan las cajas; las aristas indican los pasillos que hay entre ellas. Los almacenes necesitan instalar un sistema de seguridad que consiste en colocar guardias (vestidos de civil) en ciertas cajas, de manera que cada cajero tenga un guardia en su lugar o que haya un solo pasillo entre u ınimo de guardias necesarios?. una caja con guardia y el cajero. ¿Cual es el n´mero m´ a c h c d c
 



 ce c

b c f c c cc c

g

j i 3.- Mostrar que los grafos dados son isomorfos :

ck

1 c 5 c 2 c 6 c 3 c 7 c c4 c

a c

8

d

c h c

d e dc

f c

cb

g d

c

dc

c

43

Grafos 44 4.- Mostrar que los digrafos dados son isomorfos :

Lic. Wilber Ramos Lov´n o

a c'

d T

d

d ‚ dc e d s d d © dc c Ec

d



cb

c

c2 ¢ d ¢ d ¢ d 1 c' ¢ © ‚ dc3 d ¢ T T d¢ ¢d d ¢ d ¢ d ¢ d ¢ ‚ dc c ' ¢

5

4

5.- Mostrar que los digrafos dados no son isomorfos : 1 c c2 d d c3 c

4 c 6 c a c

7

c

5

c

8

g

c e c

cc

d c f c cb

c

h

6.- Cada uno de los siguientes multigrafos surge en el an´lisis de un conjunto de cuatro a bloques para juego de “locura instantanea”. Determine en cada caso si es posible resolver el acertijo.

Lic. Wilber Ramos Lov´n o

Grafos 45

7.- Diga si los dos grafos presentados son o no isomorfos. Si fueran, presente la funci´n o que establece el isomorfismo entre ellos; caso contrario, explique por que.

Grafos 46

Lic. Wilber Ramos Lov´n o

8.- Escriba la matriz de adyacencia que representa a los siguientes grafos :

9.- Describa la matriz de adyacencias para Kn . 10.- Dada una matriz de adyacencias A para un grafo simple G, describa la matriz de adyacencia para el complemento G. 11.- Para el ejercicio 8 dise˜e la representaci´n en la forma de lista de adyacencias para n o el grafo indicado. 12.- Dise˜e una representaci´n en forma de matriz de incidencia para el grafo valorado n o de la figura : 1 c 1 c c

3 d s d d

E c2

d 1 d d

2 d dc Ec

3

2

4

13.- ¿Cu´l es el n´mero total de aristas en Kn ? Justifique su respuesta. a u 14.- ¿Cual es el grado de cada nodo de Kn ?

Lic. Wilber Ramos Lov´n o 15.-

Grafos 47

a) Si G1 y G2 son grafos no dirigidos (sin lazos), demuestre que G1 , G2 son isomorfos si y solo si G1 y G2 son isomorfos. b) Dtermine si los siguientes grafos son isomorfos :

16.-

a) Sea un grafo no dirigido con n-nodos. Si G es isomorfo a su propio complemento G. ¿Cuantas aristas debe tener G?. (Este grafo se conoce como auntocomplemetario). b) Encuentre un ejemplo de un grafo autocomplementario con cuatro nodos y otro con cinco nodos. c) Si G es un grafo autocomplementario con n-nodos, donde n > 1 , demuestre que n = 4k o n = 4k + 1, para alguna k ∈ Z− .

17.- Sea G un ciclo conn-nodos. Demuestre que G es autocomplementario si y solo si n = 5. 18.- Dar tres caminos elementales que vayan de 1 a 3 para el digrafo dado. ¿Existe algun circuito en el digraf? ¿Es transitivo en digrafo?

Grafos 48

Lic. Wilber Ramos Lov´n o

19.- Calcular todos los semigrafos exterior e interior de los nodos del digrafo dado. Dar todos los circuitos elementales de este grafo. Obtener un digrafo que no presente ningun circuito eliminando una arista del digrafo dado. Determinar todos los nodos que puedan alcanzar cualquier otro nodo del digrafo. a c' cb T E cc 

e

c c

Ec

d

20.- Para los digrafos dados en los ejercicios 18 y 19 determinar si son fuertemente conexos, semifuertemente conexos o simplemente conexos. 21.- Demostrar que un digrafo G es fuertemente conexo si y solo si existe un circuito en G que incluye a todos los nodos al menos una vez. 22.- Hallar las componentes f-conexas del digrafo dado el problema 19 . Calcular tambien sus componentes. 23.- El digrafo de abajo representa las respuestas a la pregunta. ¿Cuales son los colegas de a o quien Ud. m´s gusta? Dadas por una promoci´n de primer semestre de estudiantes de la UNSA (un grafo como este es denominado sociograma).

Use notaci´n y la nomenclatura convenientes para indicar la existencia de lider(s), o amistades rec´ ıprocas, problemas de relacionamiento, influencias directas o indirectas y asilamiento.

Lic. Wilber Ramos Lov´n o

Grafos 49

24.- Un museo de arte ha ordenado la exposici´n que actualmente presenta en cinco salas, o como muestra la figura. ¿Existe alguna forma de recorrer la exposici´n de modo que o Ud. pase por cada puerta solo una vez? En este caso, trace el recorrido.

25.- En la puerta de una mansi´n hist´rica, usted recibe una copia del plano de la casa, o o ver figura, ¿es posible visitar cada cuarto de la casa pasando por cada puerta solo una vez? Explique el razonamiento.

26.- Trace K2,3 , K2,4 , K3,3 . 27.- Obtenga una f´rmula para el n´mero Km,n . o u 28.- ¿Para qu´ valores de m y n Km,n tiene un circuito euleriano? e 29.- Dise˜e un juego de Locura inst´ntanea que tenga exactamente cuatro soluciones. n a

Grafos 50

Lic. Wilber Ramos Lov´n o

30.- En el siguiente grafo, los nodos representan ciudades y los n´meros de las aristas u se˜alan los costos de construcci´n de la carretera correspondiente. Determine un n o sistema de caminos de menor costo que conecte todas lsa ciudades. ¿Es esta una soluci´n unica?. o ´ ca d

d10 d d 15 b c d cc d d d 30 d 5 d d d d 7 d ce dd c 12 6 d d 9 d 8 d 20 dc c

5

f

14

g

31.- Suponga que un grafo tiene una matriz de adyacencias de la forma : A= A A

en donde los elemntos de las submatrices A y A son ceros. ¿C´mo debe ser el o esquema del grafo? 32.- Demuestre que un camino que no es simple debe contener un circuito . 33.- Demuestre que si G’ es un subgrafo conexo de un grafo G, entonces G’ esta contenido en un componente de G. 34.- Todo nodo y toda arista de un digrafo estan contenidos en una componete s-conexa y en un solo. 35.- Demostrar el Corolario 8.6. 36.- Determine los valores de n para los que el grafo completo Kn tiene ciclo euleriano. ¿Para cuales n tiene Kn una cadena abierta euleriana pero no un ciclo euleriano?

Lic. Wilber Ramos Lov´n o

Grafos 51

37.- Diga si es posible trazar la figura sin levantar el l´piz. Explique su razonamiento. a 2 c d
€ € d €€€ €€ d c3 1 c €€ d €€ € d  c7 d   4 c d c5  d   d c 

a)

1 c d d

d

d

dc

d dc 3

2 c

b)

4

6

38.- Sea N − {000, 001, 010, ..., 111}. Para cualquier sucesi´n de cuatro bits b 1 , b2 , b3 , o b4 ; trace una arista del elemento b1 , b2 , b3 al elemento b2 , b3 , b4 en N . a) Trace el grafico G − (N, A) descrito. b) Encuentre un ciclo euleriano para G. c) Distribuya ocho ceros y ocho unos de modo uniforme alrededor del dorbe de un disco que gira en el sentido de las manecillas del reloj, de modo que estos 16 bits formen una sucesi´n circular tal que las subsucesiones (consecutivas) o de longitud 4 proporcionen las representaciones binarias de 0, 1, 2, 3, ..., 15 en algun orden. 39.- Determine |N | para los siguientes grafos o multigrafos G. a) G tiene nueve aristas y todos los nodos tienen grado 3. b) G es regular con 15 aristas. c) G tiene 10 aristas con dos nodos de grado 4 y los demas de grado 3. 40.- Si G = (N, A) es un grafo conexo con |A| = 17 y δ(x) ≥ 3 para todo x ∈ N , ¿cu´l es a el valor m´ximo para |N |? a 41.a) Sea N = {a, b, c, d, e, f }. Dibuje tres grafos sin lazos que, en los grafos, δ (a) = 3 , δ(b) = δ(c) = 2 y δd = δ(e) = δ(f ) = 1 b) ¿Cu´ntos de los grafos de la parte (a) son conexos? a 42.- De un ejemplo de un grafo conexo tal que : a) No tenga ciclos eulerianos ni ciclos hamiltonianos; b) Tenga un ciclo euleriano pero no un ciclo euleriano; c) Tenga un ciclo hamiltoniano pero no un ciclo euleriano; d) Tenga un ciclo hamiltoniano y un ciclo euleriano.

Grafos 52

Lic. Wilber Ramos Lov´n o

43.- Determine si el grafo dado tiene un ciclo hamiltoniano, una cadena pero no un ciclo hamiltoniano, o ninguno de los dos. Si el grafo tiene un ciclo hamiltoniano, indique el ciclo. a c a) c d d cb

d

dcc d

d

a c b) c c cd   c

cb





d

d dc



ce   c

e

f

g

1 c c)

d d

d

4 a c c c

d c3 d

d

c2

d) d dc

1 c d d

d

2 c

d

d

5 cc dc

d dc 3

4

b

e)

’ ’ ’

’ ’

c ’ ’ ’

f)

d

’c

’ ’

e

’c

a c

b c

f

cc f f  f f fcg  fc c e f  f f f f  fc f c

cd

h

i