patternMinor
Minimum spanning tree and its connected subgraph
Viewed 0 times
minimumitsconnectedandsubgraphspanningtree
Problem
This problem is from the book [1]. In case of being closed as a duplication of that in [2], I first make a defense:
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$).
Now we have $w(e'') \le w(e)$ and $e \in T \land e'' \notin T$, $\ldots$
I failed to continue...
- The accepted answer at [2] is still in dispute.
- The proof given by
@eh9is 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...
- Algorithms, Chapter 5: Greedy algorithms
- "Minimum Spanning tree subgraph"@StackOverflow
Solution
Flaws in the accepted answer: When I re-read the accepted answer given by @Mahmoud A. today, I find flaws in it.
Consider the figures for an example:
In this example, $e = CE$. In figure (5), the edge $CD$ in the cycle created by adding edge $e = CE$ into $T_H$ is not in $T_G$ shown in figure (2), but we have $w(CD)w(e)$, $T_H + \{ e \} - \{ e' \}$ has smaller weight than $T_H$.
-
1.2 Let $e = (u,v)$. Remove $e$ from $T_G$. Then vertices $u$ and $v$ are separated into two different connected components, denoted by $U \ni u$ and $V \ni v$, of $T_G$. Because $T_H$ is an MST of $H$ (which includes vertices $u$ and $v$) and $e \notin T_H$, there must be an edge $e'' \in C$ which connects the two components $U$ and $V$ again.
We claim that $w(e'') = w(e)$. In 1.1, we have proved that $w(e'') \le w(e)$ (replacing $e'$ there by $e''$). If $w(e'')
-
1.3 According to 1.1 and 1.2 above, there are an edge $e'' \in C$ such that $e'' \neq e \land w(e'') = w(e)$. We replace $e''$ with $e$ in $T_H$ to obtain $T'_H = T_H - \{ e'' \} + \{ e \} \in MST_H$.
Since $e'' \notin T_{G} \cap H$ and $e \in T_{G} \cap H$, $T'_H$ contains one more common edge with $T_{G} \cap H$ than $T_H$ does.
-
Rename $T'_H$ to $T_H$
EndWhile
After the loop we have $T_{G} \cap H \subseteq T_H$.
Consider the figures for an example:
In this example, $e = CE$. In figure (5), the edge $CD$ in the cycle created by adding edge $e = CE$ into $T_H$ is not in $T_G$ shown in figure (2), but we have $w(CD)w(e)$, $T_H + \{ e \} - \{ e' \}$ has smaller weight than $T_H$.
-
1.2 Let $e = (u,v)$. Remove $e$ from $T_G$. Then vertices $u$ and $v$ are separated into two different connected components, denoted by $U \ni u$ and $V \ni v$, of $T_G$. Because $T_H$ is an MST of $H$ (which includes vertices $u$ and $v$) and $e \notin T_H$, there must be an edge $e'' \in C$ which connects the two components $U$ and $V$ again.
We claim that $w(e'') = w(e)$. In 1.1, we have proved that $w(e'') \le w(e)$ (replacing $e'$ there by $e''$). If $w(e'')
-
1.3 According to 1.1 and 1.2 above, there are an edge $e'' \in C$ such that $e'' \neq e \land w(e'') = w(e)$. We replace $e''$ with $e$ in $T_H$ to obtain $T'_H = T_H - \{ e'' \} + \{ e \} \in MST_H$.
Since $e'' \notin T_{G} \cap H$ and $e \in T_{G} \cap H$, $T'_H$ contains one more common edge with $T_{G} \cap H$ than $T_H$ does.
-
Rename $T'_H$ to $T_H$
EndWhile
After the loop we have $T_{G} \cap H \subseteq T_H$.
Context
StackExchange Computer Science Q#18867, answer score: 6
Revisions (0)
No revisions yet.