********GRAFO ETIQUETADO********

1.Un grafo simple G = (V, A) (grafo simple dirigido, respectivamente) diremos que es un grafo ponderado si tiene asociado una función W: A -> R llamada función de ponderación.

La imagen de cada arista (arco, respectivamente) determinada por los vértices vi y vj la llamaremos peso de la arista (b) y lo denotaremos por Wij.

2. Sea G = (V, A) un grafo ponderado finito tal que V = {v1….vn}. Llamaremos matriz de peso del grafo G a la siguiente matriz de orden n x n:

Es decir, que pondremos el valor del peso cuando lo tenga, y el símbolo infinito cuando no exista tal valor.

3. En un grafo ponderado llamamos peso de un camino a la suma de los pesos de las aristas (o arcos) que lo forman.

4. En un gafo ponderado llamamos camino más corto entre dos vértices dados al camino de peso mínimo entre dichos vértices.

5. En un grafo ponderado llamaremos camino más largo o camino critico entre dos vértices al camino de peso máximo entre dichos vértices.

ü En grafo no etiquetado los arcos no tienen etiquetas.

ü En el caso de un grafo que representa el sentido del tráfico se pueden etiquetar los arcos con el nombre de las calles.