adyacencia en un grafo

describe el almacenamiento de un grafo en la memoria del pc

1. ALMACENAMIENTO DE UN GRAFO EN LA MEMORIA DEL PC PRESENTADO A: INGENIERO: JOSUE GUILLERMO CUCAITA MURCIA. PRESENTADO POR: YEILER STEVEN CORTES. RODRIGUEZ ALVARADO CRISTIAN CAMILO. FACULTAD DE SISTEMAS. TEORIA DE GRAFOS. UNIVERSIDAD COOPERATIVVA DE COLOMBIA VILLAVICENCIO META.

2. GRAFOS Los grafos no son más que la versión general de un árbol, es decir cualquier nodo de un grafo puede apuntar a cualquier otro nodo de éste (incluso a él mismo). Este tipo de estructuras de datos tienen una característica que lo diferencia de las demás estructuras de datos, los grafos se usan para almacenar datos que están relacionados de alguna manera (relaciones de parentesco , puestos de trabajo, ...); por esta razón se puede decir que los grafos representan la estructura real de un problema.

3. Terminología de grafos: Adyacencia : Se dice que dos vértices son adyacentes si entre ellos hay un enlace directo. Vecindad : Conjunto de vértices adyacentes a otro. Camino : Conjunto de vértices que hay que recorrer para llegar desde un nodo origen hasta un nodo destino. Grafo conectado : Aquél que tiene camino directo entre todos los nodos. Grafo dirigido : Aquél cuyos enlaces son unidireccionales e indican hacia donde están dirigidos.

4. FORMAS DE ALMACENAR UN GRAFO Existen varias formas de almacenar estas estructuras en memoria : COMO LISTA DE ADYACENCIA COMO MATRIZ DE ADYACENCIA COMO MATRIZ DE INCIDENCIA

5. LISTA DE ADYACENCIA Para almacenar un grafo en una lista de adyacencia, debemos trabajar con un arreglo de listas. Cada una de estas listas almacena los adjuntos a un vértice dado, comenzando por los vértices de más arriba y los de más a la izquierda como orden de prioridad. Por ejemplo una lista tendrá almacenados todos los adjuntos al vértice E; otra lista tendrá almacenados todos los adjuntos al vértice I, etc. A E D B F C B A C D E F D B C D E B A C

6. Representación en memoria de un grafo: Matriz de Adyacencia : Usamos una matriz cuadrada, en la que las filas representan los nodos origen, y las columnas, los nodos destinos. De esta forma, cada intersección entre fila y columna contiene un valor booleano que indica si hay o no conexión entre los nodos a los que se refiere. Si se trata de un grafo con pesos, en lugar de usar valores booleanos, usaremos los propios pesos de cada enlace y en caso de que no exista conexión entre dos nodos, rellenaremos esa casilla con un valor que represente un coste ∞, es decir, con el valor Natural’Last .

7. Matriz de Adyacencia : A E D B F C 1 1 1 1 1 1 1 1 Dígrafo. Matriz de adyacencia A B C D E F A B C D E F

8. Matriz De Incidencia Esta estructura es aplicable para los dígrafos. En la matriz de incidencia cada fila representa a cada uno de los nodos del grafo, y las columnas los posibles arcos de dicho grafo; en la casilla M [i ,j ], aparecerá un 1 cuando el nodo de la fila i es inicial, y un -1, cuando el nodo i es final. En la siguiente figura aparece un dígrafo y su correspondiente matriz de incidencia:

9. Matriz De Incidencia