grafos

Teoria de grafos:

En matematicas y en ciencias de la computacion, estudia las propiedades de los grafos "graficas". un grafo es un conjunto, no vacio, de objetos llamados vetices ( o nodos) y una seleccion de pares de vertices, llamados aristas (edges) que pueden ser oriendos o no. tipicamente, un grafo se representa mediante una serie de puntos (los vertices) conectados por lineas( las aristas).

Estruturas de listas:

• Listas de incidencia- las aristas son representadas por un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas.


• Listas de ayacencia- cada vertice tiene una lista de vertices los cuales son adyacentes a él. Esto causa redundancia en grafos no ( ya que a A existe en la lista de adyacencia de B y viceversa), pero las busquedas son mas rapidas, al costo de almacenamiento exitra. En esta estructura de datos la ideas es asiciar a cada vertice i del grafo una lista que contenga aquellos vertices j que sean adyacentes a él. de esta forma solo resenvara memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudiran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componetes (si /V/=n) donde cada componte a ser uan lista de adyacencia correspondiente a cada uno de los vertces de grafo. Cada elemeto de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habra que añadir un segundo campo para mostrar el valor de la etiqueta.