Grafos Dirigidos Datos PDF

Preview

Summary

Download Grafos Dirigidos Datos PDF

Description

Grado en Ciencias e Ingeniería de Datos, Curso 2019–2020

Matemática Discreta. Área de Álgebra Universidade da Coruña

Tema 4 Grafos

Recuerda que estas notas son, únicamente, parte del material de trabajo de los profesores de esta asignatura. Los contenidos de este tema se pueden ver en los siguientes libros: • K.H. Rosen, Matemática Discreta y sus aplicaciones: capítulos 8 y 9. • A. Vieites, F. Aguado, F. Gago, M. Ladra, G. Pérez, C. Vidal, Teoría de Grafos. Ejercicios resueltos y propuestos. Laboratorio con SAGE. Paraninfo 2014.

Para este tema, excepto el apartado de grafos dirigidos, se seguirán las siguientes secciones del libro Teoría de Grafos. Ejercicios resueltos y propuestos. Laboratorio con SAGE : Sección 1. Primeros conceptos (todo), Sección 2. Conectividad (todo), Sección 3. Grafos eulerianos y grafos hamiltonianos (todo, excepto la proposición 3 de la página 38), Sección 4. Grafos ponderados: solo las definiciones 16 y 17, Sección 7. Árboles (todo, excepto la sección 7.1).

4.1 4.1.1

Grafos Dirigidos Conceptos básicos

Definición 1. Un digrafo o grafo dirigido es un par G = (V, E), donde V es un conjunto finito no vacío cuyos elementos se llaman vértices o nodos y E es un conjunto cuyos elementos 83

84

TEMA 4. GRAFOS

se llaman aristas (dirigidas u orientadas). Las aristas son “pares ordenados” de vértices de V , es decir una arista e = (u, v) ∈ E es un elemento del producto cartesiano V × V Consideremos, por ejemplo, el siguiente digrafo G:

Matemática Discreta. Área de Álgebra Universidade da Coruña

v2 oi

vO1

v4

+v 3

