Teoría de Grafos

Un grafo es un conjunto de nodos o vértices (V) y un conjunto de aristas (E), donde cada arista relaciona a un par de nodos pertenecientes a V.
La estructura algebraica para los grafos es G=(V,E).

Ejemplo de grafos:

Existen diferente tipos de grafos:

Grafo Dirigido:

Un grafo dirigido (G) consiste de un conjunto V de vértices y un conjunto E al conjunto de aristas del grafo a su vez los vértices de un grafo dirigido pueden usarse para representar objetos y los enlaces relaciones entre los objetos, ejemplo de ello que los vértices pueden representar ciudades y los enlaces vuelos aéreos entre ciudades también un enlace es un par ordenado de
vértices (v, w), donde v es la cola y w corresponde a la cabeza del enlace.

Ejemplo:

Grafo no Dirigido:

Sea G un Grafo no Dirigido, donde G=(V,E) y V corresponde al conjunto de vértices y E al conjunto de aristas del grafo.
Un Grafo no Dirigido se diferencia de un Grafo Dirigido debido a que cada arista en E es un par no ordenado de vértices. Si (v,w) es una arista no dirigida (v,w) = (w,v).

Ejemplo:

Costos:

Los enlaces tanto para los grafos Dirigidos como No Dirigidos tienen un costo (valor), por lo tanto son grafos etiquetados.

Ejemplo:

Representación de los grafos

Un grafo Dirigido o No-Dirigido se puede representar mediante:

Matriz de Adyacencia:

La Matriz Adyacente A de un Grafo G=(V,E) tiene V*V elementos y se define como:

Ejemplo:

VENTAJA:
Se puede determinar en un tiempo fijo y constante si un enlace(arco) pertenece o no al grafo.

DESVENTAJAS:
Se requiere un almacenamiento |v|*|v|. Es decir O(n2).

Lista de Adyacencia:

La lista de adyacencia para un vértice v es una lista enlazada de todos los vértices w adyacentes a v. Un grafo puede ser representado por |v| listas de adyacencias, una para cada vértice.

Ejemplo:

VENTAJAS:
La lista de adyacencia requiere un espacio proporcional a la suma del número de vértices más el número de enlaces(arcos). Hace buen uso de la memoria.

DESVENTAJAS:
La representación con lista de adyacencia es que puede llevar un tiempo O(n) determinar si existe un arco del vértice i al vértice j, ya que pueden haber O(n) vértices en la lista de adyacencia. Para el vértice i.

Arreglos para la Lista de Adyacencia:

Se utilizan los arreglos para implementar la Lista de Adyacencia.