Problem Detail: This problem is from the book [1]. In case of being closed as a duplication of that in [2], I first make a defense:
- The accepted answer at [2] is still in dispute.
- The proof given by @eh9 is based on Kruskal’s algorithm.
- I am seeking for a proof independent of any MST algorithms.
Problem: Let $T$ be an MST of graph $G$. Given a connected subgraph $H$ of $G$, show that $T cap H$ is contained in some MST of $H$.
My partial trial is by contradiction:
Suppose that $T cap H$ is not contained in any MST of $H$. That is to say, for any MST of $H$ (denoted $MST_{H}$), there exists an edge $e$ such that $e in T cap H$, and however, $e notin MST_{H}$.
Now we can add $e$ to $MST_{H}$ to get $MST_{H} + {e}$ which contains a cycle (denoted $C$).
- Because $MST_{H}$ is a minimum spanning tree of $H$ and $e$ is not in $MST_{H}$, we have that every other edge $e’$ than $e$ in the cycle $C$ has weight no greater than that of $e$ (i.e., $forall e’ in C, e’ neq e. w(e’) le w(e)$).
- There exists at lease one edge (denoted $e”$) in $C$ other than $e$ which is not in $T$. Otherwise, $T$ contains the cycle $C$.
Now we have $w(e”) le w(e)$ and $e in T land e” notin T$, $ldots$
I failed to continue…
Asked By : hengxin
Answered By : Mahmoud A.
If we construct a spanning tree for $H$ containing $T_G cap H$ then your approach leads to a trivial contradiction (meaning that your initial assumption is automatically contradicted by any direct proof). Here is the construction of a MST for $H$ from a MST for $G$: Let $MST_Psi$ be the set of minimum spanning trees for the graph $Psi$. The spanning tree $T_Psi$ is not minimum for $Psi$ if there is another spanning tree for $Psi$ with smaller weight. Start with $T_H in MST_H, T_G in MST_G$. While there is an edge $e in T_G cap H$ such that $e notin T_H$ do: 1- Find $e$ and add it to $T_H$ to create a cycle. For every other edge $e’ notin T_G$ in the cycle we have $w(e’) = w(e)$ (because if $w(e)>w(e’)$ then replacing $e$ with $e’$ in $T_G$ gives a better ST for $G$, thereby $T_G$ is not minimum for $G$. If $w(e)<w(e’)$ then since $e notin T_H$ we can replace $e’$ with $e$ in $T_H$ to obtain a better spanning tree for $H$ contradicting $T_H$ being MST for $H$). Let $e” notin T_G$ be one of these edges. We can safely replace $e”$ with $e$ in order to obtain $T’_H = T_H setminus {e”} cup {e} in MST_H$. 2- Rename $T’_H$ to $T_H$. EndWhile After the loop we have $T_G cap H subseteq T_H$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/18867
