Grafos

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 18

Teora de grafos

Tema I: Introduccin Los puentes de Knigsberg.

Se puede dar un paseo pasando por todos los puentes una, y slo una, vez? Grafo: se puede dibujar sin levantar en lpiz del papel y sin repetir lneas? Desarrollo enorme en los ltimos 50 aos. Por qu?

Aplicaciones!!

En telecomunicaciones: circuitos, redes (ordenadores, comunicaciones) ...

Algunos de los problemas que trataremos:


1. Dados unos componentes c1 , . . . , ck con unas ciertas interconexiones, se puede realizar el circuito de manera plana?

2. Tenemos k ordenadores y los queremos conectar de la manera ms econmica posible MST.

3. Enrutado en redes: caminos mnimos.


B

4. Arquitecturas paralelas: dados k procesadores, los queremos interconectar de una manera adecuada.

Bibliografa:
K. Rosen: Matemtica Discreta y sus aplicaciones, Ed. McGrawHill, 2004.
3

Primeras deniciones
1. Un grafo es un par G = (V, E), donde V son los vrtices (o nodos) y E son las aristas (pares de vrtices). La arista entre los vrtices vi y vj la denotaremos {vi , vj }. Obs: ver un grafo de esta manera abstracta resulta muy til en la prctica. Se pueden dibujar de maneras distintas ...
4 5 3

10

15 8 7

5 1
8 0

9 4

11

0 14

15

12
10 14

11 12

13

13

14
10 8 9 4 6 13 1

12

13

15

10

11

12 0 2 14

15

11

2. Si en E no hay aristas repetidas, ni aristas de la forma {vi , vi } (lazos) diremos que el grafo es simple (en otro caso, diremos que G es un multigrafo). Si no se dice lo contrario, asumiremos que los grafos que aparecen son simples. 3. Se dice que G es un grafo dirigido (digrafo) si las aristas de G estn orientadas (de un vrtice origen a un vrtice destino). En este caso, las aristas {vi , vj } y {vj , vi } son distintas. Son necesarios en ciertas aplicaciones: programacin de tareas, diagramas de ujo.

c b b

Grafo simple

Multigrafo

Grafo dirigido

4. El grado de un vrtice es el nmero de aristas incidentes en l. El grado de v se denota (v).

Algunos grafos famosos


El grafo de la Web. 8 mil millones de pginas (segn Google) El grafo de Hollywood. Los vrtices son actores y las aristas
corresponden a pelculas en las que aparecen juntos. http://www.cs.virginia.edu/oracle/star_links.html Por ejemplo, cuntas pelculas hacen falta para conectar Bruce Lee con Santiago Segura?

 Santiago Segura was in Manolito Gafotas en Mola ser jefe!


(2001) with Marcela Walerstein

 Marcela Walerstein was in Emmanuelle Forever (1993) with


George Lazenby

 George Lazenby was in Last Days of Bruce Lee, The (1973)


with Bruce (I) Lee

Pasando a ejemplos ms serios ...


Grafo completo de n vrtices, Kn. Las aristas conectan todos
los pares de vrtices.

K3

K4

K5

Ciclo de n vrtices, Cn. V = {v1, v2, . . . , vn} E = {(v1, v2), (v2, v3), . . . , (vn1vn), (vn, v1)}

C3

C4

C5

Cubo n-dimensional , o n-cubo, denotado Qn V = {cadenas de n bits} |V | = 2n


Las aristas unen cadenas que dieren en 1 bit.
001 01 0 1 100 00 Q1 Q2 10 000 Q3 110 11 101 111

011

010

Un primer resultado:

Teorema 1 Sea G = (V, E) un grafo con e aristas. Entonces


(v) = 2e
vV

Una consecuencia directa: en cualquier grafo, hay un nmero par de vrtices de grado impar.

Tema II: Representacin de grafos. Isomorsmo.


