¿Que es un Grafo?

Un grafo es una estructura de datos, específicamente es un tipo abstracto de datos (TAD), que consiste en un grupo de nodos a los cuales también le podemos llamar vértices y un grupo de aristas que establecen relaciones entre las vértices. El concepto de grafo TAD tiene su origen directamente del concepto matemático de grafo.

Se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E las aristas. Un grafo, G, es definido como un par ordenado, G = (V, E), donde V es un conjunto n finito de vértices u, v, w que pertenecen a V y E es un conjunto m de aristas que consta de dos elementos de V.

Le llamamos orden del grafo G a su número de vértices, | V |.

El grado de un vértice o nodo V es igual al número de vértices E que encontramos en él.

Un bucle es una arista que conecta un vértice consigo mismo, es decir, una arista donde el nodo inicial y el nodo final coinciden.

El complemento o inverso de un grafo G = (V,E) es un grafo G’ =(V,E’), con el mismo conjunto de vértices y tal que dos vértices de G’ son adyacentes si y solo si no son adyacentes en G. Para conseguir el complemento de un grafo, debemos completar todas las aristas que faltan para hacerlo completo, y quitar todas las aristas del grafo G original.

Tipos de Grafos.

Los grafos son estructuras de datos no lineales que tienen una naturaleza dinámica, existen dos tipos de grafos, estos son:

• Grafos Dirigidos.
• Grafos No Dirigidos.

Grafos Dirigidos.

1. Un GRAFO  DIRIGIDO G consiste de un conjunto V de vértices  y un conjunto E al conjunto de aristas  del grafo.
2. 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.
3. Un enlace es un par ordenado de vértices (v, w), donde v es la cola y w corresponde a la cabeza del enlace.

Grafos No Dirigidos.

1. 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.
2. 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).

Costos.

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