證明:如果$ T'$不是MST,則可以用較淺的邊緣替換其邊緣之一,以獲得較淺的生成樹


0

證明:如果 $ T'=(V,F')$ 是生成樹,但不是 $ G =(V,E)$ ,然後有邊 $ e'\ in F'$ $ e \ in $ $ E $ \ $ F'$ 這樣,span class =" math-container"> $ w(e) $ T'$ \ $ \ {e'\} \ cup \ {e \} $ 是一棵生成樹。

我的想法:

$ T =(V,F)$ 成為 $ G $ 的MST。>

對於所有 $ e \ in T $ ,請嘗試將其插入 $ T'$ 並查看所創建的循環中是否存在比 $ e $ 重的邊緣。如果找到這樣的 $ e $ ,我們就完成了。

如果沒有,請定義 $ G'=(V,F \ cup F')$

此圖顯然具有MST,因為 $ F \ subset F'\ cup F $

我們在上一部分中沒有找到合適的 $ e $ ,因此 $ F $ 在用於在圖 $ G'$ 中找到MST的通用算法中,span>可能會被塗成紅色。

這意味著存在一個MST $ T''=(V,F'')$ 使得 $ F" \ subseteq F'$ ,但這是不可能的,因為 $ T'$ 不是MST的 $G'$ ,因為 $ T $ 較輕(根據定義, $ w(T)

這看起來正確嗎?

0

I have a proposal for a proof that doesn't involve "coloring" since it sounds vague.

Let $T' = (V,F')$ be a spanning tree but not a MST of $G=(V,E)$. Let $T = (V,F)$ be a MST of $G$.


You already did the following:
Now go through all $e \in F-F'$ and add $e$ to $T'$. Resulting graph contains a cycle if there is another edge $e'$ on the cycle such that $e\neq e',w(e) < w(e')$ we are done because $T'$ could be augmented.


My approach for the rest using Kruskal's algorithm:
Otherwise we construct a graph $G' = (V,F'\cup (F-F')) = (V, F'\cup F)$. For all $e \in F-F'$ and for all cycles $e$ lies on (in $G'$) $e$ is clearly one of the edges with the max weight.

Now run Kruskal's algorithm on $G'$ with a modified sorting procedure. Every edge is primarily sorted by its weight and secondary by the boolean if it belongs to $F'$ or not in such a way that for two edges with different weights the edge with the least weight comes first, but if two edges have the same weight the one belonging to $F'$ comes first (if both belong to $F'$ the order doesn't matter). We are allowed to make this modification to the sorting procedure because Kruskal's algo doesn't care in which order edges with equal weight appear.

The algorithm proceeds to sort all edges in mentioned order. Thus for every cycle in $G'$ all edges in the cycle are considered before the an edge $e\in F- F'$ is considered. Since we know that Kruskal's algo connects two nodes always when they do not create a cycle and we know that edges $F-F'$ are considered last for every cycle the MST found by the algo is $T' = (V,F')$.
Contradiction: But from our assumption we know that the weighted sum of $T$s edges is clearly lower than that of $T'$s edges and that $T$ is a spanning tree of $G'$. So actually $T$ is the MST of $G'$. Thus we have a contradiction and can conclude that there must be an $e \in F- F'$ such that it augments $T'$.