Consider an undirected graph G=(V,E)G=(V,E) where every edge e has a given cost

Question

Consider an undirected graph G=(V,E)G=(V,E) where every edge e has a given cost Ce. Assume that all edge costs are positive and distinct. Let T be a minimum spanning tree of G and P be a shortest path from the vertex s to the vertex t. Now suppose that the cost of every edge of G is increased by 1 (for each edge: Ce=Ce+1). Call this new graph G.

Is T a minimum spanning tree of G?
Is P the shortest s-t path of G?

Consider an undirected graph G (V, E) where every edge e has a given cost ce Assume that all edge costs are positive and distinct. Let T be a minimum spanning tree of G and P be a shortest path from the vertex s to the vertext. Now suppose that the cost of every edge of G is increased by 1 (for each edge: ce ce 1). Call this new graph G Is T a minimum spanning tree of G'? Is Pthe shortest s-t path of G

Explanation / Answer

Solution:

So a graph G(V, E) is given which has distinct edges then this means that the drawn spanning tree will be a unique one.

So if we increase the cost of every edge in G then the achieved graph G' will be a unique graph, This means that the spanning tree achieved from G' will be unique. So we can conclude that T still a MST of G'.

and P will remain as shortest s-t path in G' as well.

But the cost between s-t will increse depending on how many vertices are are in between or how many edges are connecting them.

I hope this helps. Don't forget to give a thumbs up if you like this.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---