Grafos

 Es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas), esta  definida una relación binaria,es decir,G=(V,A) tal que V es un conjunto de objetos a los que denominaremos vértices o nodos y  es una relación binaria a cuyos elementos denominaremos arcos o aristas.

Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica. Su estudio podría dividirse en dos grandes bloques:

• Grafos Dirigidos.
• Grafos no Dirigidos

Grafos Dirigidos

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.

 V={a, b, c, d}

E={(a,c), (a,b), (b,c), (b,d), (c,d)}

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

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

V={a, b, c, d}

E={(a,c),(c,a),(a,b),(b,a) (b,c),(c,b),(b,d),(d,b), (c,d),(d,c)}

Costo

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

Video Explicativo