• Author / Uploaded
• rsgalean

Citation preview

Teoría de grafos Tema I: Introducción Los puentes de Königsberg.

A

B

D

C

¾Se puede dar un paseo pasando por todos los puentes una, y sólo una, vez? Grafo: ¾se puede dibujar sin levantar en lápiz del papel y sin repetir líneas? Desarrollo enorme en los últimos 50 años. ¾Por qué?

Aplicaciones!!

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

1

Algunos de los problemas que trataremos: 1. Dados unos componentes c1 , . . . , ck con unas ciertas interconexiones, ¾se puede realizar el circuito de manera plana?

1

2

3

1

2

3

A

B

C

A

B

C

2. Tenemos k ordenadores y los queremos conectar de la manera más económica posible → MST.

2

3. Enrutado en redes: caminos mínimos. B

A

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

Bibliografía: K. Rosen: Matemática Discreta y sus aplicaciones, Ed. McGrawHill, 2004. 3

Primeras deniciones 1. Un grafo es un par G = (V, E), donde V son los vértices (o nodos) y E son las aristas (pares de vértices). La arista entre los vértices vi y vj la denotaremos {vi , vj }. Obs: ver un grafo de esta manera abstracta resulta muy útil en la práctica. Se pueden dibujar de maneras distintas ... 10

4 3

5

15

2

6

8 7 1

7

5

9 4

1 0

8

11

0 14

15

9

12

2

3

14

10

13

11 12

6

13

0

14 10

8

12

9

4

3

4 6

13

9

6

1

8

3

7

11

15

13

10

2

1

5

15

12 0 2

7

14

5

11

4

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 están orientadas (de un vértice origen a un vértice destino). En este caso, las aristas {vi , vj } y {vj , vi } son distintas. Son necesarios en ciertas aplicaciones: programación de tareas, diagramas de ujo.

c b

v

Grafo simple

b

a

a

Multigrafo

Grafo dirigido

4. El grado de un vértice es el número de aristas incidentes en él. El grado de v se denota δ(v).

5

Algunos grafos famosos • El grafo de la Web. 8 mil millones de páginas (según Google) • El grafo de Hollywood. Los vértices son actores y las aristas corresponden a películas en las que aparecen juntos. http://www.cs.virginia.edu/oracle/star_links.html Por ejemplo, ¾cuántas películas 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

6

Pasando a ejemplos más serios ... • Grafo completo de n vértices, Kn. Las aristas conectan todos los pares de vértices.

K3

K4

K5

• Ciclo de n vértices, Cn. V = {v1, v2, . . . , vn} E = {(v1, v2), (v2, v3), . . . , (vn−1vn), (vn, v1)}

C3

C4

7

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

011

11

01

101

111

1

0

100 00

110

10

010

000 Q1

Q2

Q3

Un primer resultado:

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

δ(v) = 2e

v∈V

Una consecuencia directa: en cualquier grafo, hay un número par de vértices de grado impar.

8

Tema II: Representación de grafos. Isomorsmo. ¾Cómo se puede representar un grafo? 1

Matriz de adyacencia

A ∈ Mn

aij =

