ApunteTeoriaGrafos

Apuntes de teor´ıa de grafos
Teor´ıa de Redes de Telecomunicaciones – 549112
Jorge E. Pezoa, email: jpezoa@udec.cl
´
Ultima
actualizaci´on: 5 de junio de 2013.
At the other end of the spectrum (of mathematics) is, for example, graph theory,
where the basic object, a graph, can be immediately comprehended.
W. T. Gowers, “The two cultures of mathematics,” ibid. pp. 65–78.

Resumen
En este breveapunte se resumen intuiciones, conceptos, definiciones y formalismos elementales de la
rama de las matem´
aticas llamada teor´ıa de grafos. La orientaci´
on del documento, aunque en un principio
no lo parezca debido a la cantidad de definiciones presentadas, es hacia las redes de telecomunicaciones. El
objetivo del apunte es presentar representaciones formales que modelen est´
atica y din´
amicamentelas redes de
telecomunicaciones. En primer lugar, se presentan informalmente los grafos. Luego, se formaliza el concepto
de grafo y se define el objeto grafo en t´erminos de conjuntos, pares ordenados y matrices. Se presentan
tambi´en m´etricas simples, transformaciones, extensiones y la teor´ıa espectral asociada a los grafos. Una vez
presentadas todas estas definiciones el lector se encontrar´a equipado con la maquinaria te´
orica necesaria
para poder representar, idealmente, redes determin´ısticas tiempo variantes y tiempo invariantes, condiciones
est´
aticas y simples situaciones probabil´ısticas. A continuaci´
on se presentan aplicaciones y algoritmos simples
de c´
alculo que se emplean en teor´ıa de grafos, y que por cierto son u
´tiles en redes de telecomunicaciones,
para calculartablas de ruteo en ruteadores, topolog´ıas libres de lazos e ´ındices de confiabilidad entre otras
variables y m´etricas de inter´es.

Figura 1: Mapa de conectividad de la red de Gnutella. Imagen sacada de http://personalpages.manchester.
ac.uk/staff/m.dodge/cybergeography/atlas/gnucleus_graph_large.gif en junio del 2010: “An Atlas of
Cyberspaces: Topology Maps of Elements of Cyberspace”.

´Indice

´
Indice

´Indice
1. Aclaraci´
on: limitaci´
on de responsabilidad legal del documento.

3

2. Agradecimientos.

3

3. Notaci´
on.

3

4. Introducci´
on.

4

5. Grafos: enfoque intuitivo.

5

6. Grafos: enfoque formal.
6.1. Definiciones b´
asicas. . . . . . . . . . .
6.2. Propiedades de los grafos. . . . . . . .
6.3. Algunos grafos especiales. . . . . . . .
6.4. Mapeos, relaciones yoperaciones sobre
6.4.1. Mapeos. . . . . . . . . . . . . .
6.4.2. Relaciones. . . . . . . . . . . .
6.4.3. Operaciones. . . . . . . . . . .
7. Teor´ıa algebraica y espectral:
7.1. Matriz de adyacencia. . . .
7.2. Matriz de incidencia. . . . .
7.3. Laplaciano de un grafo. . .

. . . .
. . . .
. . . .
grafos.
. . . .
. . . .
. . . .

representaci´
on
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . ..

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
..
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

6
6
8
8
11
11
12
12

matricial de grafos.
13
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

8. Aplicaciones.
8.1. M´etricas generales asociadas a la topolog´ıa de una red.
8.2. Rutas o trayectorias ´
optimas. . . . . . . . .. . . . . .
8.3. El ´
arbol de m´ınima expansi´
on de una red. . . . . . . .
8.4. Consenso y difusi´
on de informaci´
on en una red. . . . .
8.5. Redes escala invariante. . . . . . . . . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

A. Script en Matlab c para crear el grafo de la topolog´ıa de Reuna.

2

.
.
.
.
.

.
.
.
.
.

.
.
.
....