CODEWITHSUNDEEP
algorithmdata-structuresgraph-algorithmminimum-spanning-tree
Yao Yingjie
Yao Yingjie

Reputation: 468

How to prove there always exists a minimax path completely on the MST

A minimax path in an undirected graph is a path between two vertices v, w that minimizes the maximum weight of the edges on the path.

Let T be the minimum spanning tree of a given graph G=(V,E). How can I prove that, for any pair of vertices v, w in V, there always exists a minimax path between v and w that is completely on T.

I have tried to assume there is no minimax path completely on T, but I don't know how to get a contradiction.

Upvotes: 3

Views: 5594

Answers (2)

trincot
trincot

Reputation: 349946

Assume there exists a minimax path P between vertices u and v that is not completely on the minimum spanning tree T.

This means there is an edge A(p, q) in P that is not in T.

Let Q be the path in T from p to q.

Let B be an edge with the greatest weight in Q (in the imaged graph the length of the edge represents its weight):

enter image description here

                    T is marked in green
                    P = (u,p,q,v)

There are now 2 conditions to consider:

  1. weight(B) > weight(A): In that case T is not a minimum spanning tree. If you would remove B from T and add A instead, you would still have a spanning tree, but its total weight would have decreased. As this is a contradiction (T is given as being a minimum spanning tree), the only possibility left is:

  2. weight(B) <= weight(A): In that case you could remove A from P and add the edges from Q to it instead, and it would still be a minimax path, as we did not include an edge with a greater weight than that was already on that path before.

    Note that this replacement will make the minimax path longer, but that is not an issue. There can be several paths between two vertices that all minimise the maximum edge weight -- there is no requirement that the minimax path be the shortest of those.

For every edge A on a minimax path that is not in T, an edge replacement can be done as described in point 2, thereby creating a minimax path that will be completely on T.

Upvotes: 5

mcdowella
mcdowella

Reputation: 19601

Suppose that there is a minimax path outside the minimum spanning tree that does better than the path on the minimum spanning tree. Remove the most costly edge on the minimum spanning tree path from the tree, splitting the graph into two connected components. You can get from one component to another using the minimax path. As you go along this path, there must be one edge that leaves one of the components and enters the other component. Add this edge to the minimum spanning tree. The graph is now connected again and the total cost of the minimum spanning tree has reduced, because every edge on the minimax path had a cost less than that of the most costly edge on the minimum spanning tree. So we have a contradiction and no such minimax path can exist.

Upvotes: 4

Related Questions