Definici\u00f3n y ejemplos<\/strong><\/p>\n 1- Un grafo simple G = (V, A) (grafo simple dirigido, respectivamente) diremos que es un grafo ponderado<\/strong> si tiene asociado una funci\u00f3n W: A -> R llamada funci\u00f3n de ponderaci\u00f3n<\/strong>.<\/p>\n La imagen de cada arista (arco, respectivamente) determinada por los v\u00e9rtices vi<\/sub> y vj<\/sub> la llamaremos peso <\/strong>de la arista (arco) y lo denotaremos por wij<\/sub>.<\/p>\n 2- Sea G = (V, A) un grafo ponderado finito tal que V = {v1, \u2026, vn}. Llamaremos matriz de peso del grafo G a la siguiente matriz de orden n x n<\/p>\n 3- En un grafo ponderado llamamos peso de un camino a la suma de los pesos de las aristas (arcos respectivamente) que lo forman.<\/p>\n 4- En un grafo ponderado llamamos camino m\u00e1s corto entre dos v\u00e9rtices dados al camino de peso m\u00ednimo entre dichos v\u00e9rtices.<\/p>\n 5- En un grafo ponderado llamaremos camino m\u00e1s largo o camino cr\u00edtico entre dos v\u00e9rtices al camino de peso m\u00e1ximo entre dichos v\u00e9rtices.<\/p>\n Como siempre la teor\u00eda est\u00e1 muy bien para quien la entienda, aqu\u00ed va un ejemplo que espero que os ayude m\u00e1s:<\/p>\n EJEMPLO<\/p>\n Caminos\u00a0 m\u00e1s cortos<\/strong><\/p>\n Supondremos\u00a0 que los pesos asociados a los arcos son todos no negativos y que el grafo es dirigido. Supondremos adem\u00e1s que los v\u00e9rtices del grafo est\u00e1n numeradores de 1 a n, de forma que wij<\/sub> representa el peso del arco (i, j) y que el v\u00e9rtice 1 es el origen del camino. Adem\u00e1s uj<\/sub> denotar\u00e1 el peso del camino m\u00e1s corto de 1 a j.<\/p>\n Dicho de otra forma, vamos a suponer que el peso es siempre positivo y que el grafo es dirigido, adem\u00e1s numeraremos los v\u00e9rtices del grafo de 1 a n.<\/p>\n Adem\u00e1s debemos saber que cada secci\u00f3n a su vez es el camino m\u00e1s corto que se puede considerar. Esto viene demostrado por el siguiente teorema.<\/p>\n Teorema<\/strong><\/p>\n Sea 1, \u2026., k, \u2026..,j un camino m\u00e1s corto entre los v\u00e9rtices 1 y j de un grafo ponderado G. Entonces las secciones de este camino 1, \u2026., k y k, \u2026., j son los caminos m\u00e1s cortos entre los v\u00e9rtices respectivos.<\/p>\n Tenemos pues que si tenemos un camino de 1 a 3 pasando por 2, podemos considerar que el camino de 1 a 2 y el camino de 2 a 3 son los caminos m\u00e1s cortos tambi\u00e9n de las respectivas secciones.<\/p>\n Corolario<\/strong><\/p>\n Supongamos que en un grafo ponderado tenemos un camino m\u00e1s corto entre los v\u00e9rtices 1 y j. Sea k el v\u00e9rtice inmediatamente anterior a j en ese camino. Entonces la secci\u00f3n de este camino desde 1 a k es el camino m\u00e1s corto entre estos dos v\u00e9rtices. Adem\u00e1s se cumple que:<\/p>\n uj<\/sub> = uk<\/sub> + wkj<\/sub><\/p>\n Con esto y las ecuaciones de Bellman podemos calcular el camino m\u00e1s corto:<\/p>\n Ecuaciones de Bellman<\/strong><\/p>\n![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2011\/01\/Sin-t\u00edtulo.jpg\")
<\/a><\/p>\n<\/a><\/p>\n
![](\"..\/..\/romulo\/files\/2010\/12\/Sin-t%C3%ADtulo-221.jpg\"){kind=link}