Lectura fundamental 8 - Estructura de datos PDF

Preview

Summary

Estructura de datos...

Description

Grafos

Contenido 1

Definición

2

Conceptos básicos

3

Representación

4

Implementación de grafos dirigidos con listas de sucesores

Palabras clave:grafo, nodo, arco, grado, c

Grafos 1 1. Definición Un grafo G = < V, E> es una estructura de datos conformada por: 1. Un conjunto V de nodos. 2. Un conjunto E de arcos, que conectan nodos entre sí. El conjunto E debe ser subconjunto de VxV.

Figura 1. Ejemplo de un grafo que contiene 6 nodos y 13 arcos Fuente: Sotelo (s.f.)

A los nodos también se les llama vértices y a los arcos también se les llama aristas o enlaces. El producto cartesiano V x V={ | a ∈ V y b ∈ V}, visto como el conjunto de todas las parejas de la forma donde ambas componentes son valores de tipo , representa todos los posibles arcos en un grafo cuyo conjunto de nodos es V . Formalmente, dado un grafo G=:

•

Un nodo es un elemento del conjunto V.

•

Un arco es una pareja ∈ x V donde es a el nodo origen y b es el nodo destino.

•

El conjunto de arcos E es un subconjunto de V * V , es decir V, es un conjunto conformado por parejas de la forma donde a y b son valores de tipo V.

1 Este texto es una adaptación del material preparado para el mismo módulo por Alejandro Sotelo Arévalo para la Institución Universitaria Politécnico Grancolombiano (Sotelo, s.f.).

POLITÉCNICO GRANCOLOMBIANO

2

La tabla 1 muestra algunas notaciones gráficas para representar los arcos:

Tabla 1. Notación gráfica de los arcos

Notación formal 〈A, B 〉 ∈ E

Notación compacta

Descripción

A� B

Hay arco del nodo A al nodo B, pero no hay arco del nodo B al nodo A.

A- B

Hay arco del noso A al nodo B, y también hay arco del nodo B al nodo A.

A- B

Hay arco del noso A al nodo B, y también hay arco del nodo B al nodo A.

A� B

Hay arco del nodo A al nodo A, ed decir, del nodo A a sí mismo.

〈A, B 〉 ∈ E y 〈B, A 〉 ∈ E 〈A, B 〉 ∈ E y 〈B, A 〉 ∈ E 〈A, B 〉 ∈ E

Notación gráfica

Fuente: Sotelo (s.f.)

Adicionalmente, los arcos de un grafo se pueden etiquetar con costos a través de una función de costos f: E R, que dado un arco del conjunto E da como resultado el costo de ir del nodo al nodo . La tabla 2 ejemplifica algunos grafos cuyos arcos tienen asociado un costo:

POLITÉCNICO GRANCOLOMBIANO

3

Tabla 2. Ejemplos de grafos con arcos que asocian costos

Fuente: Sotelo (s.f.)

Nótese que el conjunto de arcos de un grafo puede ser vacío. A lo largo del desarrollo de este documento, se representará el número de nodos con la variable n y el número de arcos con la variable e. Las definiciones introducidas en esta lectura podrían diferir un poco respecto a otros textos, pues no hay consenso estándar sobre estas.

2. Conceptos básicos 2.1. Grafos dirigidos y grafos no dirigidos Un grafo G= es un grafo no dirigido si y solo si para todo par de nodos a y b tales que haya un arco desde hacia b, se cumple que también hay un arco desde b hacia a . Un grafo G= es un grafo dirigido si y solo si existe un par de nodos a y b tales que hay un arco desde a hacia b pero no existe un arco b desde a hacia.

POLITÉCNICO GRANCOLOMBIANO

4

En otras palabras, un grafo no dirigido es un grafo donde todos sus arcos se pueden visitar en ambos sentidos, y un grafo dirigido es un grafo donde uno de sus arcos puede recorrerse en una dirección, pero no en la otra. La tabla 3 presenta varios ejemplos de grafos clasificándolos en dirigidos y no dirigidos y proporcionando el número de nodos y arcos para cada uno:

