Teoria de grafos

En matemáticas y en ciencias de la computación, la teoría de grafos (también llamadateoría de las gráficas) estudia las propiedades de los grafos (también llamadasgráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa medianteuna serie de puntos (los vértices) conectados por líneas (las aristas).

Estructuras de datos en la representación de grafos
Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunquefrecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.
Estructura de lista
 lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada parrepresenta una de las aristas.1
 lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra.

En esta estructura de datos la idea es asociar a cada vértice i del grafo una lista que contengatodos aquellos vértices j que sean adyacentes a él. De esta forma sólo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vértices del grafo. Cada elemento dela lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta.
Ejemplo de lista de adyacencia
Estructuras matriciales
Matriz de incidencia
La matriz de incidencia es una matriz binaria (sus elementos sólo pueden ser unos o ceros), que se utiliza como una forma de representarrelacionesbinarias.
Construcción de la matriz a partir de un grafo


Relación binaria descrita mediante una matriz de incidencia, y mediante un grafo.




1. Las columnas de la matriz representan las aristas del grafo.
2. Las filas representan a los distintos nodos.
3. Por cada nodo unido por una arista, ponemos un uno (1) en el lugar correspondiente, y llenamos el resto de las ubicacionescon ceros (0).
En el ejemplo de la figura, si sumamos las cantidades de 1's que hay en cada columna, veremos que hay solo dos. Pero si sumamos las cantidades de unos 1's que hay por cada fila, comprobaremos que los nodos 2, 4 y 5 poseen un valor de 3. Ese valor indica la cantidad de aristas que inciden sobre el nodo.
Comparación con otras representaciones
Existen otras formas de representarrelaciones binarias, como por ejemplo los pares ordenados o los grafos. Cada representación tiene sus virtudes y desventajas.
En particular, la matriz de incidencia es muy utilizada en la programación, porque su naturaleza binaria y matricial calza perfecto con la de los computadores. Sin embargo, a una persona sin conocimientos de computación se le hará mucho más sencillo comprender una relacióndescrita mediante grafos, que mediante matrices de incidencia.
Otra representación matricial para las relaciones binarias es la matriz de adyacencia.
Matriz de adyacencia
La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias
Construcción de la matriz a partir de un grafo
1. Se crea una matriz cero, cuyas columnas y filas representan los...