Relation Between Bridges And Spanning Trees
Needs to be restructured into separate pages according to house style.
It may also need to be brought up to our standard house style.
If you have done this or know it has been done, please remove {{Tidy}} from the code.
You can help ProofWiki by adding these links.
To discuss this in more detail, feel free to use the talk page.
Once you have done so, you can remove this instance of {{MissingLinks}} from the code.
Contents |
Bridges and spanning trees
Let $G$ be a simple graph and $T$ a spanning tree for $G$.
Theorem
An edge $e$ is a bridge in $G$ $\iff$ $e$ belongs to every spanning tree $T$
Proof
Necessary Condition
If $e$ is a bridge then it belongs, by definition, to every path between a pair of vertices $u$ and $v$. Therefore $e$ has to be in $T$ in order to be a spanning tree of $G$, otherwise $u$ and $v$ would not be connected in $T$.
Sufficient Condition
You can help Proof Wiki by expanding it.
To discuss it in more detail, feel free to use the talk page.
When this page/section has been completed, {{Stub}} should be removed from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
Bridges and minimum spanning trees
Let $G$ be a simple weighted graph and $T$ a minimum spanning tree for $G$. Lets assume every edge has a unique weight associated to it.
Theorem (minimum weighted bridge)
An edge $e$ is a bridge of minimum weight in $G$ $\iff$ $e$ belongs to every minimum spanning tree $T$
Proof
Necessary Condition
Assume the contrary, $e$ is a bridge of minimum weight but it doesnt belong to some minimum spanning tree $Q$. Adding $e$ to $Q$ creates an unique cycle $C$ in $Q$ but then there exists $v$ $\in$ $C$ such that $w(Q)$ < $w(Q+e-v)$ contadicting its minimality.
Sufficient Condition
You can help Proof Wiki by expanding it.
To discuss it in more detail, feel free to use the talk page.
When this page/section has been completed, {{Stub}} should be removed from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
Theorem (maximum weighted bridge)
An edge $e$ belongs to every minimum spanning tree $T$ for $G$ and has maximum weight in $G$ $\implies$ $e$ is a bridge in $G$
Proof
You can help Proof Wiki by expanding it.
To discuss it in more detail, feel free to use the talk page.
When this page/section has been completed, {{Stub}} should be removed from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