Cmo se puede representar un grafo? 1 Matriz de adyacencia

V = {v1, v2, . . . , vn}


si (vi , vj ) G en otro caso

A Mn

aij =

1 0

G
0 1 A=1 0 0

2 3 5 4

1 0 1 1 0

1 1 0 0 0

0 1 0 0 1

0 0 0 1 0

Ventaja: sencilla de implementar. Inconveniente: GRAN tamao

Lista de adyacencias

V = {v1, v2, . . . , vn}

A cada vrtice vi se le asocia una lista con los vrtices adyacentes.


1

2 3 5 4

v1 v2 v3 v4 v5

{v2, v3} {v1, v3, v4} {v1, v2} {v2, v5} {v4}

Ventaja: tamao proporcional a |V | + |E|. Inconveniente: a primera vista, manejo menos evidente
Ambas estructuras son fcilmente adaptables al caso de grafos dirigidos y multigrafos.

10

Isomorsmo de grafos: Idea intuitiva. Dos grafos (simples)


G = (VG, EG) y H = (VH , EH ) son isomorfos si son el mismo
etiquetando adecuadamente los vrtices.

2 G
Formalmente:

b H

G y H son isomorfos si existe una biyeccin f : VG VH tal que {vi , vj } EG {f (vi ), f (vj )} EH Notacin: G H .
Es fcil pensar en muchas condiciones necesarias: 1. Igual nmero de vrtices y aristas 2. La secuencia de grados es la ordenacin creciente de los grados de los vrtices (v1 ), (v2 ), . . . , (vn ). Dos grafos isomorfos deben tener la misma sucesin de grados.

No es suciente ...
11

Algunas operaciones con grafos


Sea G = (V, E) un grafo. Se dice que G = (V , E ) es un subgrafo de G, y se escribe G G, si V V y E E (las aristas de E deben conectar vrtices de V .. Si V V , se llama subgrafo inducido por V al subgrafo cuyos vrtices son V y cuyas aristas son las aristas de G que unen vrtices de V .

subgrafo

subgrafo inducido grafo G

Si u es un vrtice de G, el grafo G u se obtiene al eliminar de G el vrtice u y todas las aristas incidentes a u.

grafo G

Gu

12

Tema III: Conexin


Sea G un grafo simple. Un recorrido de u a v es una sucesin de aristas {uu1, u1u2, u2u3, . . . , un1v}. (Pueden aparecer aristas y vrtices repetidos). Un camino es un recorrido en el que no hay aristas repetidas. Si no tiene vrtices repetidos, se dice que el camino es simple. Un ciclo es un camino simple cerrado (u = v ).

u v

u v

recorrido

camino

camino simple

ciclo

13

Un grafo G es conexo si para cualquier par de vrtices existe un recorrido que los conecta. (Si el grafo es dirigido, hay que tener en cuenta la orientacin de las aristas) La distancia d(u, v) entre dos vrtices u y v es la longitud del recorrido ms corto que los conecta.

Obs: d es una distancia Obs: El recorrido ms corto entre dos vrtices u y v es siempre un
camino (es decir, no repite vrtices).

Def: El grafo G = (V, E) es bipartido si existe una particin


V = V1 V2 (V1 V2 = ) tal que todas las aristas de G conectan vrtices de V1 con vrtices de V2 .
V1 V2

bipartido

es bipartido?

14

G es bipartido

Teorema 2 Sea G un grafo conexo.

Dem. inmediato. . Sea u vrtice de G. X = {x | d(u, x) impar}, Y = {y | d(u, y) par}.

G no contiene ciclos de longitud impar.


v P1 x u

P2

(X, Y ) es biparticin. Si no lo fuera, v, w en X (o en Y ), conectados. P1 el camino mnimo de u a v , P2 cam. min. de u a w. longitud de P1 P2 ?? Ojo: P1 P2 no tiene por qu ser un ciclo. Sea x el ltimo vrtice comn a P1 y P2 . Repetir argumento con los caminos de x a v, arista v,w, camino w,x.

Pregunta: cuntos caminos de longitud k hay entre dos vrtices


de un grafo?

gido) con vrtices V = {v1 , . . . , vn} y matriz de adyacencia A. El nmero de recorridos de longitud k entre los vrtices vi y vj es el coeciente (i, j) de la matriz Ak .

