Grafos

Asignatura: Desarrollo de Software

Tema: Grafos

PNFSI

Ing. Zamantha González Abril, 2008

Tema 4: Grafos

Contenido

• Definición de grafo.

• Operaciones sobre grafos.

• Representación matricial de grafos en un lenguaje

de programación.

• Grafos (representación enlazada)

• Operaciones sobre grafos representados de

manera enlazada.

• Representación enlazada de grafos en un

lenguaje de programación

Objetivos

Conozcan las estructuras de datos arbóreas y las

formas de trabajar con ellas en la solución de

problemas de mediana complejidad

Introducción

Estructuras de datos estudiadas:

Listas lineales y sus variantes.

Las relaciones entre los nodos de información son

lineales.

•Todos los nodos tienen un único antecesor,

excepto el primero que no tiene antecesor.

•Todos los nodos tienen un único sucesor, excepto

el último que no tiene sucesor.

Introducción

Estructuras de datos estudiadas:

Los árboles y sus variantes

Cuando se está en presencia de relaciones nolineales de tipo jerárquica, se utilizan los árboles.

• Un nodo puede tener más de un sucesor.

• Se puede establecer un camino único desde elnodo raíz hasta un nodo cualquiera del árbol.

• Cada nodo tiene un único padre, exceptuando alnodo raíz del árbol, que no tiene padre.

Introducción

En ocasiones, incluso, se requiere tener acceso a un

nodo determinado a partir de más de un nodo de la

estructura. Existen varios caminos entre un nodo y

otro.

Ejemplo:

• Una red hidráulica,

• Caminos entre ciudades,

• Afinidad entre miembros de un colectivo, entre

otros.

Introducción

Caminos entre ciudades

Ciudad A

Ciudad B

Ciudad CCiudad F

Ciudad D

Ciudad E

Definición de Árbol

Un árbol (tree) es un T.D.A. que consta de un

conjunto finito T de nodos y una relación R

(paternidad) entre los nodos tal que:

• Hay un nodo, especialmente designado, llamado la

raíz del árbol T.

A

D E F G

CB

A

D E F G

CB


• Los nodos restantes, excluyendo la raíz, son

particionados en m (m 0) conjuntos disjuntos T1,

T2, ..., Tm, cada uno de los cuales es, a su vez, un

árbol, llamado subárbol de la raíz del árbol T.

A

D E F G

CB


• A los nodos que no son raíces de otros subárboles

se les denomina hojas del árbol T, o sea, no tienen

sucesores o hijos.

A

D E F G

CB

Grafos

Un grafo (en inglés graph) es un T.D.A. querepresenta un conjunto finito N de nodos, llamadosvértices, relacionados entre sí por un conjunto R dearcos.

AB

DC

E

Grafo con 5 vértices y 6 arcos.

• Vértices del Grafo

N ={ A, B, C, D, E }

• Arcos del Grafo

R={(A, A), (A, B), (A, D), (A, C), (D, C), (C, E)}

Grafos: Aclaraciones

•Si el conjunto N es vacío, el grafo será vacío.

• Cada arco de un grafo establece una única relación

entre dos vértices.

• No existe restricción en la relación que establece

un arco, o sea, un vértice puede estar relacionado

consigo mismo o con otro vértice.

• Cada arco se representa a través de un par, donde

cada elemento determina uno de los vértices.

Observación

Dado que no hay restricciones en cuanto a los arcosde un grafo, todas las estructuras vistas conanterioridad pueden ser consideradas como ungrafo.

Ejemplo, una lista lineal puede ser vista como ungrafo donde cada nodo está relacionado conexactamente un nodo distinto de él.

Clasificación de los Grafos

Un grafo es no orientado o no dirigido (en inglés

not directed o not oriented graph) si el hecho de

que el arco (Nj, Nk) pertenezca a R implica que el

arco (Nk, Nj) pertenece a R, para todo j y k.

• Es irrelevante el sentido de las saetas en los arcos

• Al representarlos, los arcos se grafican sin saeta.

• El arco que los relaciona aparece una sola vez en

el conjunto R de arcos del grafo.

Si el grafo es no orientado, al arco se le llama arista.


Un grafo es orientado o dirigido (en inglés:

oriented graph o directed graph) si el hecho de

que el arco (Nj, Nk) pertenezca a R no implica que el