Tabla 3. Ejemplos de grafos y su clasificación en dirigido o no dirigido

Fuente: Sotelo (s.f.)

2.2. Sucesores y antecesores Un nodo a es sucesor de un nodo b si y solo si existe un arco que va desde b hacia a. Un nodo a es antecesor de un nodo b si y solo si existe un arco que va desde a hacia b. Un nodo a es adyacente a un nodo b si y solo si a es sucesor y/o antecesor de b.

Observe lo siguiente:

•

Un nodo a es antecesor de un nodo b si y solo si b es sucesor de a.

•

Para todo arco se cumple que su origen es antecesor de su destino y que su destino es sucesor de su origen.

•

Para todo nodo de un grafo no dirigido se cumple que sus antecesores, que sus sucesores y que sus adyacentes son los mismos.

POLITÉCNICO GRANCOLOMBIANO

5

•

Dos nodos son adyacentes si y solo si uno de los dos es sucesor del otro, es decir, si y solo si hay un arco que va del uno al otro.

La figura 2, muestra el ejemplo de un grafo y las relaciones entre sus nodos: Nodo

Sucesores

Antecesores

Adyacentes

A

〈C, D, E, F 〉

〈C, E 〉

〈C, D, E, F〉

B

〈B, F〉

〈B, D〉

〈B, D, F〉

C

〈A〉

〈A〉

〈A〉

D

〈B, D, F〉

〈A, D, F〉

〈A, B, D, F〉

E

〈A, F〉

〈A〉

〈A, F〉

F

〈D〉

〈A, B, D, E〉

〈A, B, D, E〉

Figura 2. Ejemplo de un grafo y las relaciones entre nodos Fuente: Sotelo (s.f.)

2.3. Fuentes, sumideros y nodos aislados Un nodo es una fuente si y solo si no tiene antecesores. Un nodo es un sumidero si y solo si no tiene sucesores. Un nodo es un nodo aislado si y solo si no tiene antecesores ni sucesores. Un nodo que sea fuente y sumidero a la vez es considerado un nodo aislado. Ejemplos de estos conceptos se presentan en la figura 3: Fuentes

〈A, F, G〉

Sumideros

〈E, F, G〉

Nodos aislados

〈F, G〉

Figura 3. Ejemplo de un grafo y la clasificación de sus nodos Fuente: Sotelo (s.f.)

POLITÉCNICO GRANCOLOMBIANO

6

2.4. Grado de un nodo El grado de salida de un nodo es la cantidad de sucesores que tiene. El grado de entrada de un nodo es la cantidad de antecesores que tiene. En un grafo no dirigido, el grado de un nodo es la cantidad de sucesores que tiene (los antecesores serían los mismos sucesores en un grafo no dirigido). La figura 4 ilustra un grafo e indica los grados de entrada y salida para cada uno de sus nodos: Nodo

Grado de salida

Grado de entrada

A

4

2

B

2

2

C

1

1

D

3

3

E

2

1

F

1

4

Figura 4. Ejemplo de un grafo y los grados de sus nodos Fuente: Sotelo (s.f.)

Con esta nueva terminología, es posible definir una fuente como un nodo con grado de entrada cero, un sumidero como un nodo con grado de salida cero y un nodo aislado como un nodo con grado de entrada cero y con grado de salida cero.

2.5. Grafos completos, grafos densos y grafos dispersos Dado un grafo G= donde la variable n representa el número de nodos y la variable representa el número de arcos, se debe cumplir que 0 ≤ e ≤ n 2. Esto porque un grafo podría no tener arcos (e=0) o podría llegar a tener la máxima cantidad posible de arcos (e=n2), lo que ocurre cuando se conecta cada nodo con todos los demás, incluido sí mismo.

POLITÉCNICO GRANCOLOMBIANO

7