Claramente G tiene como conjunto de vértices V = {v1 , v2 , v3 , v4 }, y como conjunto de aristas   E = (v1 , v2 ), (v2 , v3 ), (v3 , v1 ), (v3 , v2 ) . Si una arista une un vértice consigo mismo, recibe el nombre de lazo. Un vértice no conectado a ningún otro vértice se llama vértice aislado (por ejemplo v4 ). Ejemplo 1. La red1 de internet se puede pensar como un grafo dirigido, donde los vértices son las páginas web, y las aristas enlaces entre ellas. v1 `

/ v2

/ v3 O

vO4

v5

/ v6

v7

v9

Ejemplo 2. En el estudio del comportamiento humano es interesante conocer el grado de influencia que unas personas ejercen sobre otras. Se puede utilizar un grafo dirigido llamado grafo de influencia para modelar este comportamiento. Cada persona del grupo se representa por un vértice y, si la persona A ejerce influencia sobre la persona B, tendremos una arista (A, B). Aoc

E {

Fo

BZ {

Ct

/Go/w o

D D H

Reunimos ahora algunas definiciones básicas. Dado un digrafo G = (V, E) llamamos grafo no dirigido subyacente a G al grafo U (G) = (V, E ′ ) donde E ′ = {{u, v } | (u, v ) ∈ E o (v, u) ∈ E}. Dos digrafos distintos pueden tener el mismo grafo no dirigido subyacente. 1 En la literatura, la palabra red suele utilizarse para sistemas reales, mientras que el término grafo se usa para la representación matemática de la red.

85

4.1. GRAFOS DIRIGIDOS

Matemática Discreta. Área de Álgebra Universidade da Coruña

Ejemplo 3.

v1

/v2

vO 1

v1

/v2

v2

v3

v3

v3

G

H

U (G) = U (H)

Definición 2. i) Dada una arista e = (u, v), se dice que u es adyacente hacia v o que v es adyacente desde u. También se dice que u es el vértice inicial y v es el vértice final de e. ii) El grado de entrada de un vértice v, que se denota por ∂e (v), es el número de aristas con v como vértice final y el grado de salida de un vértice v, que se denota por ∂s (v), es el número de aristas con v como vértice inicial. Por lo tanto: ∂e (v) =| {(u, v ) | (u, v ) ∈ E} | y ∂s (v) =| {(v, u) | (v, u) ∈ E} | Lema 1. La suma de los grados de entrada de todos los vértices de un digrafo G = (V, E) es igual a la suma de los grados de salida de todos los vértices e igual al número de aristas. Σ ∂e (v) = Σ ∂s (v) = | E |

v∈V

4.1.2

v∈V

Matriz de adyacencia de un digrafo

Una forma de representar un digrafo es utilizando matrices. Definición 3. Sea G = (V, E) un digrafo con V = {v1 , . . . , vn }. La matriz de adyacencia de G es la matriz A = (aij ) cuadrada de orden n cuyo elemento aij (para i, j = 1, . . . , n) es el número de aristas que tienen a vi como vértice inicial y a vj como vértice final. Ejemplo 4. Matriz de adyacencia de un digrafo:

v1_ v

v1

/ v2T

v( J 5 v! 3

1v4

v1 v2 origen→ v3 v4 v5



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

v2

v3

v4

v5

1 0 0 0 1

1 1 1 0 0

0 0 1 0 0

 1 0  0  1 0

← destino

86

TEMA 4. GRAFOS La matriz de adyacencia no es necesariamente simétrica. La matriz de adyacencia permite

conocer fácilmente el grado de salida, respectivamente de entrada, de un vértice vi , sumando, los elementos de la fila, respectivamente de la columna, i de A: ∂e (vi ) =

n X

aij y ∂s (vi ) =

Matemática Discreta. Área de Álgebra Universidade da Coruña

j=1

n X

aji

j=1

El problema principal de las matrices de adyacencia es que suelen ser muy dispersas (muchos de sus elementos son nulos) y esto gasta mucha memoria innecesariamente. Por ello, se puede utilizar otra representación del grafo mediante listas de adyacencias, donde el primer elemento de cada entrada indica un vértice, y los vértices a los cuales puede acceder (mediante una única arista dirigida) se señalan después de los dos puntos. Puede observarse en el siguiente grafo: vK 2 m v1Z

Lista de adyacencias 1: 2: 3, 4 3: 2, 4 4: 5 5: 1, 2

- v3 # 

v4

v5 q

4.1.3

Caminos y ciclos

Definición 4. Sea G = (V, E) un digrafo, i) Un camino o trayectoria de un vértice v a un vértice w es una secuencia de aristas (no necesariamente distintas) de G de la forma e1 = (v0 , v1 ), e2 = (v1 , v2 ), . . . , en = (vn−1 , vn ), con v0 = v y vn = w. El vértice v0 se llama vértice inicial y vn se llama el vértice final del camino; el número de aristas, n, recibe el nombre de longitud del camino. Nótese que, a diferencia de los grafos (no dirigidos), puede existir un camino de un vértice v a un vértice w y, sin embargo, no existir camino de w a v : v +u

ws ii) Un camino en el que todos los vértices son distintos (excepto posiblemente vn = v0 ) se llama simple. iii) Un camino en el que vn = v0 se llama circuito o camino cerrado. iv) Un camino simple y cerrado, conteniendo al menos una arista, recibe el nombre de ciclo. Por ejemplo, un lazo es un ciclo de longitud 1.

87

4.1. GRAFOS DIRIGIDOS v) Un camino de longitud cero consiste en un único vértice.

Matemática Discreta. Área de Álgebra Universidade da Coruña

Teorema 1. Sea G = (V, E) un digrafo, A su matriz de adyacencia con respecto a la ordenación v1 , v2 , . . . , vn y k un entero positivo. El número de caminos (dirigidos) de longitud k desde vi hasta vj es igual al elemento de la posición (i, j) de la matriz Ak . Ejemplo 5. La comisión de recursos humanos de una empresa está estudiando la relación de dominio o influencia en un grupo de trabajo de 5 personas: Antía, Brais, Catuxa, Duarte y Estevo. Mediante entrevistas personales, consigue establecer quién domina a quién por parejas. Empleando los datos que obtiene, elabora el siguiente grafo dirigido donde cada vértice representa a una persona y una flecha, por ejemplo, la de A a B significa que Antía domina a Brais. DW w

EX n

A B C D E

&

7C

& 



( A

/ B

A 0 0  0  1 1

B 1 0 1 0 1

C 1 0 0 1 0

D 0 1 0 0 0

E 1 0  1  1 0

3 1 2 3 2

Para ver quién es el líder del grupo se suman los elementos de cada fila de la matriz de adyacencia (o grado de salida del vértice correspondiente). Con esto se obtiene a cuántos compañeros domina cada persona. Se obteniene que: Antía domina a 3 personas, Brais a 1, Catuxa a 2, Duarte a 3 y, finalmente, Estevo domina a 2 personas. Tanto Antía como Duarte dominan a 3 personas. Este empate hace que no sea posible decidir cuál es el líder del grupo. Si M es la matriz de adyacencia del grafo, M 2 indica el número de caminos de longitud 2 para ir de un vértice a otro. En el ejemplo que estamos considerando, esto indica los dominios “de segundo orden”, es decir, la cantidad de personas que son dominadas por personas que domina cierta persona. Por ejemplo, si Duarte domina a Catuxa y esta domina a Brais, tiene sentido pensar que Duarte puede ejercer algún tipo de influencia sobre Brais. Finalmente, la matriz M + M 2 representa la cantidad de dominios de primer o segundo orden que ejerce cada persona sobre las personas del grupo. Sumando los elementos de cada fila de esta matriz (excepto el elemento de la diagonal, que representa la influencia de una persona sobre sí misma), podemos señalar a Duarte como líder del grupo.  0 0  M + M2 =  0 1 1

4.1.4

1 0 1 0 1

1 0 0 1 0

0 1 0 0 0

 1 0  1 + 1 0



1 1  1  1 0

2 0 1 3 1

0 1 0 1 1

1 0 1 0 1

  1 1   1  1  0  = 1  2 2 1 1

3 0 2 3 2

1 1 0 2 1

1 1 1 0 1

 2 8−1 1 4  1 5   3 10 1 6−1

Conexión

Definición 5. Se dice que un digrafo G = (V, E) es fuertemente conexo si, para cada par de vértices u, v distintos de V , existe un camino con vértice inicial u y vértice final v y otro camino con con vértice inicial v y vértice final u.

88

TEMA 4. GRAFOS

Se define una relación binaria en V como sigue: u ∼ v si y sólo si u = v o existe un camino de u a v y un camino de v a u. ∼ es una relación de equivalencia. Si llamamos {V1 , V2 , . . . , Vr } a la partición del conjunto de vértices en las clases de equivalencia para esta relación, para cada i = 1, . . . , r, podemos formar subgrafos Gi = (Vi , Ei ), donde

Matemática Discreta. Área de Álgebra Universidade da Coruña

Ei = {(v, u) ∈ E | v, u ∈ Vi } es decir, Ei está formado por todas aquellas aristas de G que unen los vértices de Vi . Estos digrafos Gi reciben el nombre de componentes fuertemente conexas de G. Obviamente, un digrafo G es fuertemente conexo si, y sólo si, tiene una única componente fuertemente conexa. Definición 6. Se dice que un digrafo G = (V, E) es unilateralmente conexo si, para cada par de vértices u, v distintos de V , existe un camino con vértice inicial u y vértice final v o un camino con vértice inicial v y vértice final u. Definición 7. Se dice que un digrafo G = (V, E) es débilmente conexo su grafo subyacente U (G) es conexo.

v1Z

v1Z

vJ 5 v3

v3 2

3v 2

3v2T

v1Z

vJ 5

1v 4

1v 4

v3

vJ 5 v3

Grafo unilateralmente conexo no fuertemente conexo Lema 2. Sea G = (V, E) un digrafo. Grafo fuertemente conexo

v1 4

Grafo débilmente conexo no unilateralmente conexo

i) Si G es un digrafo fuertemente conexo, G es unilateralmente conexo ii) Si G es un digrafo unilateralmente conexo, G es débilmente conexo Ejemplo 6. El grafo no dirigido subyacente al grafo de la red no es conexo y tiene una componente conexa que incluye al 94% de las páginas web existentes. El subgrafo del grafo dirigido original que se corresponde con esta componente conexa tiene una componente fuertemente conexa muy grande y muchas otras pequeñas. A la primera se la denomina componente fuertemente conexa gigantesca o GSCC (giant strongly connected component). En el año 2012 tenía más de 51 millones de vértices. Desde cualquier página de esta componente se puede acceder a cualquier otra página de la misma componente. Supongamos que el grafo de la red fuese el siguiente: vO 0

vO 1

/ v2

v5

/ v6 ~

v7 o

~

/ > v3

v4

v8

v9

89

4.1. GRAFOS DIRIGIDOS El grafo no dirigido subyacente U (G) sería: v0

v1

v2

v3

v4

v5

v6

v7

v8

v9

Matemática Discreta. Área de Álgebra Universidade da Coruña

El grafo U (G) no es conexo. Tiene dos componentes conexas: {v0 , v1 , v2 , v3 , v5 , v6 , v7 , v8 } y {v4 , v9 }. El subgrafo de G dirigido correspondiente a la componente {v0 , v1 , v2 , v3 , v5 , v6 , v7 , v8 } es: vO 0

vO 1

/ v2

/ > v3

v5

/ v6 ~

v7 o

~

v8

Tiene cinco componentes fuertemente conexas: {v1 , v2 , v6 } (GSCC), {v3 , v7 }, {v8 }, {v0 } y {v5 }. Los vértices de G que no están en GSCC pueden ser: i) Nodos IN: páginas desde las que se puede acceder a la GSCC, pero no se puede acceder a ellas desde la GSCC (hacia GSCC pero no desde GSCC): {v5 } ii) Nodos OUT: páginas a las que se puede acceder desde la GSCC, pero desde ellas no se puede acceder a la GSCC (desde GSCC pero no hacia GSCC): {v3 , v7 } iii) Nodos ZARCILLO: páginas accesibles desde algún nodo IN pero desde las que no se accede a la GSCC o páginas que pueden acceder a nodos OUT pero no son accesibles desde la GSCC: {v0 , v8 } iv) Nodos DECONECTADOS: páginas que pertenecen a diferente componente conexa que los nodos de GSCC: {v4 , v9 }

4.1.5

Digrafos eulerianos y hamiltonianos

Definición 8. En un digrafo G, llamamos camino euleriano a un camino que contiene todas las aristas del grafo, apareciendo cada arista exactamente una vez. Llamamos circuito euleriano a un camino euleriano cerrado. Definición 9. Un digrafo euleriano es un digrafo que admite un circuito euleriano. Un digrafo semieuleriano es un grafo que admite un camino euleriano no cerrado. Teorema 2. Un digrafo débilmente conexo G = (V, E) es euleriano si, y sólo si, para todo vértice v de G, ∂s v = ∂e v. Proposición 1. Un digrafo débilmente conexo G = (V, E) es semieuleriano si, y sólo si, existen dos vértices u y v tales que: • ∂e (w) = ∂s (w) para todo vértice w 6= u, v

90

TEMA 4. GRAFOS • ∂e (v) = ∂s (v) + 1 y ∂s (u) = ∂e (u) + 1.

Matemática Discreta. Área de Álgebra Universidade da Coruña

Ejemplo 7.

• El siguiente digrafo es semieuleriano vO 1

/ v2

v3 o

v4

El camino (v1 , v2 ), (v2 , v4 ), (v4 , v3 ), (v3 , v1 ), (v1 , v4 ) es un camino euleriano • El siguiente digrafo es euleriano vO 1 `