arco (Nk, Nj) pertenece también a R, para todo j y k.

• El sentido de las saetas en los arcos es importante.

• Es importante la dirección del arco, o sea, el vértice

origen del arco y el vértice destino.

• El hecho que exista un arco de Nj a Nk no implica

que exista de Nk a Nj.

Se conocen como digrafos (en inglés: digraph).

AB

DC

E

Grafo No Orientado

o No Dirigido


AB

DC

E

Grafo Orientado o

Dirigido

Adyacencia

El vértice n es adyacente al m, si existe un arco o

arista de m a n.

AB

DC

E

Adyacencia:

• B es adyacente a A

• D es adyacente a A

• C es adyacente a A

• A es adyacente a A

• C es adyacente a D

• E es adyacente a C

Incidencia

AB

DC

E

Incidencia:

• B es incidente al arco (A,B)

• (A,B) es incidente a B

El vértice n es incidente al arco o arista x, si n es

uno de los vértices relacionados con el arco o arista

x. Del mismo modo, se dice que el arco o arista x es

incidente al vértice n.

Así, todos los arcos que llegan o salen de un nodo

son incidentes a él

.

Sobre el Vértice D:

• Grado de Entrada: 3

• Grado de Salida: 2

• Grado del Nodo: 5

AB

D

C

E

F

Grado de un Vértice

Grado de un Vértice

El grado de un vértice n es el número de arcos

incidentes a él.

En el caso de los grafos orientados, el grado de

entrada de un vértice n es el número de arcos que

llegan a él y el grado de salida de un vértice n es el

número de arcos que salen de él.

Por lo tanto, el grado de un vértice es la suma de

los grados de entrada y de salida del vértice.

Ponderando arcos y vértices

En muchas aplicaciones resulta de interés asignar

valores de ponderación, también llamados pesos,

a los arcos o a los vértices, obteniéndose así:

• Grafos ponderados por los arcos

• Grafos ponderados por los vértices

Ejemplo: Grafo ponderado por los arcos

Problema del agente viajero

Un agente necesita repartir paquetes en diferentes

ciudades. Se sabe en qué ciudades el agente debe

repartir los paquetes, así como la distancia entre

cada ciudad y las otras.

El problema consiste en saber cuál es la mejor ruta a

seguir por el agente para repartir todos los paquetes.


El problema se puede modelar con un grafo, donde:

• Las ciudades son vértices.

• Los caminos entre las ciudades son arcos.

Si para todas las ciudades se cumple que la

distancia entre una ciudad origen y una ciudad

destino y la distancia de la ciudad destino a la ciudad

origen es la misma, entonces, se puede utilizar un

grafo no orientado.

Podemos ponderar los arcos con la distancia que

existe entre las ciudades.


El agente debe visitar tres ciudades A, B y C,

partiendo de la ciudad A. Entre las ciudades A y B

hay 50 km, entre las ciudades B y C hay 20 km y

entre las ciudades A y C hay 15 km.

El camino más corto es de A a C y de C a B.

A B

C

50 Km

Caminos:

A-B-C: 70 Km

A-C-B: 35 Km

Ejemplo: Grafo ponderado por los vértices

Se tiene una secuencia de actividades, de las que se

conoce su duración y se quiere saber, en un

momento dado, en qué orden debieran realizarse, de

forma tal que se realicen primero las de menor

duración.

• Las actividades se pueden representar por los

vértices de un grafo no orientado.

• En cada vértice se puede almacenar la duración de

la actividad como factor de ponderación.

Ejemplo: Grafo ponderado por los vértices

Resulta más conveniente realizar la actividad A,

luego la C y, por último, la B.

A

10

B

25

C

20

Camino entre vértices

Existe un camino de longitud k desde el vértice A

al B, si existe una secuencia de k+1 vértices n1, n2,

..., nk+1, donde n1 = A, nk+1 = B y (ni, ni+1) son

adyacentes para todo i entre 1 y k.

En un grafo no orientado, al camino se le llama

cadena.

AB

DC

E

Caminos entre los vértices A y C:

Camino de longitud 1: (A,C)

Camino de longitud 2: (A,D,C)

Camino de longitud 2: (A,A,C)

Camino de longitud 3: (A,A,D,C)

Ejemplo: Camino entre nodos

¿Existe un camino de longitud mayor que 1 entre los