Un grafo G= es un grafo completo si y solo si para todo par de nodos distintos a y b, se cumple que hay un arco desde a hacia b. En un grafo completo con n nodos debe haber exactamente n*(n-1) arcos si se cuenta cada enlace (-) como dos arcos por separado (� y ←). No obstante, si se cuenta cada enlace (-) como un solo arco, un grafo completo con n nodos tendría exactamente n*(n-1)/2 arcos. Nótese que un grafo completo no requiere enlace de cada nodo con sí mismo. La figura 5 muestra los ejemplos de grafos completos con un número de nodos, n, variando desde 1 hasta 10 y considerando cada enlace como dos arcos:

Figura 5. Ejemplos de grafos completos Fuente: Sotelo (s.f.)

Subjetivamente, un grafo G= es un grafo denso si y solo si e está cerca de n2, donde n es la cantidad de nodos y e es la cantidad de arcos. Subjetivamente, un grafo G= es un grafo disperso si y solo si e está cerca de n, donde n es la cantidad de nodos y e es la cantidad de arcos. La figura 6 muestra algunos ejemplos de grafos tanto densos como dispersos considerando cada enlace como dos arcos:

Figura 6. Ejemplos de algunos grafos densos y algunos grafos dispersos Fuente: Sotelo (s.f.)

POLITÉCNICO GRANCOLOMBIANO

8

2.6. Caminos y cadenas Un camino es una lista no vacía de nodos 〈x1, x2, … ,xm 〉 donde cada nodo es sucesor de su anterior (para todo i desde 2 hasta m, se cumple que xi es sucesor de xi-1). La longitud de un camino 〈x1, x2, … ,xm 〉 es m-1, es decir, la cantidad de nodos en la lista menos uno. El primer nodo de un camino se llama origen y el último se llama destino. Un camino simple es un camino tal que todos los nodos que recorre son distintos, con la excepción de que su origen puede ser igual a su destino. Una cadena es una lista no vacía de nodos 〈x1, x2, … ,xm 〉 donde cada nodo es adyacente a su anterior para todo i desde 2 hasta m, se cumple que xi es sucesor y/o antecesor d e xi-1). La longitud de una cadena 〈x1, x2, … ,xm 〉 es m-1, es decir, la cantidad de nodos en la lista menos uno. La figura 7 muestra un grafo y la clasifica algunas listas como camino, camino simple y/o cadena:

〈A, C, A〉

Longitud (tamaño -1) 2

¿Es camino? SI

¿Es camino simple? SI

¿Es cadena? SI

〈A, C, A, C, A〉

4

SI

NO

SI

〈D, B, F, A, D〉

4

NO

NO

SI

〈A, F, E, A, F, E, A〉

6

NO

NO

SI

〈E, F, D, C, E〉

4 6

NO SI

NO NO

NO SI

Lista

〈D, D, B, B, B, B, F〉

Figura 7. Ejemplo de un grafo y la clasificación de algunas listas de sus nodos Fuente: Sotelo (s.f.)

Cómo mejorar... Reflexione acerca de cada uno de los siguientes hechos:

•

Todo camino es cadena, pero no toda cadena es camino.

•

En un grafo no dirigido los conceptos de camino y cadena son equivalentes.

•

Toda cadena es un camino en la clausura simétrica del grafo, y viceversa.

POLITÉCNICO GRANCOLOMBIANO

9

2.7. Ciclos, grafos cíclicos y grafos dirigidos acíclicos Un ciclo es un camino cuyo origen es igual a su destino. Un ciclo simple es un camino simple cuyo origen es igual a su destino. Tabla 4. Ejemplos de grafos y su clasificación de acuerdo a si contienen ciclos o no

Fuente: Sotelo (s.f.)

Un grafo G= es un grafo cíclico si y solo si tiene por lo menos un ciclo. Un grafo G= es un grafo acíclico si y solo si no tiene ningún ciclo. Un grafo G= es un grafo dirigido acíclico si y solo si es un grafo dirigido que no tiene ningún ciclo. Estos grafos se conocen en inglés como Directed Acyclic Graphs (DAG por sus siglas), y tienen especial importancia en la teoría de grafos, porque todo camino en un DAG recorre nodos distintos sin caer en un ciclo, lo que facilita el proceso de recorrerlo. La tabla 4 presenta varios ejemplos de grafos y los clasifica de acuerdo a si contienen ciclos o no.

