Un grafo simple G = (V,A) diremos que es un grafo ponderado si cada arista/arco tiene un peso (puede ser negativo) denotado por wij.
Cada arco o arista tiene un peso, por ejemplo en el grafo dirigido Wbd = 21.
Grafo A / Grafo B
La matriz de peso contendrá el peso de los arcos/aristas, si el vértice x no es adyacente con y en la matriz pondremos Wxy = ∞
Las matrices de pesos de los grafos anteriores son:
En un grafo ponderado llamamos peso de un camino a la suma de los pesos de las aristas/arcos que lo forman.
En un grafo ponderado llamamos camino mas corto entre dos vértices al camino de menor peso entre los vértices.
En un grafo ponderado llamamos camino crítico entre dos vértices al camino de peso máximo entre los vértices.
Ejemplo:
Peso del camino A,C
Wab + Wbc = 4
Camino más corto A, F
Camino críticio A, F
Wab + Wbc + Wcd + Wdf = 10 (mayor peso)
Wae + Wef = 8 (menor peso)
Comments
4 responses to “Capítulo 16 “Grafos Ponderados””
Thank you for taking this possiblity to speak about this, I am strongly about it and I benefit from garden greenhouse structures this subject. When possible, when you gain data, please update this blog with new information. I have discovered it extremely useful.
That is extremely interesting, You’re a very expert blogger. I have joined your feed and stay up for hunting for extra of your spectacular submit. Also, I have shared your site in my social networks!
tsssss no me cansare de decir que tus fotos son algo inigualable por favor nunca dejes de tomar fotos eres LA MEJOR !!!
OMG! Jake has become quite a stunner!