vértices C y B?

• Camino de longitud 3: (C, B, A, B)

• Camino de longitud 4: (C, B, A, C, B)

AB

DC

Camino simple

Entre dos vértices existe un camino simple si todos

los vértices, excepto posiblemente el primero y el

último, son distintos dos a dos.

O sea, un camino simple es aquel en el que no se

repiten los arcos.

Ejemplo:

(A, B, D)

(A, B, A, C)

AB

DC

Camino simple

Un ciclo, o también circuito, es un camino simple

de cualquier longitud de un vértice a sí mismo. Si el

ciclo es de longitud 1, entonces se denomina bucle o

lazo.

Ejemplo:

Ciclo: A,D,C,A

Bucle: A,A

AB

DC

E

Grafo cíclico y acíclico

Si un grafo contiene al menos un ciclo se llama

cíclico.

Un grafo acíclico es aquel que no tiene ningún

circuito o ciclo.

AB

DC

E

AB

DC

Grafo cíclico Grafo acíclico

Operaciones sobre Grafos

• Construir un grafo dada la información de sus

vértices. (Convenio: se crea inicialmente vacío).

• Verificar si un grafo está vacío o no.

• Insertar vértices y arcos.

• Eliminar vértices y arcos.

• Dados dos vértices, determinar si son adyacentes.

• Dado un vértice, determinar cuáles vértices son

adyacentes a él.

Operaciones sobre Grafos

• Dados dos vértices, determinar un camino de

longitud k entre ellos.

• Dado un arco, determinar vértices incidentes a él.

• Determinar si el grafo es cíclico.

Representación matricial de Grafos

• La representación matricial permite establecer si

hay relación entre cada vértice del grafo y los

demás.

• Para ello, se utiliza una matriz cuadrada.

• Se utiliza un arreglo bidimensional.

• Esto significa que la representación matricial es

una representación secuencial.


A partir de un grafo, siempre es posible definir un

orden arbitrario de los vértices.

A B C D E

0 1 2 3 4

AB

DC

E

Matriz de Adyacencia

La matriz de adyacencia representa para cada

nodo cuáles son sus vértices adyacentes.

• Cada fila y cada columna de la matriz se

corresponde con un vértice en particular.

• Los elementos de la matriz son booleanos

• Si el elemento (i, j) es verdadero, existe un arco

que va del vértice i al vértice j y, si el elemento (i, j)

es falso, no existe arco del vértice i al vértice j.

• Si el grafo es no orientado, si existe el arco del

vértice i al vértice j existe el arco del vértice j al

vértice i.


A B C D E

0 1 2 3 4

0 1 2 3 4

01000

10000

11000

00100

011000

1

2

3

4

AB

DC

E

Vértices

Matriz de Adyacencia

Implementación en C++

class TVertex

{

private:

void* aInfo;

public:

TVertex(void* pInfo) : aInfo(pInfo){}

void* Info(){return aInfo;}

};


class TSeqGraph

{

private:

bool** aAdjacent;

bool aDirected;

int aOrder;

TGSeqList* aVertexList;

public:

TSeqGraph(int, bool);

~TSeqGraph();

TGSeqList* Adjacents(int);

bool AreAdjacents(int, int);

bool Cyclic();

int Degree(int);

… };


class TSeqGraph

{

public:

…

bool DeleteEdge(int, int);

bool DeleteVertex(int);

bool Directed() {return aDirected;}

bool Empty(){return aVertexList->Empty();}

bool InsertEdge(int, int);

bool InsertVertex(void*);

bool IsEdge(int, int);

bool IsPathWithLength(int, int, int);

int Order() {return aOrder;}

TGSeqList* VertexList(){return aVertexList;}

};

Problemas

La representación de la matriz de adyacencia de

un grafo exige conocer por adelantado la cantidad

de vértices del grafo.

Esta representación no es suficientemente flexible

cuando la cantidad de vértices varía con relativa

frecuencia o cuando la estructura del grafo cambia

durante la ejecución de la aplicación que lo usa.

Esto implica crear la matriz cada vez que se inserte

o elimine un nuevo vértice.

Problema: Solución costosa en tiempo y recursos.

Representación enlazada de Grafos

AB

DC

E

Variante 1:

A

B

C

D

E

C D

C

D E

E

D

