4
$\begingroup$

I know by definition that a minimum spanning tree (MST) of a weighted, connected graph has the lowest global value for for sum of all edges in a path that connects all vertices.

I'm curious if all MSTs are also optimized for lowest individual edge value possible. (I know that ones calculated with Kruskal's Algorithm are!)

As an example, is it possible to have two MSTs in a graph (equal global sum of their edges) but have one of those MSTs contain an edge of higher value than any edge on the other MST in the graph.

Thanks for any help you can give!

$\endgroup$

migrated from stackoverflow.com Oct 9 '15 at 16:32

This question came from our site for professional and enthusiast programmers.

7
$\begingroup$

is it possible to have two MSTs in a graph (equal global sum of their edges) but have one of those MSTs contain an edge of higher value than any edge on the other MST in the graph.

No, it isn't; assume it is, let $X$ be the MST with the heavy edge, and call that heavy edge $e := \{u,v\}$. Now there is some other MST $Y$ that doesn't contain edges that are at least as heavy as $e$. In $Y$, we know that there is a path from $u$ to $v$ since $X$ has such a path, so $Y$ must have one as well. Let $p$ denote that path in $Y$. There must be an edge $f$ on $p$ that isn't in $X$, since otherwise $X$ would contain the cycle formed by $p$ and $e$. Now add $f$ to $X$ and delete $e$ from it to get $X'$, which is a spanning tree as well. However, $X'$ has lower weight than $X$ since $f$ has lower weight than $e$, contradicting the assumption that $X$ is an MST.

For something more general which might answer your question more succinctly, here and here are proofs that all MSTs of a graph have the same multiset of edge weights, that is: if $k$ edges of weight $w$ occur in some MST, then $k$ edges of weight $w$ occur in all MSTs for any $w$ and $k$.


Something else that isn't proven in those answers that might be of interest to you: every MST only contains paths with smallest maximum weights for all pairs of vertices $\{u,v\}$, or in words: let $p$ be the unique path between $u$ and $v$ in a given MST $T$ of graph $G$; then for any $u$-$v$-path $q$ in $G$, the heaviest edge on $q$ is at least as heavy as the heaviest edge on $p$.

To prove this, assume that there is some pair $\{u,v\}$ such that the heaviest edge in the unique $u$-$v$-path $p$ in some MST $T$ is heavier than the heaviest edge in some other $u$-$v$-path $q$ in $G$. Let $e$ denote the heaviest edge in $p$; now remove $e$ from $T$, which partitions $T$ into two connected components $U$ and $V$ such that $u \in U$ and $v \in V$. We know that $q$ starts in $U$ and ends in $V$, so there must be an edge $f$ that belongs to the cut $(U,V)$. Now we find that $(T \cup \{f\}) - \{e\}$ is a spanning tree again, and since the weight of $f$ is smaller than the weight of $e$ by assumption, we find that $(T \cup \{f\}) - \{e\}$ has lower weight than the MST $T$, contradicting the minimality of $T$. Thus, no such path $q$ can exist in $G$.

Spanning trees with the heaviest weight being minimal are called minimum bottleneck spanning trees, and you can use the above to show that every MST is an MBST (the converse does not hold, i.e. there may be an MBST that is not an MST, specifically: an MBST might use too many heaviest edges). If an MST $T$ wasn't also an MBST, then there would be a heavier edge in $T$ than in some other spanning tree, and that edge would be on some path, and then the arguments above apply to that path.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.