Grafos

GRAFOS

Es un conjunto de nodos o vértice (V) y conjunto de aristas (E) donde cada arista relaciona a un par de nodos.

Su estructura algebraica es:

 (G=V,E)

«Tipos de grafos»

Grafos Dirigidos: 

G Consiste de un conjunto V de vértices y un conjunto E al conjunto de aristas del grafo.

Los vértices de este grafo se pueden usar para representar objetos y los enlaces relaciones entre objetos.

Ejemplo:

Los vértices pueden representen unas ciudades y enlaces los vuelos aéreos entre estas ciudades.

En la siguiente imagen podemos divisar un enlace el cual es un par ordenado de vértices (V,W) donde V es la cola y la W corresponde a la cabeza de dicho enlace.

V= {A,B,C}

E={(A,C), (B,C), (B,D), (C,D)}

Grafos No Dirigidos: 

Sea G un grafo no d donde G=(V,E) y V corresonpde al conjunto de vértices y E al conjunto de aristas del grafo

La diferencia con el grafo dirigido es que cada arista E es un par no ordenado de vértices. (Si (V,W) es un 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)}

COSTOS

Los enlaces tanto para los grafos no dirigidos y los dirigidos tiene un costo, por lo que son grafos etiquetados

«Costo de grafo Dirigido Etiquetado»

«Costo de grafo no Dirigido Etiquetado»