Una lista de vértices y cada uno tiene

una lista de los vértices adyacentes a él.

Problemas

• Es difícil saber cuántos arcos

llegan a un vértice.

• Se repite la información del

vértice

• Las listas pueden ser

indistintamente secuenciales o

enlazadas o una combinación.

• El grafo está vacío si no

existen vértices.


Variante 2: Representación multienlazada

• Cada vértice se representa a través de un nodo que

contiene:

• Apuntador a su información,

• Apuntador a una lista de arcos

• Apuntador al siguiente vértice en la lista

•Cada arco se representa por un nodo que contiene:

• Apuntador al próximo arco de su vértice origen

• Apuntador al nodo de su vértice destino


Variante 2: Representación multienlazada

AB

DC

E

• El grafo está vacío si no hay

vértices.

A B C D E

c

D

C D

E

E


Contador de referencia formar parte de la

información de los vértices y mantiene actualizado

la cantidad de arcos llegan a él.

• Los contadores de referencia facilitan algunas

operaciones del grafo:

• Al eliminar un vértice se deben decrementar los

contadores de referencia de los vértices adyacentes.

Si el contador del vértice adyacente se hace cero, se

puede eliminar ese vértice si la lista de arcos está

vacía.


La representación multienlazada de grafos debe

considerar si el grafo es ponderado por los

vértices o por los arcos.

En estos casos habría que agregar a los nodos de

vértices y arcos respectivamente el peso o factor

de ponderación.


class TVertex

{

private:

void* aInfo;

TGLinkedList* aEdgeList;

public:

TVertex(void* pInfo) : aInfo(pInfo)

{aEdgeList = new TGLinkedList();}

void* Info() {return aInfo;}

void Info(void* pInfo) {aInfo = pInfo;}

TGLinkedList* EdgeList(){return

aEdgeList;}

};


class TEdge

{

private:

TVertex* aVertex;

public:

TEdge(TVertex* pVertex){aVertex =

pVertex;}

TVertex* Vertex(){return aVertex;}

void Vertex(TVertex* pVertex)

{aVertex = pVertex;}

};


class TLinkedGraph

{

private:

bool aDirected;

TGLinkedList* aVerticesList;

public:

TLinkedGraph(bool pDirected);

~TLinkedGraph();

TGLinkedList* Adjacents(int);

bool AreAdjacents(int, int);

bool Cyclic();

int Degree(int);

…

};


class TLinkedGraph

{

…

bool DeleteEdge(int, int);

TVertex* DeleteVertex(int);

bool Directed (){return aDirected;}

bool Empty(){return aVertexList-

>Empty();}

int InDegree(int);

bool InsertEdge(int, int);

bool InsertVertex(void*);

TSEdge* IsEdge (int, int);

int OutDegree(int);

bool Path(int, int, int);

bool PathWithLength (int, int, int);

TGLinkedList* VerticesList();

};

Inserción en grafos multienlazados

Inserción un arco de V1 a V2:

1-Verificar la existencia de los vértices V1 y V2

2-Hay dos posibilidades:

2.1 De no existir uno o ninguno, no se

puede insertar el arco.

2.2 Insertarlos.

• Insertar un arco en la lista de arcos de V1 y

poner su apuntador al vértice adyacente

apuntando al nodo que contiene a V2 en la lista

de vértices.

• Si tiene contador de referencia incrementar en 1,

el contador de referencia del vértice V2.

Eliminación en grafos multienlazados

Eliminar el vértice V:

1-Verificar la existencia del vértice V.

2-Para cada arco de V:

-Si en el vértice apuntado por ese arco hay

contador de referencia, decrementarlo en uno y

si éste toma el valor cero, verificar si la lista de

arcos está vacía, para eliminarlo.

-Eliminar el arco.

Eliminación en grafos multienlazados

Eliminar el vértice V:

3-Para cada Vértice excepto V

-Buscar si existe algún arco que apunte a V

-i existe eliminarlo y si la lista queda vacía,

verificar el contador de referencia y si es cero,

analizar de acuerdo a la política si se elimina o

no.

4-Eliminar el vértice V.

5-Devolver la información del vértice V.

Date post:	14-Jun-2015
Category:	Technology
Upload:	zamantha-gonzalez-universidad-nacional-abierta
View:	27,971 times
Download:	3 times

Grafos

Technology