Grafos
Un grafo es un conjunto, no vaco, de objetos llamados vrtices (o nodos) y una
seleccin de pares de vrtices, llamados aristas (arcs en ingls) que pueden
ser orientados o no. Tpicamente, un grafo se representa mediante una serie de
puntos (los vrtices) conectados por lneas (las aristas).
Definicin de grafo dirigido
Un grafo en el cual toda arista es dirigida se denominar "digrafo" o bien "grafo
dirigido". Un grafo dirigido o dgrafo consiste de un conjunto de vrtices V y un
conjunto
de
arcos
A.
Los vrtices se denominan nodos o puntos; los arcos tambin se conocen
como aristas o lneas dirigidas que representan que entre un par de vrtices
existe
una
relacin
unvoca.
Un
grafo
dirigido.
Un grafo dirigido o digrafo es un tipo de grafo en el cual el conjunto de los
vrtices tiene una direccin definida , a diferencia del grafo generalizado, en el
cual la direccin puede estar especificada o no.
V={v1,v2,v3,v4}
E={(v1,v2),(v2,v2),(v2,v3),(v3,v1),(v3,v4),
(v4,v3)}
Implementacin de grafos.
Diferentes implementaciones del tipo grafo: una forma acotada (con una matriz de
adyacencias) y dos no acotadas (con listas y multilistas de adyacencia).
Implementacin mediante matrices de adyacencia. Con la matriz de adyacencia, los
arcos de un grafo G = {N, A}se representan como elementos de una matriz n n,
donde n es Card(N).
Para un grafo no etiquetado, el elemento (i, j) de la matriz es 1 (o VERDADERO) si el
arco (i, j) pertenece a A. Si el arco no pertenece, el elemento valdr 0 (o FALSO). Si el
grafo es etiquetado, se sustituyen los 1s por el valor de las etiquetas y los 0s por un
valor distinguido ().
CONST
MAXNODOS = (* Mximo nmero de nodos *)
TYPE
GRAFO = POINTER TO ESTRUCTURA;
ARCO = RECORD
existe : BOOLEAN;
peso : CARDINAL;
END;
NODO = [1.. MAXNODOS]
MATRIZ = ARRAY [NODO, NODO] OF ARCO;
ESTRUCTURA = RECORD
ult_lleno: [0 .. MAXNODOS]
matriz: MATRIZ;
END;
Operaciones bsicas de los grafos
En los grafos, como en todas las estructuras de datos, las dos operaciones
bsicas son insertar y borrar. En este caso, cada una de ellas se desdobla en
dos, para insertar/eliminar vrtices e insertar/eliminar aristas.
Insertar vrtice
La operacin de insercin de un nuevo vrtice es una operacin muy sencilla,
nicamente consiste en aadir una nueva entrada en la tabla de vrtices
(estructura de datos que almacena los vrtices) para el nuevo nodo. A partir de
ese momento el grafo tendr un vrtice ms, inicialmente aislado, ya que
ninguna arista llegar a l.
Insertar arista
Esta operacin es tambin muy sencilla. Cuando se inserte una nueva arista en
el grafo, habr que aadir un nuevo nodo a la lista de adyacencia (lista que
almacena los nodos a los que un vrtice puede acceder mediante una arista)
del nodo origen, as si se aade la arista (A,C), se deber incluir en la lista de
adyacencia de A el vrtice C como nuevo destino.
Eliminar vrtice
Esta operacin es inversa a la insercin de vrtice. En este caso el
procedimiento a realizar es la eliminacin de la tabla de vrtices del vrtice en
s. A continuacin habr que eliminar las aristas que tuviesen al vrtice borrado
como origen o destino.
Eliminar arista
Mediante esta operacin se borra un arco del grafo. Para llevar a cabo esta
accin es necesario eliminar de la lista de adyacencia del nodo origen el nodo
correspondiente al nodo destino.
Otras operaciones
Las operaciones adicionales que puede incluir un grafo son muy variadas.
Adems de las clsicas de bsqueda de un elemento o recorrido del grafo,
tambin podemos encontrarnos con ejecucin de algoritmos que busquen
caminos ms cortos entre dos vrtices, o recorridos del grafo que ejecuten
alguna operacin sobre todos los vrtices visitados, por citar algunas
operaciones de las ms usuales.
Representacin de grafos dirigidos
Hay por lo menos dos maneras evidentes de representar un grafo en un
computador, utilizando la notacin pseudoformal propuesta en [2]. La primera
utiliza lo que se conoce como una matriz de adyacencia, a saber:
CLASE Grafo
Privado: Arreglo de Nodos de [1..N];
Arreglo de logico MatrizDeAdyacencia de [1..N][1..N];
Publico:
# Todas las operaciones aqu
Un valor verdadero en la posicin (i,j) de la matriz indica que hay una arista que
conecta al nodo i con el nodo j. Para representar un grafo pesado se puede
cambiar la matriz de adyacencia de lgicos a una matriz de registros, siendo el
peso un campo del registro.