/ v2

v3 o

v4

El camino (v1 , v2 ), (v2 , v4 ), (v4 , v3 ), (v3 , v1 ), (v1 , v4 ), (v4 , v1 ) es un circuito euleriano

4.1.6

Orientación de grafos

Definición 10. Dado un grafo (no dirigido) G = (V, E), una orientación de G es un digrafo O(G) = (V, E ′ ), con los mismos vértices de G y, donde para cada {u, v} ∈ E, se tiene que (u, v) ∈ E ′ o (v, u) ∈ E ′ , pero no ambas cosas a la vez. Definición 11. Un grafo G = (V, E) es conexa.

orientable si admite una orientación fuertemente

Teorema 3. (Teorema de Robin). Un grafo G = (V, E) es orientable si, y sólo si, G es conexo y no tiene aristas puente. El algoritmo de Hopcroft y Tarjan indica cómo hallar una orientación de un grafo orientable: • Se comienza con un vértice cualquiera, al que se le asigna la etiqueta 1. • Se considera el vértice vi con la mayor etiqueta t y tal que vi que tenga un vértice adyacente vj aún sin etiquetar. Se orienta la arista e = {vi , vj } del vértice vi hacia el vértice vj . • Cuando todos los vértices estén etiquetados, se orientan las aristas restantes siempre desde el vértice con etiqueta superior al vértice con etiqueta inferior. Ejemplo 8. Supongamos que el siguiente grafo representa el callejero de una ciudad, ¿cómo orientar las calles con sentido único, de modo que se siga pudiendo ir de cada punto a cualquier otro punto? Aplicamos el algoritmo de Hopcroft y Tarjan: se parte de un vértice cualquiera, que se etiqueta con 1, se elige un vértice adyacente a este y se etiqueta con 2, se orienta la arista como (1, 2). Se sigue el proceso, etiquetando vértices y orientando aristas hasta llegar al vértice 5.

91

4.1. GRAFOS DIRIGIDOS •

•

•

2 •o

1 •

•

•

•

•

3•

•

•

4•

•

Matemática Discreta. Área de Álgebra Universidade da Coruña

•

{

•

•

5

#•

•

•

Como el vértice 5 no es adyacente a un vértice sin etiquetar, se retrocede por el camino seguido hasta llegar a un vértie etiquetado y que sea adyacente a algún vértice sin etiquetar y se realiza el proceso anterior (las veces que sea necesario):

4•

2 •o

1 •

•

3•

/• 4

/• 5 /

{

4• #

5•

• 6

1 •

•O 6

3•

/• 4

•/ 5 /

{ #

2• 7



2 •o

5•

• 6

•2 7

Una vez etiquetados todos los vértices, se orientan las aristas aún no orientadas, desde el vértice con etiqueta superior al de etiqueta inferior:

4•

1

2 •o

; •O co

•O 6

3 •O

/• 4

/ •O 5

{

5

#•

• 6

2• 7

/...