curso c

Cap´
ıtulo 5
Grafos
La teor´ de grafos es una disciplina antigua con muchas aplicaciones
ıa
modernas. Sus ideas b´sicas las introdujo el gran matem´tico suizo Leona
a
hard Euler en el siglo XVIII. Euler utiliz´ los grafos para resolver el famoso
o
problema de los puentes de K¨nigsberg.
o
Los grafos se emplean para resolver problemas de diversas ´reas. Pueden
a
utilizarse, porejemplo, para determinar si se puede o no implementar un
circuito sobre una placa de una sola capa, para estudiar la estructura de una
red de internet, para determinar si dos ordenadores est´n conectados o no
a
dentro de una red inform´tica, para hallar el camino m´s corto entre dos
a
a
ciudades en una red de transportes, ...
El primer trabajo sobre la teor´ de grafos aparece en 1736 y fueescrito
ıa
por el matem´tico Leonnard Euler (1700-1783). Este trabajo comienza con
a
la discusi´n de un problema surgido en la ciudad de K¨nigsberg (ahora Kao
o
liningrado, Rusia). La ciudad estaba dividida en cuatro partes por los dos
brazos en los que se bifurca el r´ Pregel. Estas cuatro partes eran las dos
ıo
regiones a orillas del r´ Pregel, la isla de Kneiphof y la regi´n que quedaba
ıoo
entre ambos brazos del r´ Siete puentes conectaban entre s´ estas regiones
ıo.
ı
en el Siglo XVII. La figura siguiente ilustra las regiones y los puentes.
A

RÌO PREGEL

B

C

D

Los habitantes se preguntaban: ¿Es posible recorrer los siete puentes pasando por todos ellos una unica vez, partiendo y llegando al mismo sitio?
´
99

CAP´
ITULO 5. GRAFOS

100

Para tratar deresolver el problema, conocido como Problema de los puentes de K¨nigsberg, Euler represent´ esquem´ticamente las ´reas de tierra por
o
o
a
a
puntos y los puentes por l´
ıneas conectando esos puntos. El resultado constituye un ejemplo de grafo:
A

e1

e5

e2
B
e3

e4

C

e6
e7

V = {A, B, C, D}
E = {e1 , e2 , e3 , e4 , e5 , e6 , e7 }
e1 = {A, B}, . . . e7 = {C, D}

DDe la obtenci´n de algunas propiedades b´sicas de grafos, Euler dedujo
o
a
que no era posible recorrer todos los puentes una sola vez.

5.1.

Conceptos b´sicos
a

Inicialmente consideraremos grafos finitos no dirigidos.
Definici´n 52. Un grafo es un par G = (V, E), donde V es un conjunto
o
finito no vac´ cuyos elementos se llaman v´rtices o nodos, y E es una faıo,
e
milia, cuyoselementos se llaman aristas. Una arista es un “par no ordenado”
de v´rtices de V .
e
Se dice que dos v´rtices u y v de G son adyacentes si {u, v} es una arista
e
de G. Si e = {u, v}, se dice que la arista e incide en los v´rtices u y v, que la
e
arista e conecta u y v, o que los v´rtices u y v son extremos de la arista e.
e
Seg´n esta definici´n de grafo, se admiten aristas m´ltiples, es decir,arisu
o
u
tas distintas que inciden en los mismos v´rtices (como las aristas e1 y e2 del
e
ejemplo de los puentes de K¨nigsberg) y lazos, es decir, aristas de la forma
o
e = {v, v}. Se dir´ que un grafo es simple si no tiene lazos ni aristas m´ltiples.
a
u
Nota: No todos los textos utilizan la misma nomenclatura.
Si G = (V, E) es un grafo con |V | = n, se dice que G es un grafo finito deorden n.
El grado de un v´rtice de un grafo es el n´mero de aristas incidentes en
e
u
´l, exceptuando los lazos, cada uno de los cuales contribuye con dos unidades
e
al grado del v´rtice. El grado del v´rtice v se denota por ∂(v)
e
e

´
5.1. CONCEPTOS BASICOS

101

A los v´rtices de grado 0 se les denomina aislados. Se dice que un v´rtice
e
e
es colgante, o que es una hoja, sitiene grado 1.
Ejemplo.

v1
v2

v6

v3

v4

v5
v7

∂(v1 ) = 2
∂(v2 ) = 7

∂(v6 ) = 0
∂(v5 ) = 2

∂(v7 ) = 1
∂(v3 ) = 4

∂(v4 ) = 4

Proposici´n 10. La suma de los grados de todos los v´rtices de un grafo
o
e
G = (V, E) es igual al doble del n´mero de aristas.
u
Demostraci´n. Al calcular la suma de los grados de los v´rtices, cada arista
o
e
contribuye con dos...