Lectura De Archivos Con Registros De Longitud Fija Y La Escritura De Archivos Con Registros De Longitud Varia

GRAFOS

1. Definiciones básicas:

Un grafo es la representación por medio de conjuntos de relaciones arbitrarias entre objetos. Existen dos tipos de grafos según la relación entre los objetos sea unívoca o biunívoca. Los primeros forman los grafos dirigidos o dígrafos y los segundos los grafos no dirigidos o simplemente grafos. En la mayor parte de los algoritmos que serán nuestro objeto de estudio se hace referencia a la termología básica que se propone a continuación. Dicha terminología; por desgracia, no es estándar y puede llegar a variar en los distintos textos que existen en la materia. Cuando exista ambigüedad se harán las aclaraciones según sea necesario.

Un grafo dirigido o dígrafo consiste de un conjunto de vértices V y un conjunto de arcos A. Los vértices se denominan nodos o puntos; los arcos también se conocen como aristas o líneas dirigidas que representan que entre un par de vértices existe una relación unívoca aRb pero no bRa. De modo que los arcos se representan comúnmente por medio de pares ordenados (a,b), donde se dice que a es la cabeza y b la cola del arco y a menudo se representa también por medio de una flecha, tal como se muestra en la figura 1.

Figura 1 Grafo dirigido

donde , y tal que . En dicho grafo se entiende que y en muchos casos solo existe uno de los pares de vértices.

Un vértice que solo tiene arcos saliendo de él se denomina fuente y un vértice que solo tiene arcos dirigidos hacia él se denomina sumidero. Dicha nomenclatura es importante cuando los dígrafos se usan para resolver problemas de flujos.

Un grafo no dirigido, o grafo, al igual que un dígrafo consiste de un conjunto de vértices V y un conjunto de arcos A. La diferencia consiste en que la existencia de aRb presupone que bRa también existe y además que son iguales. De este modo es indistinto hablar del arco (a,b) o (b,a), tampoco tiene sentido hablar de la cabeza o la cola del arco. Los grafos representan como lo indica la figura 2, donde los círculos representan los vértices y las líneas representan los arcos.

Figura 2 Grafo no dirigido

donde , y tal que . En dicho grafo se entiende que y además , donde ambos pares de vértices representan el mismo arco.

Existen además grafos en donde los arcos tienen asociado algún valor en cuyo caso hablamos de grafos ponderados y ahora se representan los arcos como tripletas. Sigue existiendo la información de los vértices unidos por dicho arco además de la información del peso de dicho arco. Así pues el arco se representa como donde son el origen y destino y es el peso respectivamente.

Un nodo b se dice que es adyacente al nodo a si existe el arco (a, b), tómese en cuenta que para un grafo no dirigido necesariamente a es también adyacente a b. Esto no ocurre en los grafos dirigidos donde la existencia de (a, b) no implica que (b, a) también existe. Este concepto es de particular importancia dado que los grafos suelen representarse en la computadora por medio de listas o matrices de adyacencias.

Un arco (a,b) incide en el nodo b, de igual modo en grafo no dirigido dicho arco también incide en el nodo a debido a que también existe (b, a). El número de arcos que inciden en un nodo le otorga el grado a dicho nodo. El nodo con mayor grado en el grafo le indica el grado de dicho grafo. También se acostumbra representar a un grafo por medio de listas o matrices de incidencias.

Existen otras definiciones que son útiles para explicar el funcionamiento de un algoritmo en particular, se definirán los conceptos en su momento.

2. Métodos de representación en computadora

Tal como se adelanto en el apartado anterior, existen varias formas de representar un grafo en la computadora y cada una tiene sus ventajas y desventajas. Mostraremos las más comunes y la forma de implementarlas.

La primera forma es por medio de una matriz de adyacencias, con este método se tiene una matriz de tamaño nxn, donde n es el numero de vértices o nodos en el grafo. Una forma simple de ver la información guardada en dicha matriz es que los renglones de las mismas representan el origen y las columnas el destino de cada arista o arco en el grafo. Si el grafo es no ponderado se acostumbra poner un cero en el (renglón i, columna j) de la matriz cuando no existe dicho arco y un uno cuando dicho arco existe en el grafo. En el caso de grafos ponderados, se acostumbra poner una bandera (normalmente el valor de infinito) en las posiciones donde no existe un arco y el peso correspondiente en las posiciones donde si existe.

1 2 3 4 5

1 0 1 0 0 1

2 1 0 1 1 1

3 0 1 0 1 0

4 0 1 1 0 1

5 1 1 0 1 0

Figura 3 Grafo no ponderado y su matriz de adyacencia

Debe notarse que para un grafo no dirigido la matriz de adyacencia es simétrica y que la diagonal principal contiene ceros. Esto puede llegar a aprovecharse para ahorrar tiempo en algunos algoritmos. La representación por medio de matriz se prefiere para algoritmos donde el numero de arcos es grande en proporción al numero de vértices. Si sucediera lo contrario se prefiere la representación por medio de listas de adyacencia.

Figura 4 Lista de adyacencia para el grafo de la figura 3

Las estructuras de datos para las dos formas de representación anteriores pueden modelarse en C como sigue:

char grafo[MAX_VERT][MAX_VERT], visitado[MAX_VERT];

void inserta(char i, char j){

grafo[i][j] = grafo[j][i] = 1;

}

void limpia_grafo(){

int i, j;

for(i = 0; i < nvert; i++){

visitado[i] = 0;

for( j = i; j < nvert; j++)

grafo[i][j] =

...