2.8. Descendientes y ancestros Un nodo a es descendiente de un nodo b si y solo si existe un camino que va de b hacia a. Un nodo a es ancestro de un nodo b si y solo si existe un camino que va de a hacia b. Nótese lo siguiente:

POLITÉCNICO GRANCOLOMBIANO

10

•

Un nodo es ancestro de un nodo b si y solo si b es descendiente de a .

•

Todo nodo es ancestro y descendiente de sí mismo, debido a la existencia de caminos de longitud cero.

•

Para todo camino se cumple que su origen es ancestro de su destino y que su destino es descendiente de su origen.

•

Para todo nodo de un grafo no dirigido se cumple que sus ancestros y que sus descendientes son los mismos.

La figura 8 presenta un grafo y los ancestros y descendientes de cada uno de sus nodos: Nodo

Sucesores

Antecesores

A

〈A, B, C, D, E〉

〈A〉

B

〈B, C, E〉

〈A, B〉

C

〈C, E〉

〈A, B, C, D〉

D

〈C, D, E〉

〈A, D〉

E

〈E〉

〈A, B, C, D, E〉

F

〈F〉

〈F〉

G

〈G〉

〈G〉

Figura 8. Ejemplo de un grafo y los ancestros y descendientes de sus nodos Fuente: Sotelo (s.f.)

2.9. Grafos conexos y grafos fuertemente conexos Un grafo G= es un grafo conexo si y solo si para todo par de nodos a y b, se cumple que hay una cadena desde a hacia b. Un grafo G= es un grafo fuertemente conexo si y solo si para todo par de nodos a y b, se cumple que hay un camino desde a hacia b. Todo grafo fuertemente conexo también es conexo, pero no todo grafo conexo es fuertemente conexo.

POLITÉCNICO GRANCOLOMBIANO

11

La tabla 5 recoge algunos ejemplos de grafos y los clasifica como grafos conexos y/o fuertemente conexos: Tabla 5. Ejemplos de grafos y su clasificación en conexos y/o fuertemente conexos

Grafo

¿Es conexo?

¿Es fuertemente conexo?

SI

NO

SI

SI

NO

NO

NO

NO

Fuente: Sotelo (s.f.)

2.10.

Sub-grafos, componentes conexas y componentes fuertemente conexas

Un grafo G = es un subgrafo de un grafo G = si y solo si:

•

.V ⊆V (el conjunto de nodos de G  es subconjunto del conjunto de nodos de G)

•

. E ⊆E (el conjunto de arcos de G es subconjunto del conjunto de arcos de G ).

POLITÉCNICO GRANCOLOMBIANO

12

Una componente conexa es un sub-grafo conexo que cumple la propiedad de que no se le puede agregar ningún nodo ni arco de tal forma que siga siendo conexo. Una componente fuertemente conexa es un sub-grafo fuertemente conexo que cumple la propiedad de que no se le puede agregar ningún nodo ni arco de tal forma que siga siendo fuertemente conexo. La tabla 6 presenta ejemplos de grafos y el número de componentes conexas que contienen.

2.11. Caminos y ciclos hamiltonianos Un camino Hamiltoniano es un camino simple que recorre todos los nodos del grafo. Un ciclo Hamiltoniano es un ciclo simple que recorre todos los nodos del grafo. Como los ciclos también son caminos, entonces todo ciclo Hamiltoniano también es un camino Hamiltoniano. La tabla 7 presenta ejemplos de grafos y los ciclos y caminos hamiltonianos que contienen:

Tabla 6. Ejemplos de grafos y sus componentes conexas

Grafo

Número de componentes conexas SI

SI

NO

NO

Fuente: Extracto de una tabla de Sotelo (s.f.)

POLITÉCNICO GRANCOLOMBIANO

13

Tabla 7. Ejemplos de grafos y sus ciclos y caminos hamiltonianos

