Proving equivalent definitions for MSTs
-
05-11-2019 - |
题
I am working on the following homework exercise:
Let $G = (V,E)$ be an undirected graph and $c: E \rightarrow \mathbb{R}$ it's cost function. Further let $T = (V,E')$ be a spanning tree in G.
I need to show the equivalence of the following statements:
- $T$ is a MST.
- For all $e = \{x,y\} \in E \setminus E'$ holds: No edge of the (unique) path from $x$ to $y$ has a higher cost than $e$.
- For all $e \in E'$ holds: Let $C$ one of the two connected components of $T-e$, then $e$ is an edge with minimal weight in $\delta(V(C))$.
I have done $1) \implies 2)$ and $2) \implies 3)$, but I do not know how to prove $3) \implies 1)$. Could you give me a hint?
EDIT: Please note that $\delta$ refers to the cut, i.e.:
$$\delta(X) = \{ \ \{u,v\} \in E(G) : u \in X \text{ and } v \notin X \}\}$$
没有正确的解决方案
不隶属于 cs.stackexchange