Teora de Grafos

Introduccin
Grafos: modelos matemticos de situaciones reales Ejemplos:
Mapa de carreteras, plano de metro, callejero, red de PCs, plano de un circuito elctrico, rboles genealgicos, etc.

Aplicaciones:
Compiladores y traductores, Redes, Planificacin, etc.

Origen: 1736 (Los Puentes de Knisberg. Euler)

ndice
Conceptos bsicos y representacin Accesibilidad y conexin Grafos y relaciones Caminos Eulerianos y Hamiltonianos rboles Planaridad y coloreado

Conceptos bsicos
Un Grafo G es una terna (V,A,p) formada por dos conjuntos V (de vrtices) y A (de arcos) y una aplicacin p: A P2(V) (de incidencia)
p(a) = {u, v}. (u, v son los extremos del arco a) p(a) = {u} (a es un bucle)

Un Digrafo D = (V,A,p) dnde p: A VV

p(a) = (u, v) (u es el extremo inicial u origen de a v es el extremo final o destino de a) p(a) = (u, u) (a es un bucle)

Representaciones de un grafo
Representacin grfica
v1 a5 v5 a4 a8 v4 a3 v3 a5 a6 a7 a2 a6 a1 v2 v1 v2 a8 v3 a3 v4 a7 a4 v5

a1

a2

Conceptos bsicos
Un Grafo/digrafo G=(V,A,p) es Simple si p es inyectiva Un vrtice que no es extremo de ningn arco es un vrtice aislado. Grafo nulo: todos los vrtices son aislados

Conceptos bsicos
Si D un digrafo y cada arco se considera no dirigido se obtiene un Grafo asociado a D, G(D) Si G es un grafo y por cada arco a con p(a)={u,v} (u v) se consideran a1 y a2 con p(a1) = (u,v) y p(a2) = (v,u) se obtiene un Digrafo asociado a G, D(G).
(Si p(a) = {u}, se sustituye por p(a) = (u,u))

Grafos finitos

Conceptos bsicos
G = (V, A, p) es subgrafo de G = (V,A,p) si:
G es un grafo VV, A A y p= p|A

Subgrafo determinado por:

AA, G(A) = (V, A, p|A) V extremos de los arcos de A VV, G(V) = (V, A, p|A) A arcos que unen nodos de V Subgrafo estrellado determinado por vV, G(v)= (Vv, Av, p|Av) Av

arcos emergentes de v (tales que un extremo es v) y Vv extremos de los arcos de Av (adems de v)

G1G2. G1G2

Representaciones de un grafo
Matriz de Adyacencia
G= (V, A, p) con V = {v1,..., vn} Ma(G) = (aij) : i,j = 1..n
aij = nmero de arcos de extremos {vi, vj}/ (vi, vj)

a4 v1 a1 a2 a5 v2 a3 v3 v5 v4 a6

0 2 M (G ) = 0 0 0

2 0 1 0 0

0 1 0 0 0

0 0 0 1 2

0 0 0 2 0

Accesibilidad y conexin
Un camino en G es una sucesin
v0 a1 v1 a2 v2....an vn (n0) tal que los extremos (inicial y final) del arco ai son vi-1 y vi, con i = 1 .. n n es la longitud del camino v0 y vn son los extremos (inicial y final) v1, ..., vn-1 son los vrtices interiores Representaciones alternativas:
a1 a2 ....an
v0 v1 v2.... vn slo si G es simple

Accesibilidad y conexin II
Un camino v0 a1 v1 a2 v2....an vn es
cerrado si v0 = vn simple si sus arcos son distintos dos a dos elemental si sus vrtices son distintos dos a dos salvo, a lo sumo, los extremos ciclo si es cerrado, elemental, simple y de longitud positiva (>0)

Accesibilidad (D digrafo)
Sean u y v vrtices de D.
v es accesible desde u sii existe un camino en D desde u hasta v v es k-accesible desde u sii existe un camino en D de longitud k de u a v

Matriz de accesibilidad de orden k de D, Mk, es una

matriz booleana:
(k ) mij = 1 v j es k accesible desde vi

D*: Mady(D*) = M1 (= M), grafo simple asociado a D

Accesibilidad II
Mk = M Mk-1 (k > 1)
k (: producto booleano de matrices)

vi

vj

vi

vr

k-1

vj

Mk = Mk (k 1)

(potencia booleana)

Matriz de accesibilidad de D, M(D)

mij = 1 v j es accesible desde vi

Accesibilidad III
M(D) = I r1 Mr
Veamos que es suficiente con calcular un n finito de potencias

D= (V, A, p), n= |V|; vi vj V : vj es m-accesible desde vi para algn m1 vj es k-accesible desde vi para algn 1k n-1
[hay un camino de u a v hay un camino elemental de u a v]

vi

vj

Accesibilidad IV
M(D) = I M .... Mn-1

(n = |V|)

Digrafos simples y relaciones (I)