( 1

0

V = {v1, v2, . . . , vn} si (vi , vj ) ∈ G en otro caso

1

G 

 0    1   A=  1    0   0

2 3 5 4

Ventaja: sencilla de implementar. Inconveniente: GRAN tamaño

9

1 0 1 1 0

1 1 0 0 0

0 1 0 0 1



0   0   0    1   0

2

Lista de adyacencias

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

A cada vértice vi se le asocia una lista con los vértices adyacentes. 1

G

v1 v2 v3 v4 v5

2 3 5

→ → → → →

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

4

Ventaja: tamaño proporcional a |V | + |E|. Inconveniente: a primera vista, manejo menos evidente Ambas estructuras son fácilmente 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 vértices.

1

4

2

3

a

d

b

c H

G Formalmente:

G y H son isomorfos si existe una biyección f : VG → VH tal que {vi , vj } ∈ EG ⇐⇒ {f (vi ), f (vj )} ∈ EH Notación: G ≈ H . Es fácil pensar en muchas condiciones necesarias: 1. Igual número de vértices y aristas 2. La secuencia de grados es la ordenación creciente de los grados de los vértices δ(v1 ), δ(v2 ), . . . , δ(vn ). Dos grafos isomorfos deben tener la misma sucesión de grados.

No es suficiente ... 11

Algunas operaciones con grafos Sea G = (V, E) un grafo. Se dice que G0 = (V 0 , E 0 ) es un subgrafo de G, y se escribe G0 ⊂ G, si V 0 ⊂ V y E 0 ⊂ E (las aristas de E 0 deben conectar vértices de V 0 .. Si V 0 ⊂ V , se llama subgrafo inducido por V 0 al subgrafo cuyos vértices son V 0 y cuyas aristas son las aristas de G que unen vértices de V 0 .

subgrafo

subgrafo inducido grafo G

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

u

G−u

grafo G

12

Tema III: Conexión Sea G un grafo simple. Un recorrido de u a v es una sucesión de aristas {uu1, u1u2, u2u3, . . . , un−1v}. (Pueden aparecer aristas y vértices repetidos). Un camino es un recorrido en el que no hay aristas repetidas. Si no tiene vértices repetidos, se dice que el camino es simple. Un ciclo es un camino simple cerrado (u = v ).

u

u

v

v

camino

recorrido

u

v

u

camino simple

ciclo

13

Un grafo G es conexo si para cualquier par de vértices existe un recorrido que los conecta. (Si el grafo es dirigido, hay que tener en cuenta la orientación de las aristas) La distancia d(u, v) entre dos vértices u y v es la longitud del recorrido más corto que los conecta.

Obs: d es una distancia Obs: El recorrido más corto entre dos vértices u y v es siempre un camino (es decir, no repite vértices).

Def: El grafo G = (V, E) es bipartido si existe una partición V = V1 ∪ V2 (V1 ∩ V2 = ∅) tal que todas las aristas de G conectan vértices de V1 con vértices de V2 . V1 V2

bipartido

¿es bipartido?

14

Teorema 2 Sea G un grafo conexo.

G es bipartido

⇔

G no contiene ciclos de longitud impar. v P1

Dem. ⇒ inmediato. ⇐. Sea u vértice de G. X = {x | d(u, x) impar}, Y = {y | d(u, y) par}.

x u

P2

w

(X, Y ) es bipartición. Si no lo fuera, v, w en X (o en Y ), conectados. P1 el camino mínimo 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 vértice común a P1 y P2 . Repetir argumento con los caminos de x a v, arista v,w, camino w,x.

Pregunta: ¾cuántos caminos de longitud k hay entre dos vértices de un grafo?

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

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

15

Conectividad

conexo

“m´as conexo”

Se dice que un grafo G es k-conexo si al eliminar menos de k vértices (y las aristas adyacentes) el grafo sigue siendo conexo (o queda reducido al vacío). Obs: en redes, se dice que una red es tolerante a fallos si, para todo par de vértices u, v existen, al menos, dos caminos alternativos entre u y v . (Esto es claramente equivalente a que cualquier par de vértices 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 vértice). Se dice que dos caminos entre u y v son disjuntos si no tienen vértices ni aristas en común (excepto, claro, u y v ). (A veces se habla de internamente disjuntos). 16

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

menos, 3 vértices. G es 2-conexo si y sólo si dados dos vértices distintos u, v ∈ V existen al menos dos caminos disjuntos que los conectan.

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 . Inducción en d(x, y) (número 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 vértices a distancia k y consideremos un camino de x a y con k aristas. Sea w el vértice 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 vértice de R que está en P o en Q (si no hay ninguno, z = x). Sup. z ∈ P . a) Si y 6∈ 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 y

z

P

R

y

z R

e

x

e

x Q

Q

Q w

w

Obs: Dos vértices u y v están unidos por dos caminos disjuntos si y sólo si están contenidos en un ciclo. Por tanto, el teorema de Whitney se puede formular también de esta forma:

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

menos, 3 vértices. G es 2-conexo si y sólo si dos vértices distintos cualesquiera están contenidos en un ciclo. 17

Construcción de grafos 2-conexos: síntesis de Whitney La operación de sumar un camino al grafo G consiste en añadir un camino P entre dos vértices de G tal que las aristas y los vértices internos de P no están en G. Una síntesis 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 Gi−1 sumándole un camino simple.

Observación: Si G se obtiene a partir de H mediante una síntesis 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 sólo si es un ciclo o se puede obtener a partir de un ciclo mediante una síntesis de Whitney. Ejemplo: obtener Q3 como una síntesis de Whitney de Q2 .

18