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 C F
arco
D
nodo
E
G
H
Si los pares de nodos en los arcos dirigidos, el grafo sedenomina 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 sedenomina 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
Matriz de {adyacencia
Enlazada
Listas { encadenadas
MATRIZ DE ADYACENCIA
A B CD A 0 1 0 0 B A C D B 0 0 1 0 C 1 0 0 1 D 0 0 0 0 A B C D
600 600 300
B A
1000
D C A B C D
0
600
100 0
0 0 300 0
600
100 0
0 600 0
600 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 nodoses 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 datosno 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ÍADE 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 puntoso 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 artistasque 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 nodosson 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…