Grafos Ponderados

GRAFOS PONDERADOS
En muchos casos, es preciso atribuir a cada arista un número específico, llamadovaluación, ponderación o coste según el contexto, y seobtiene así un grafo valuado o ponderado.
Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre sí por carreteras; suinterés previsible será minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos). El grafo correspondiente tendrá como vértices las ciudades,como aristas las carreteras y la valuación será la distancia entre ellas.
Definiciones:
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 queV = {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ímboloinfinito cuando no exista tal valor.
3. En un grafo ponderado llamamos peso de un camino a la suma de lospesos de las aristas (o arcos) que loforman.
4. En un gafo ponderado llamamos camino mas corto entre dos vértices dados al camino de peso mínimo entre dichos vértices.
5. En un grafoponderado llamaremos camino mas largo o camino criticoentre dos vértices al camino de peso máximo entre dichos vértices.

Ejemplo de grafo ponderado