D= (V,A,p) simple se puede representar como (V,R) dnde:
v1Rv2 sii aA, p(a) = (v1,v2)

Ma(D) es ahora la matriz de la relacin (booleana)

Mi,j = 1 sii hay un arco de vi a vj sii vi R vj

Propiedades de las relaciones binarias

Reflexiva Simtrica Antisimtrica

v, vRv u , v, uRv vRu

v, a, p ( a ) = (v, v )
a , p ( a ) = (u , v ) u , v b, p (b) = (v, u )

i, M ii = 1

i, j , M ij = 1 M ji = 1

u v, uRv vRu u v a, p ( a ) = (u , v ) b, p (b) = (v, u ) i j , M ij = 1 M ji = 0

Digrafos simples y relaciones (II)

Propiedad transitiva de las relaciones binarias u,w,v uRw y wRv uRv u,v v u v u

M2 M

(A B sii i, j, aij = 1 bij = 1)

Cierre transitivo de R, RT : la menor relacin transitiva

que contiene a R

Cierre transitivo
Sea D = (V, R) con matriz de adyacencia M, calculamos DT = (V, RT) su cierre transitivo
M MT {R RT} M2 MT {RT transitiva} .... Si hay un camino no nulo de vi a vj , mTij = 1

MT = r1 Mr

[Ntese MT no coincide con M(D) y que MT es la matriz de adyacencia de un grafo, no la de accesibilidad]

Cierre transitivo II
D= (V, R), n= |V|; vi V : vi es m-accesible desde vi para algn m1 vi es k-accesible desde vi para algn 1k n
[hay un camino cerrado de longitud positiva en u hay un camino elemental, cerrado y de longitud > 0 en u (long n)]

Ntese que si R es reflexiva k =1

MadyT = M .... Mn

(n = |V|)

Conexin (G no dirigido)
Dos vrtices u y v de G estn conectados en G sii existe un camino que los une. La relacin de conexin, C, definida en V por:

uCv u y v estn conectados

es una relacin de equivalencia El subgrafo de G determinado por el conjunto de vrtices de una clase de equivalencia de C se llama

componente conexa.

10

Conexin II
G es conexo si posee slo una componente conexa. G es conexo u,vV existe un camino en G que conecta u con v. Las componentes conexas son grafos conexos Las componentes conexas de G son una particin de G (G = G1...Gn , GiGj= ij)

Conexin III
Un grafo simple y conexo con n vrtices tiene al menos n-1 arcos (n1)
Induccin completa en n
n=1 (trivial) n>1

Gl, lm

. . . .

G2 G1

11

Caminos Eulerianos y Hamiltonianos

Recorrer de un solo trazo sin levantar el lpiz del papel

Problema de los puentes de Knisberg (Euler, 1736)

A C B

A D B C D

Caminos Eulerianos
Si v es un vrtice de G, se llama grado de v , (v), al n de arcos incidentes en l (cada bucle suma 2) Si D es un digrafo:
el grado de entrada de v, E(v), es el n de arcos cuyo extremo final es v el grado de salida de v, S(v), es el n de arcos cuyo extremo inicial es v

Un Camino Euleriano en G es un camino simple que contiene todos los arcos de G.

12

Caminos Eulerianos (G no dirigido)

Sea G= (V, A, p) un grafo con A,
G no tiene vrtices aislados y posee un camino euleriano cerrado

G es conexo y todos sus vrtices son de grado par

0 9 j k 8 i 5 h m 7 l 6 n e 4 g f 3 a d c 2 1 b

Caminos Eulerianos II
0 9 j k 8 i 5 h m 7 l 6 n e 4 g f 3 a d c 2 1 b

G
9 k 8 m 7 l 6 n e 4 5 f 3 d c 2 1

G 3 G 2
h

G 1

0a1b2g5i8j90
C1 C5 C9

0 a 1c 2 f 4 e 3 d 1 b 2 g 5 h 5 i 8 j 9 m 6 n 7 l 8 k 9 0

13

Caminos Eulerianos III

Sea G= (V, A, p) un grafo sin vrtices aislados,
G posee un camino euleriano no cerrado

G es conexo y tiene dos vrtices de grado impar

b
1 2

c
9 10

e
4

a 1 b 0 i 11 c 10 h 5 f 9 b 2 c 3 e 4 f 6 g 7 h 8 i 12 a i 11 c 10 h 5 f 9 b 2 c 3 e 4 f 6 g 7 h 8 i 12 a 1 b

a
12

11

h
7

5 6

Caminos Hamiltonianos
Un camino hamiltoniano en un grafo G es un camino elemental que contiene todos los vrtices de G. Un digrafo D se dice completo si cada pareja de vrtices distintos estn unidos por, al menos, un arco.

14

Caminos Hamiltonianos (Digrafos)

Para cada digrafo completo existe un camino

hamiltoniano
Caso 1:

u1

u2 v

.....
ui+1

uk

u1

...
u1

ui v

...
ui+1 v

uk

Caso 2: i Caso 3:

