1Teora de GrafosTeora de Grafos

IntroduccinIntroduccin

Grafos: modelos matemticos de situaciones realesEjemplos:

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)

2ndicendice

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

Conceptos bsicosConceptos 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)

3Representaciones de un grafoRepresentaciones de un grafo

Representacin grfica

a1

a2

a3

a4

a5

a6a7

a8

a1 a2a3 a4

v1

v2

v3

v5

v4

v1 v2 v3 v4 v5

a5

a6a7

a8

Conceptos bsicosConceptos 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

4Si 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 bsicosConceptos bsicos

Conceptos bsicosConceptos bsicos

G = (V, A, p) es subgrafo de G = (V,A,p) si:G es un grafoVV, A A y p= p|A

Subgrafo determinado por:AA, G(A) = (V, A, p|A) V extremos de los arcos de AVV, G(V) = (V, A, p|A) A arcos que unen nodos de VSubgrafo 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

5Representaciones de un grafoRepresentaciones de un grafoMatriz 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)

v1

v2 v3

v4

v5

a1a2

a3

a4

a6a5

=

0200021000000100010200020

)(GM

Accesibilidad y conexinAccesibilidad 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

6Accesibilidad y conexin IIAccesibilidad 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 Accesibilidad (D digrafodigrafo))

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 vMatriz de accesibilidad de orden k de D, Mk, es una

matriz booleana:

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

ijk

ij vdesdeaccesiblekesvm =1)(

7Accesibilidad IIAccesibilidad II

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

Mk = Mk (k 1) (potencia booleana)

Matriz de accesibilidad de D, M(D)

vi vj vi vr vjk

k-1

ijij vdesdeaccesibleesvm =1

Accesibilidad IIIAccesibilidad 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 w vj

8Accesibilidad IVAccesibilidad IV

M(D) = I M .... Mn-1 (n = |V|)

DigrafosDigrafos simples y relaciones (I)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 vRvv, ),()(,, vvapav = 1, = iiMiSimtrica vRuuRvvu ,,

==

),()(,),()(,

,uvbpb

vuapavu 11,, == jiij MMji

Antisimtrica RuvuRvvu ,

=

=),()(,

),()(,uvbpb

vuapavu 01, == jiij MMji

9DigrafosDigrafos simples y relaciones (II)simples y relaciones (II)

Propiedad transitiva de las relaciones binariasu,w,v uRw y wRv uRvu,v

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

Cierre transitivo de R, RT : la menor relacin transitiva que contiene a R

u v u v

Cierre transitivoCierre 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]

10

Cierre transitivo IICierre 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)Conexin (G no dirigido)

Dos vrtices u y v de G estn conectados en G siiexiste 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.

11

Conexin IIConexin 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 IIIConexin 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

v m....

Gl, lm

G2G1

12

Caminos Caminos EulerianosEulerianos y y HamiltonianosHamiltonianos

Recorrer de un solo trazo sin levantar el lpiz del papel

Problema de los puentes de Knisberg (Euler, 1736)

A

B

DC

A

B

C D

Caminos Caminos EulerianosEulerianos

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.

13

Caminos Caminos EulerianosEulerianos (G no dirigido)(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

9 7

8 6

3

2

1

4

5

a0

bcd

g

e

i

f

kl

jm

n

h

Caminos Caminos EulerianosEulerianos IIII

0 a 1 b 2 g 5 i 8 j 9 0

9 7

8 6

3

2

1

4

5

a0

bcd

g

e

i

f

kl

jm

n

h

9 7

8 6

3

2

1

4

5

c d

e f

kl

mn

h

G

G 1

G 2

G 3

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

14

Caminos Caminos EulerianosEulerianos IIIIIISea 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

a

b c e

h f

g

i

1

2 3

4

5

910

11

8

12

7 6

0

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

Caminos Caminos HamiltonianosHamiltonianos

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.

15

Caminos Caminos HamiltonianosHamiltonianos ((DigrafosDigrafos))

Para cada digrafo completo existe un camino hamiltoniano

Caso 1:

Caso 2: i

Caso 3:

u1 u2 uk

v

.....

u1 ui ui+1 uk... ...v

u1 ui ui+1 uk... ...v

u1 ui ui+1 uk... ...v

rbolesrboles

Un rbol es un grafo conexo y sin ciclos.

Sea G un grafo. Son equivalentes:1. G es un rbol2. Cada par de vrtices distintos est conectado por uno y

slo un camino simple3. G es conexo, pero si eliminamos un arco deja de serlo.4. G no tiene ciclos, pero si aadimos un arco se forma

exactamente un ciclo.

16

rboles IIrboles 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 IIIrboles III

Sea G un grafo con n 1 vrtices. Son equivalentes:

1. G es un rbol2. G no tiene ciclos y tiene n - 1 arcos.3. G es conexo y tiene n - 1 arcos.

(T22. Un grafo simple y conexo con n vrtices tiene al menos n-1 arcos )

17

rboles IVrboles 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 Dirigidosrboles 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

18

rboles dirigidos IIrboles 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 IIIrboles dirigidos III

Representacin grfica

rbol ordenado1 2 3

11 12 31 32

321 322 323

19

rboles binariosrboles 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 IIrboles binarios II

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

/

* -

- b

a 6

c a

20

rboles binarios IIIrboles 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 IVrboles 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

21

Recorridos de rboles binariosRecorridos 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

2 3

4 5

98

6 7

0

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

Grafos Planos y ColoreadosGrafos 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)

22

ColoreamientoColoreamiento

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) = 1f(u) = min {z / z f(u) para todo u adyacente a u previamente

coloreado}

ColoreamientoColoreamiento IIII

G es 2-coloreable s, y slo s, no tiene ciclos de longitud impar

Un rbol es 2-coloreable

23

PlanaridadPlanaridad

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

1 2

3

45

a

b c

hg

d

ef

i

1 2

3

45

a

b c

hg

d

ef

i

PlanaridadPlanaridad IIII

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 - 6Demostracin: para r>1, acotar la suma N de las longitudes de los

contornos de las regiones finitas.

24

PlanaridadPlanaridad IIIIII

Ejemplos de grafos no planos:

n=5 m=10

m > 3n - 6

n=6 m=9 r=5Se verifican las desigualdades del corolario. Particularizando la demostracin para l:

4r 2m