algoritmos y estructura de datos - lectura 2

7/17/2019 Algoritmos y Estructura de datos - Lectura 2

http://slidepdf.com/reader/full/algoritmos-y-estructura-de-datos-lectura-2 1/7

Materia: Algoritmos y Estructuras de Datos 2

Profesor: Claudio Ochoa - 1 -

Lectura 2: Definiciones y Conceptos Relacionados a

Grafos

Temas:2.1 Grafos y digrafos2.2 Adyacencia2.3 Grado de un vértice2.4 Ciclos y caminos2.5 Grafos simples y multigrafos

2.6 Grafos densos y dispersos2.7 Bucle2.8 Grafos conexos2.9 Grafos completos2.10 Ejemplo de propiedades de grafos

Bibliografía:

- Estructuras de Datos en Java, Mark Weiss, Addison Wesley, 2000, capítulo 14

2.1 Grafos y digrafos

Como mencionamos en la lectura anterior, un grafo es un una tupla <V, E>, donde

V: conjunto de vértices (nodos)

E: conjunto de aristas (arcos)

y cada arista es un par (v,w), donde v,w V.

Los grafos pueden ser dirigidos (o dígrafos), y en ese caso (v,w) se trata un par ordenado.

Algunas veces las aristas tienen un peso o costo asociado (v,w,p), v,w V, p R . Por ejemplo, en

el grafo de la Figura 1, se observa un conjunto de ciudades, donde las distancias entre ellas están

determinadas por los pesos de cada arista. Este grafo puede ser utilizado para encontrar el

camino más corto (en kilómetros) que lleva de una ciudad a otra.





Figura 1. Grafo de distancia entre ciudades

2.2 Adyacencia

Decimos que un vértice w es adyacente a un vértice v si existe una arista (v,w) en E. En el caso

de grafos no dirigidos, si w es adyacente a v, entonces v es adyacente a w. En el caso de

dígrafos, esto no se cumple, a no ser que tanto (v,w) y (w.v) sean aristas del grafo.

2.3 Grado de un vértice

Se considera grado de un vértice a la cantidad de aristas que llegan o salen de él. Para el caso de

grafos no dirigidos, el grado de un vértice es simplemente la cantidad de aristas incidentes a estevértice.

En el caso de grafos dirigidos, podemos definir un grado de entrada y un grado de salida. El grado

de entrada está determinado por el número de aristas que llegan al grafo, mientras que el grado

de salida está determinado por el número de aristas que salen de él. Por ejemplo, en la siguiente

figura el grado de salida de V 2 es 2, mientras que el grado de entrada de V 2 es 1.

Bogotá

Brasilia

Lima

Santiago

Buenos Aires

Asunción

1.500

800

900

2.000

200

500

120

230

201

320

280

1900

250

160

210





Figura 2. Grafo dirigido

A un vértice del que sólo salen aristas se le denomina fuente (en el ejemplo anterior, el vértice V 4 ),

mientras que a aquellos vértices a los que sólo llegan aristas se les denomina sumidero (en el

caso anterior, el vértice V 5 ); tiene grado positivo 0.

2.4 Ciclos y caminos

Un camino es secuencia de vértices w1,..,wN donde (wi,wi+1) E, para 1 i < N. Se define como la

longitud de un camino al número de aristas en el camino. Por ejemplo, la longitud del camino

w1,..,wN es N-1. Cuando las aristas tienen peso, se define su longitud como la suma de los pesos

de las aristas en el camino. Un camino simple es un camino en el que todos los vértices son

distintos, con excepción del primero y el último.

Un ciclo es un camino w1,..,wN donde w1 y wN son el mismo vértice. Un ciclo hamiltoniano tiene,

además, que recorrer todos los vértices exactamente una vez (excepto el vértice del que parte y al

cual llega). La Figura 3 muestra un ciclo hamiltoniano.

Por ejemplo, en un museo grande (al estilo del Louvre), lo idóneo sería recorrer todas las salas

una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los

vértices son las salas y las aristas los corredores o puertas entre ellas).

V0

V2 V3

V1

V6V5

V4

1

8 45

2

4

1

2

2

10

3

6





Se habla también de camino hamiltoniano si no se impone regresar al punto de partida. Por

ejemplo, un caballo puede recorrer todas las casillas de un tablero de ajedrez sin pasar dos veces

por la misma: es un camino hamiltoniano.

Hoy en día, no se conocen métodos generales para hallar un ciclo hamiltoniano en tiempo

polinómico, siendo la búsqueda por fuerza bruta de todos los posibles caminos u otros métodos

excesivamente costosos. Existen, sin embargo, métodos para descartar la existencia de ciclos o

caminos hamiltonianos en grafos pequeños.

El problema de determinar la existencia de ciclos hamiltonianos, entra en el conjunto de los NP-

completos.

Figura 3. Ciclo hamiltoniano

Fuente: http://es.wikipedia.org/wiki/Archivo:Hamiltonian_path.svg

Si un grafo no contiene ciclos, decimos que el grafo es acíclico.

2.5 Grafos simples y multigrafos

Un grafo es simple si a lo sumo sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a

decir que una arista cualquiera es la única que une dos vértices específicos.





Un grafo que no es simple se denomina multigrado

2.6 Grafos densos y dispersos

Si un grafo tiene un gran número de aristas, decimos que se trata de un grafo denso. En el caso

de los grafos dirigidos, podemos ser mas precisos diciendo que es denso si |E| (|V|2). Si |E|

(|V|) decimos que el grafo es disperso. En la mayoría de las aplicaciones los grafos son

dispersos.

Nótese que puede haber grafos que no sean ni densos ni dispersos.

2.7 Bucle

Un bucle es una arista (v,v), es decir, una arista que sale y llega al mismo nodo. En la figura 4,

vemos un bucle, donde una arista sale y llega al nodo A

Figura 4. Bucle

2.8 Grafos conexos

Un grafo es conexo si cada par de vértices está conectado por un camino, es decir, si para

cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b .

Un grafo es fuertemente conexo si cada par de vértices está conectado por al menos dos caminos

disjuntos, es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea

disconexo.

A





Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (Breadth

First Search , o BFS) o Búsqueda en profundidad (Depth First Search , o DFS).

Figura 5. Grafos conexos y no conexos

Fuente: http://es.wikipedia.org/wiki/Archivo:GrafoConexo.jpg

2.9 Grafos completos

Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices, es decir, todo

par de vértices (a, b) debe tener una arista e que los une.

Un grafo completo de n vértices tiene exactamente aristas.

2.10 Ejemplo de propiedades de grafos





Figura 6. Grafo de ejemplo

En el grafo de la figura 6:

Los nodos c y e tienen grado 4, y los demás nodos tienen grado 5

Existe un lazo o bucle en el nodo d

Es multigrafo ya que existen dos aristas que unen los vértices a y b

Existen varios caminos que unen el nodo a y el nodo d

o Por ejemplo, a-b-c-d, a-e-d , a-d o a-c-d

El camino a-c-d-a es un ciclo

El camino a-c-d-a es un camino simple, mientras que a-c-b-d-c-a no lo es

Es un grafo conexo, ya que todos los nodos tienen al menos un camino a otro nodo

Es un grafo completo, ya que existen aristas para todo par de vértices

Es un grafo denso, ya que |E|=12, si fuera dirigido |E|=23 |V|2=25

a

ec

b

d

algoritmos y estructura de datos - lectura 2

Documents