4
$\begingroup$

$G$ is a weighted connected graph. Let $T(G)$ be the graph that has the spanning trees of $G$ as vertices, and two spanning trees are adjacent to each other if and only if each one of them has only one edge that the other doesn't have. To each vertex of $T(G)$ we associate the weight of the spanning tree that corresponds to it.

Let $T_1$ be any vertex of $T(G)$, that is, any spanning tree of $G$. Prove that $T_1$ is a local minimum if and only if $T_1$ is a global minimum.

To put it in another words, prove that $T_1$ has weight less than or equal to all its neighbours in $T(G)$ if and only if $T_1$ is a minimum spanning tree.

$\endgroup$

2 Answers 2

5
$\begingroup$

Let $T$ be a local minimum spanning tree that is not a global minimum. Let $e_1,\ldots,e_m$ the edges of $T$ ordered by non-decreasing weight. Let $T'$ be a minimum weight spanning tree that coincides with $T$ on the largest possible begin segment, so we may assume $T'$ has edges $e_1,\ldots,e_{n-1},f_n,\ldots,f_m$ (again ordered by non-decreasing weight) and $f_n\ne e_n$. Let $w$ be the weight function in our graph.

We claim that $w(f_n)<w(e_n)$: indeed, if $w(e_n)\leq w(f_n)$ then $e_1,\ldots,e_{n-1},e_n$ would be a valid startup for Kruskal's algorithm and would lead to a minimum weight spanning tree that coincides with $T$ on a larger initial segment.

$T+f_n$ contains exactly one cycle $C$. The edges of $C$ different from $f_n$ cannot all be in $\{e_1,\ldots,e_{n-1}\}$ or we would have a cycle in $T'$. So we find at least one edge $f$ on $C$ that is different from $e_1,\ldots,e_{n-1}$ and $f_n$. But then $w(f)\geq w(e_n)>w(f_n)$, so $T+f_n-f$ is a spanning tree with a smaller total weight that is a neighbour of $T$ in the spanning tree graph. Contradiction.

(I left some small details for you to prove. Let me know if they cause trouble).

Note that this proves the slightly stronger statement, that each non-minimal tree has a neighbour of strictly smaller total weight.

$\endgroup$
16
  • $\begingroup$ It looks like this approach assumes that Kruskal's algorithm can find every minimum spanning tree, a fact that might not be trivial to prove. $\endgroup$
    – Apass.Jack
    Commented Jul 10, 2020 at 18:20
  • $\begingroup$ I fail to see where that assumption is used in the proof. Can you elaborate? $\endgroup$ Commented Jul 12, 2020 at 9:31
  • $\begingroup$ "$e_1,\ldots,e_{n-1},e_n$ would be a valid startup for Kruskal's algorithm". Why is "$e_1,\ldots,e_{n-1}"$ a valid startup for Kruskal's algorithm? You have assumed that fact, which may not be trivial to prove. $\endgroup$
    – Apass.Jack
    Commented Mar 8, 2022 at 6:14
  • $\begingroup$ There are three ways to remedy the situation. One way is to consider Kruskal's algorithm can find every minimum spanning tree as a known fact. A second way is to prove that fact right here. The third way is, instead of "let $T'$ be a minimum weight spanning tree that coincides with $T$ on the largest possible begin segment", we can "let $T'$ be a minimum weight spanning tree obtainable by Kruskal's algorithm that coincides with $T$ on the largest possible begin segment". $\endgroup$
    – Apass.Jack
    Commented Mar 8, 2022 at 6:19
  • $\begingroup$ The reason that $e_1,\ldots,e_{n-1}$ is a valid startup follows from the assumption in the first paragraph that $e_1,\ldots,e_{n-1},f_n,\ldots,f_m$ is ordered by non-decreasing weight. $\endgroup$ Commented Mar 9, 2022 at 15:09
0
$\begingroup$

I'm not sure if this proof is correct, so feel free to discuss and point out the errors. My intention was to arrive at a proof without the consideration of greedy algorithms such as Kruskal's. This is because the claim that "every local optimum is a global optimum (which is to be proved) forms the basis of such algorithms.

Suppose not that is, there exists a local minimal spanning tree $T=(e_1,e_2,...e_m)$ which differs from the (global) minimal spanning tree, say $T'=(e_1,e_2,...e_{n-1},f_n,...f_m), \sum_{j=n}^m w(f_j)\ne \sum_{j=n}^m w(e_j)$. [This last assumption is required so as to truly say that $T$ is not the global spanning tree.]

Now, we define the neighbourhood of a spanning tree, $t$ as $N(t)=\{s: s\text{ is a spanning tree obtained as: add an edge to }t\text{, delete an edge from the cycle formed}\}.$ Hence, there exist spanning trees $S_n,S_{n+1},...S_m\in N(T)$ such that $$S_n=(e_1,e_2,...e_{n-1},f_n,e_{n+1},...e_m),\quad S_{n+1}=(e_1,e_2,...e_n,f_{n+1},e_{n+2},...e_m)\quad...$$ Since, $T$ is a local optimum it has less weight than each of its neighbours. So, we can write $$w(f_n)\ge w(e_n),\quad w(f_{n+1})\ge w(e_{n+1}),\quad...$$ Summing these up we get, $$\sum_{i=1}^m w(e_i)\le\sum_{i=1}^{n-1}w(e_i)+\sum_{j=n}^m w(f_j)\Rightarrow\text{weight of }T\le\text{weight of }T'.$$ But, $T'$ is the minimal spanning tree and $\sum_{j=n}^m w(f_j)\ne \sum_{j=n}^m w(e_j)\Rightarrow$ weight of $T'<$ weight of $T$. We arrive at a contradiction. Hence, a local MST is necessarily a global MST.

$\endgroup$
1
  • $\begingroup$ @LeenDroogendijk do you mind giving some input on the proof? I'm not confident about it and I believe you know more about the topic. $\endgroup$
    – reyna
    Commented Jan 23 at 17:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .