Que es un grafo

¿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, wque pertenecen a V y E es un conjunto m de aristas que consta de dos elementos de V.

 

  • GRAFO DIRIGIDO:
Un GRAFO  DIRIGIDO G consiste de un conjunto V de vértices  y un conjunto E al conjunto de aristas  del grafo.
 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.
.
  • 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).

MATRIZ ADYACENTE

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

LISTA ADYACENTE

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.

ARREGLOS PARA LA LISTA DE ADYACENCIA

Se utilizan los arreglos para implementar la Lista de Adyacencia: