IWishYourNameCouldBeHere's blog

By IWishYourNameCouldBeHere, history, 3 years ago, In English

Can we say that in the minimum spanning tree the maximum weight edge on the path between any pair of vertices is minimized?

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it +37 Vote: I do not like it

imagine you have a mst,

now we will prove it by contradiction,

assume that the max wt is not minimized, so there must be another edge which after adding, creates cycle, and we can remove the edge as, it will be part of cycle, so the new tree has less total weight, which contradicts definition of mst.

»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

(i started writing this when there were no other comments, so might as well post it) I think this is true. Let's consider Kruskal's algorithm that builds the MST for a connected graph $$$G$$$ with $$$n$$$ nodes and $$$m$$$ edges (all edge weights are distinct for simplicity). Let $$$G_i$$$ for $$$0<=i<=m$$$ denote the subgraph at stage $$$i$$$, that is, $$$i$$$ smallest edges have been looked at. Our only concern are edges that are not in $$$G_i$$$. Such an edge $$$e_i$$$ satisfies "$$$e_i$$$ connects two points in the same connected component (CC) of $$$G_{i-1} (= G_i)$$$". Now consider any path from $$$u$$$ to $$$v$$$ in $$$G_m$$$.

case 1: $$$u$$$ and $$$v$$$ belong to the same CC of $$$G_i$$$. Thus, the path from $$$u$$$ to $$$v$$$ in $$$G_m$$$ has maximum weight lesser than $$$w_{e_i}$$$ (The same CC of $$$G_i$$$ has edges smaller than $$$e_i$$$). Thus, we already have a path with maximum edge weight lesser than $$$w_{e_i}$$$. Thus, $$$e_i$$$ cannot cause an issue.

case 2: $$$u$$$ and $$$v$$$ belong to different CCs of $$$G_i$$$. If there is a path from $$$u$$$ to $$$v$$$ that goes through $$$e_i$$$, then it must cross two different CCs in $$$G_i$$$. Thus, it must have another edge that has weight greater than $$$e_i$$$ (Different CCs of $$$G_i$$$ will be connected by later edges with greater weights). Thus, $$$e_i$$$ is not the maximum weight on any path from $$$u$$$ to $$$v$$$ in $$$G$$$. Thus, it cannot cause an issue.