Grafos

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
B
A

arco

D
C

E
nodo

F

G

H

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 quelos 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
nodosrestantes.
*.-El camino de un nodo así mismo se llama ciclo.

Representacion
de grafos

{

Secuencial

Enlazada

Matriz de
{adyacencia

Listas
{ encadenadas

MATRIZ DE ADYACENCIA
A B C D
A 0 1 0 0
B

D

A

C

B 0 0 1 0
C 1 0 0 1
D 0 0 0 0
A B C D

B

D

600

600

A

C
1000

300

A
B
C
D

0

600

100
0

0

600

0

600

0

100
0

6000

300

0

0

300

0

*.-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) Estamí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 ypresentaremos 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 tantoadvertimos 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 0i ,v 1i ,v 2i ,....vm)
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…...