Grafo

¿Es conexo?

¿Es fuertemente conexo?

El grafo no tiene ningún ciclo Hamiltoniano.

El grafo no tiene ningún ciclo Hamiltoniano.

El grafo no tiene ningún ciclo Hamiltoniano.

El grafo no tiene ningún ciclo Hamiltoniano.

El grafo no tiene ningún ciclo Hamiltoniano.

Fuente: Extracto de una tabla de Sotelo (s.f.)

2.12.

Caminos y ciclos eulerianos

Un camino Euleriano es un camino que recorre todos los arcos del grafo, sin repetir. Un ciclo Euleriano es un ciclo que recorre todos los arcos del grafo, sin repetir. Como los ciclos también son caminos, entonces, todo ciclo Euleriano también es un camino Euleriano. Además, hay que tener en cuenta que, si el grafo es no dirigido, cada arco se debe visitar en una sola dirección. La tabla 8 contiene ejemplos de grafos y sus caminos y ciclos eulerianos:

POLITÉCNICO GRANCOLOMBIANO

14

Tabla 8. Ejemplos de grafos y sus ciclos y caminos eulerianos

Grafo

camino Euleriano (ejemplo)

Ciclo Euleriano (ejemplo)

El grafo no tiene ningún ciclo Euleriano.

El grafo no tiene ningún ciclo Euleriano.

El grafo no tiene ningún camino El grafo no tiene ningún ciclo Euleriano. Euleriano.

Fuente: Extracto de una tabla de Sotelo (s.f.)

¿Sabía que...? La solución al problema típico en el que se propone dibujar una casa sin levantar el lápiz de la hoja (ver la figura 9) implica hallar un camino Euleriano.

Figura 9. Casa que debe ser dibujada sin levantar el lápiz Fuente: elaboración propia

POLITÉCNICO GRANCOLOMBIANO

15

3. Representación

2

Para implementar un grafo es necesario representar sus nodos y sus arcos con estructuras de datos apropiadas, según las necesidades particulares que se tengan.

3.1. Almacenamiento de los nodos La tabla 9 ofrece tres maneras diferentes de almacenar los nodos de un grafo: Tabla 9. Estructuras de datos típicas para almacenar los nodos de un grafo

Nombre de la estructura

Descripción

Arreglos de nodos Consiste en almacenar los nodos en un arreglo. Lista de nodos Conjunto de nodos

Consiste en almacenar los nodos en una lista, implementada con vectores de tamaño variable o con nodos encadenados. Consiste en almacenar los nodos en un conjunto, implementando con árboles Roji-negros o con tablas Hashing.

Fuente: Sotelo (s.f.)

2 La teoría expuesta en esta sección, como el resto del documento, es una adaptación del texto de Sotelo (s.f.) que a su vez se inspiró para este apartado en Villalobos (1996).

POLITÉCNICO GRANCOLOMBIANO

16

3.2. Almacenamiento de los arcos Por simplicidad, suponga que los nodos del grafo están identificados con números naturales desde 0 hasta n-1, donde es la cantidad total de nodos. La tabla 10 presenta algunas de las estructuras típicamente usadas para guardar los arcos de un grafo:

Tabla 10. Estructuras de datos típicas para almacenar los arcos de un grafo

Nombre de la estructura

Descripción

Lista de arcos

Consiste en almacenar los arcos en una lista.

Consiste en almacenar la información de los arcos en una matriz m de números flotante de tamaño n x n donde para todos i y j entre o y n-1 s Matriz de adyacencia se tiene m [i] [j] es el costo del arco que va del nodo con identificador i al nodo con identificador j. En caso de que no haya arco desde i hacia j, entonces m [i] [j] se llena con el valor infinito. Consiste en tener para casa nodo: • Una lista con sus arcos de salida, que van hacia sus sucesores. Lista de adyacencia

• Lista de sucesores

Otra lista con sus arcos de entrada, que vienen desde sus predecesores.

Consiste en tener para casa nodo una lista con sus arcos de salida, que van hacia sus su...