DE SISTEMAS Y COMPUTACIÓN

SEP SEIT DGIT

INSTITUTO TECNOLÓGICO DE NUEVO

LAREDO

DEPTO. DE SISTEMAS Y COMPUTACIÓN

“GRAFOS”

Estructura de Datos

Lipschutz, Seymour

CAPÍTULO 8

GRAFOS

Un grafo está formado por un conjunto de nodos(o vértices) y un conjunto de arcos. Cada

arco en un grafo se especifica por un par de nodos.

El conjunto de nodos es {A, B, C, D, F, G, H} y el conjunto de arcos {(A, B), (A, D), (A,

C), (C, D), (C, F), (E, G), (A, A)} para el siguiente grafo

A

B

D

C

F

E G

H

arco

nodo

Si los pares de nodos en los arcos dirigidos, el grafo se denomina grafo directo, dirigido o

dígrafo.

TERMINOLOGÍA

*.-Al número de nodos del grafo se le llama orden del grafo.

*.-Un grafo nulo es un grafo de orden 0 (cero).

*.-Dos nodos son adyacentes si hay un arco que los une.

*.-En un grafo dirigido, si A es adyacente de B, no necesariamente B es adyacente de A

*.-Camino es una secuencia de uno o mas arcos que conectan dos nodos.

*.-Un grafo se denomina conectado cuando existe siempre un camino que une dos

nodos cualesquiera y desconectado en caso contrario.

*.-Un grafo es completo cuando cada nodo esta conectado con todos y cada uno de los

nodos restantes.

*.-El camino de un nodo así mismo se llama ciclo.

Representacion

de grafos

Secuencial

Enlazada

Matriz de

adyacencia

Listas

encadenadas { {

{

MATRIZ DE ADYACENCIA

B

A C

D

0

0

1

0

0

1

0

0

1 0 0 1

0 0 0 0

B

C

D

A

A B C D

B

A C

D

600

100 0

0 600 0

0

300

300 0

0

0 0

100

0

0

600

600

A B C D

ABCD

300

600

600

1000

*.-Un grafo sin ciclos es un árbol.

*.-El entregado de un nodo indica el número de arcos que llegan a se nodo.

*.-El fuera de grado de un nodo indica el número de arcos que salen de él.

*.-Un grafo de N vértices o nodos es un árbol si cumple las siguientes condiciones

a) Tiene N-1 arcos

b) Existe una trayectoria entre cada par de nodos.

c) Esta mínimamente conectado.

Ciclo

ARBOL GRAFO

*.-Un grafo esta etiquetado si sus arcos tiene valores asignados. Si este valor es numérico

se dice que el grafo tiene peso.

GRAFOS Y SUS APLICACIONES

INTRODUCCIÓN

Este capítulo profundiza en otra estructura de datos no lineal: el grafo. Como hemos hecho

con otras estructuras de datos. Discutiremos la representación de los grafos en memoria y

presentaremos varias operaciones y algoritmos sobre ellos. En particular discutiremos la

búsqueda en anchura y la búsqueda en profundidad para nuestros grafos. También se

repasaran ciertas aplicaciones de los grafos, incluyendo la ordenación topológica.

8.2 TERMINOLOGÍA DE TEORÍA DE GRAFOS

Esta sección recoge alguna de la terminología principal asociada con la teoría de grafos

por tanto advertimos al lector de que nuestras definiciones pueden ser ligeramente

diferentes de las definiciones usadas en otros textos de estructuras de datos y teoría de

grafos.

GRAFOS Y MULTIGRAFOS

Un grafo G consiste en dos cosas:

(1) Un conjunto V de elementos llamados nodos (o puntos o vértices)

(2) Un conjunto E de aristas tales que cada arista e de E esta identificada por un único

(desordenado) par [u,v] de nodos de V, denotado por e-[v,u].

A veces denotamos un grafo escribiendo G=(V,E)

Suponga que e =[u,v]. entonces los nodos u y v se llaman extremos de e, y u y v se dice

que son nodos adyacentes o vecinos. El grado de un nodo u, escrito grad(u), es el número

de artistas que contienen a u.si grad(u)= 0, o sea, si u no pertenece a ninguna arista---

entonces se dice que u es un nodo aislado.

Un camino P de longitud n desde un nodo u se define como la secuencia de n +1 nodos.

P=( v 0 i , v 1 i , v 2 i , . . . . v m )

Tal que u =v0i, v1, es adyacente a vi-1 para i=1,2,…n ; y vn=v . El camino P se dice que es

cerrado si v0 =vn .El camino P se dice que es simple si todos los nodos son distintos, a

excepción de v0 que puede ser igual a vn ; es decir , P es simple si los nodos v0, v1……….vn-1…

son distintos y los nodos v1, v2……….vn son distintos. Un ciclo es un camino simple cerrado

de longitud 3 o mas . Un ciclo de longitud k se llama k-ciclo.

Un grafo G se dice que es conexo si existe un camino entre cualesquiera dos de sus nodos.

Mostraremos en el problema 8.18 que si existe un camino P desde un nodo u a un nodo v,

entonces eliminando las aristas innecesarias, se puede obtener un camino simple Q de u a v,

de acuerdo con esto podemos establecer la siguiente proposición.

Proposición 8.1.-Un grafo G es conexo si y sólo si existe un camino simple entre

cualesquiera dos nodos de G.

Se dice que un grafo G es completo si cada nodo u de G es adyacente a todos los demás

nodos de G claramente, un grafo así es conexo, un grafo completo de n nodos tendrá n(n-

1)2 aristas.

Un grafo conexo T sin ciclos se llama grafo árbol o árbol libre o simplemente árbol. Esto

significa en particular, que existe un único camino simple P entre cada dos nodos u y e de

T (problema 8.18) mas aún, si T es un árbol de finito de m nodos, entonces T tendrá m -1

aristas (problema 8.20).

Un grafo G se dice que esta etiquetado si sus aristas tiene datos asignados. En particular,

se dice que G tiene peso si cada arista e de G tiene asignado un valor numérico no

negativo w(e) llamado peso o longitud de e. En ese caso, a cada camino P de G se le

asigna un peso o una longitud que es la suma de lo pesos de las aristas que constituyen el

camino P. si no se da otra información sobre pesos, asumiremos que cada grafo G tiene

peso pero de forma que los pesos w(e) de cada arista e de G es igual a 1.

La definición de un grafo puede ser generalizada si permitimos lo siguiente:

(1) .- Aristas múltiples. Dos aristas e y e distintas se llama aristas múltiples si conectan los

mismos extremos, o sea, si e[u,v] y e=[u.v].

(2) .- Bucles. Una arista

...