Teorema 3 Sea G un grafo (puede ser multigrafo o grafo diri-

15

Conectividad

conexo

ms conexo a

Se dice que un grafo G es k-conexo si al eliminar menos de k vrtices (y las aristas adyacentes) el grafo sigue siendo conexo (o queda reducido al vaco). Obs: en redes, se dice que una red es tolerante a fallos si, para todo par de vrtices u, v existen, al menos, dos caminos alternativos entre u y v . (Esto es claramente equivalente a que cualquier par de vrtices u, v est contenido en un ciclo.) Veamos que esto es equivalente a que el grafo sea 2-conexo (es decir, que siga siendo conexo si falla un solo vrtice). Se dice que dos caminos entre u y v son disjuntos si no tienen vrtices ni aristas en comn (excepto, claro, u y v ). (A veces se habla de internamente disjuntos).
16

menos, 3 vrtices. G es 2-conexo si y slo si dados dos vrtices distintos u, v V existen al menos dos caminos disjuntos que los conectan.

Teorema (Whitney). Sea G = (V, E) un grafo conexo con, al

Dem: (1) Si G no es 2-conexo, existe w t.q. G w no conexo. x, y no conectados en G w. Los caminos de x a y en G pasan por w. No hay dos caminos disjuntos de x e y . (2) Sabemos G 2-conexo. caminos disjuntos de x a y ?

x, y V . Induccin en d(x, y) (nmero de aristas)


Si d(x, y) = 1, e = {x, y}, G 2-conexo G e conexo camino en G e de x a y dos caminos disjuntos en G. Supongamos cierto si d(x, y) < k . Sean x, y vrtices a distancia k y consideremos un camino de x a y con k aristas. Sea w el vrtice anterior a y , e = {w, y}. Como d(x, w) < k , dos caminos disjuntos de x a w, P y Q. Como G es 2-conexo, existe un camino de x a y que no pasa por w, sea R dicho camino. Sea z el ltimo vrtice de R que est en P o en Q (si no hay ninguno, z = x). Sup. z P . a) Si y Q, caminos P (x z) + R(z y), e + Q b) Si y Q, caminos P (x z) + R(z y), Q(x y).

R P R x Q w e x Q z y P R z

R y e w Q

Obs: Dos vrtices u y v estn unidos por dos caminos disjuntos si y slo si estn contenidos en un ciclo. Por tanto, el teorema de Whitney se puede formular tambin de esta forma: menos, 3 vrtices. G es 2-conexo si y slo si dos vrtices distintos cualesquiera estn contenidos en un ciclo.
17

Teorema (Whitney). Sea G = (V, E) un grafo conexo con, al

Construccin de grafos 2-conexos: sntesis de Whitney


La operacin de sumar un camino al grafo G consiste en aadir un camino P entre dos vrtices de G tal que las aristas y los vrtices internos de P no estn en G. Una sntesis de Whitney de un grafo G a partir de un grafo H es una secuencia de grafos G0 , G1 , . . . , Gk , donde G0 = H , Gk = G y Gi se obtiene de Gi1 sumndole un camino simple.

Observacin: Si G se obtiene a partir de H mediante una sntesis


de Whitney y H es 2-conexo, entonces G es 2-conexo.

2-conexo

2-conexo

Teorema: Un grafo G es 2-conexo si y slo si es un ciclo o se puede


obtener a partir de un ciclo mediante una sntesis de Whitney. Ejemplo: obtener Q3 como una sntesis de Whitney de Q2 .

18

También podría gustarte