DE SISTEMAS Y COMPUTACIÓN
Enviado por legf86 • 20 de Octubre de 2013 • Síntesis • 14.658 Palabras (59 Páginas) • 220 Visitas
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)
...