...
ui v

ui

...
uk

uk

u1

...

ui+1

...

rboles
Un rbol es un grafo conexo y sin ciclos. Sea G un grafo. Son equivalentes:
1. 2. 3. 4. G es un rbol Cada par de vrtices distintos est conectado por uno y slo un camino simple G es conexo, pero si eliminamos un arco deja de serlo. G no tiene ciclos, pero si aadimos un arco se forma exactamente un ciclo.

15

rboles II
Todo rbol con ms de un vrtice posee, al menos, dos vrtices de grado 1.
Demostracin: por induccin completa en el n de vrtices

rboles III
Sea G un grafo con n 1 vrtices. Son equivalentes:
1. 2. 3. G es un rbol G no tiene ciclos y tiene n - 1 arcos. G es conexo y tiene n - 1 arcos.
(T22. Un grafo simple y conexo con n vrtices tiene al menos n-1 arcos )

16

rboles IV
Un rbol generador (spanning tree) de un grafo G=(V, A, p) es un rbol T=(V, A, p|A) con AA

Todo grafo conexo posee un rbol generador

rboles Dirigidos
Un vrtice r es la raz de un digrafo si todos los vrtices son accesibles desde l.

Un rbol con raz o dirigido es un digrafo que, si no es vaco, posee una raz y su grafo asociado es un rbol

17

rboles dirigidos II
Conceptos bsicos
Padre / hijo Ancestro / descendiente Grado de un vrtice = n de hijos Subrbol de raz u: subgrafo determinado por u y sus

descendientes

Nivel o profundidad de u: longitud del camino de la raz a u Altura o profundidad del rbol: mximo nivel de los nodos

rboles dirigidos III

Representacin grfica

rbol ordenado
11

1 12

2 31

3 32 323

321 322

18

rboles binarios
Un rbol binario es un conjunto de nodos:
vaco o formado por una raz, r, y dos subrboles binarios, TI y TD, subrbol izquierdo y subrbol derecho

No son una subclase de rboles ordenados A B A B

rboles binarios II
Representacin de expresiones algebraicas ((a - 6) * b ) / (c - a)

/ * a 6 b c a

19

rboles binarios III

El nmero de nodos del nivel i en un rbol binario es 2i El nmero de nodos n de un rbol binario de altura h verifica n 2h+1-1 La altura h de un rbol binario de n nodos verifica h log2(n+1) -1

rboles binarios IV
Un rbol binario es lleno si todos los nodos tienen 2 hijos no vacos excepto los del
ltimo nivel que son hojas

completo
cada nivel i, 0 i h-1, tiene 2i nodos los nodos del nivel h-1 con hijos estn a la izquierda no existen hijos nicos

homogneo si cada nodo tiene 0 o 2 hijos

20

Recorridos de rboles binarios

Sea T un rbol binario con raz R y subrboles izquierdo y derecho TI y TD. Podemos visitar todos sus nodos en: Preorden: R, TI en preorden y TD en preorden Inorden: TI en inorden, R y TD en inorden Postorden: TI en postorden, TD en postorden y R

1
Preorden: 1 2 4 8 9 5 3 6 7 0 Inorden: 8 4 9 2 5 1 6 3 7 0 Postorden: 8 9 4 5 2 6 0 7 3 1

2 4 8 9 5 6

3 7 0

Grafos Planos y Coloreados

G es plano si admite una representacin en la que los arcos no se cortan

Un grafo es n-coloreable si existe una funcin f: V {1, 2,.., n} tal que para todo par de vrtices adyacentes, u y v, f(u) f(v)

21

Coloreamiento
El n cromtico de G, kG, es el menor n de colores suficientes para colorear el grafo. Cotas de kG
1 kG |V| (si G conexo) Si el mximo grado de los vrtices de G es m entonces kG m+1
f(v) = 1 f(u) = min {z / z f(u) para todo u adyacente a u previamente coloreado}

Coloreamiento II
G es 2-coloreable s, y slo s, no tiene ciclos de longitud impar Un rbol es 2-coloreable

22

Planaridad
Consideremos una representacin grfica plana de un grafo plano y conexo G:
Regin (finitas e infinita) Contorno Regiones adyacentes
i

b 1 a h g e f 5 4 2 d

c
b 1 a h g e f 5 4 2 d

Planaridad II
Si un grafo plano y conexo tiene n vrtices, m arcos y r regiones, entonces: n - m + r = 2 (Frmula de Euler)
Demostracin: completar un rbol generador

Si G es un grafo simple, conexo, plano, sin bucles con n vrtices, m2 arcos y r regiones, entonces: 3/2 r m 3n - 6
Demostracin: para r>1, acotar la suma N de las longitudes de los contornos de las regiones finitas.

23

Planaridad III
Ejemplos de grafos no planos:

n=6 m=9 r=5 n=5 m=10 m > 3n - 6 Se verifican las desigualdades del corolario. Particularizando la demostracin para l: 4r 2m

24