Apuntesdegrafos

101

Parte II

Teoría de grafos

Una de la partes de la matemática discreta que en estos últimos años ha experimentado un desarrollo más notable es la la teoría de grafos. Enmarcada dentro de la combinatoria, esta teoría
permite modelar de forma simple cualquier sistema en el cual exista una relación binaria entre
ciertos objetos; y es por esto que su ámbito de aplicación es muy general y cubreáreas que van
desde la misma matemática—topología, probabilidad, análisis numérico, etc.—hasta las ingenierías eléctrica, de telecomunicación e informática, la investigación operativa, la sociología o,
incluso, la lingüística.
En los capítulos siguientes se presentan los temas más importantes de la teoría de grafos:
grafos y digrafos; planaridad; árboles y árboles generadores; grafos eulerianos yhamiltonianos;
ciclos y cociclos fundamentales; flujos en redes de transporte; conectividad y apareamientos.

© Los autores, 2001; © Edicions UPC, 2001.

5 Grafos y digrafos

103

Capítulo 5

Grafos y digrafos
1.
2.
3.
4.
5.
6.
7.
8.

Definiciones básicas
Caminos, conectividad y distancia
Operaciones entre grafos
Digrafos
Representación matricial
Grafos y redes de interconexión
Planaridad: lafórmula de Euler
Caracterización de los grafos planares

En este capítulo se estudian los conceptos más básicos de la teoría de grafos y se introduce
la relación de la teoría con una de sus aplicaciones importantes: el diseño de redes de interconexión. La última parte del capítulo estudia los grafos planares. Una de las aplicaciones
interesantes del tema es el diseño de circuitos integrados e impresos.5.1 Definiciones básicas
Un grafo G ´V E µ es una estructura combinatoria constituida por un conjunto V V ´Gµ
de elementos llamados vértices y un conjunto E E ´Gµ de pares no ordenados de vértices
uv
uv relaciona los vértices u y v, se dice
distintos llamados aristas. Si la arista e
que u y v son vértices adyacentes y también que el vértice u (o v) y la arista e son incidentes.
De otro modo, losvértices se llaman independientes. Las aristas e uv y f wz son aristas
/ El número de
wz
0.
independientes si no tienen vértices en común, es decir, u v
vértices de G, V ´Gµ , es el orden del grafo y el número de aristas E ´Gµ es su tamaño. A
menudo resulta útil representar un grafo mediante un dibujo donde los vértices son puntos y

© Los autores, 2001; © Edicions UPC, 2001.

104

MATEMÁTICADISCRETA

w
u

v

Figura 5.1: Grafo con orden 5 y tamaño 8
las aristas líneas que unen los vértices adyacentes. Así, por ejemplo, en el grafo representado
en la figura 5.1, de orden 5 y tamaño 8, los vértices u y v son adyacentes, mientras que u y w
son vértices independientes. A veces conviene ampliar esta definición de grafo para permitir la
existencia de lazos, es decir, aristas que unen unvértice con él mismo, y aristas paralelas que
unen un mismo par de vértices. En este texto, un grafo con lazos y/o con aristas paralelas se
llamará multigrafo. En la figura 5.2 se muestra un multigrafo con un lazo l y aristas paralelas e
y f.
f

e
l

Figura 5.2: Multigrafo
Un grafo G¼ ´V ¼ E ¼ µ es un subgrafo de G ´V E µ si V ¼ V y E ¼ E. Cuando V ¼ V ,
el subgrafo G¼ se llama subgrafo generador de G.Dado V ¼ V , si el subgrafo G¼ ´V ¼ E ¼ µ
contiene todas las aristas que unen en G dos vértices de V ¼ , entonces se dice que G¼ es el
subgrafo inducido por V ¼ y se denota con G V ¼ . Por ejemplo, dado W V ´Gµ, G   W
G V Ò W es el subgrafo que resulta de suprimir en G los vértices del conjunto W y todas
las aristas incidentes con estos vértices. En particular, dado un vértice u ¾ V , el subgrafo
G  u G   u es el obtenido eliminando el vértice u y todas las aristas incidentes con u.
En cambio, la supresión de aristas no implica la eliminación de los vértices incidentes con
estas aristas. Dado el grafo G y el subconjunto de aristas F E ´Gµ, el subgrafo G   F es
simplemente ´V E Ò F µ. Si F está formado por una única arista e, entonces el grafo G   F se
denotará por G   e. Ver la figura...