摘要：簡要論述了最小支撐樹MST子集證明方法的改進。

關鍵詞：

最小支撐樹MST；MST；定理

中圖分類號：TB

文獻標識碼：A

文章編號：1672-3198（2012）02-0289-01

1最小支撐樹

圖論中兩點的連線叫做邊，兩點之間的距離叫做邊的長度。兩個點之間通過一系列的邊聯(lián)系起來，那么這些邊則組成了鏈，如圖1所示，結點A和D，通過邊AB ，BC和CD聯(lián)系起來，所以上述三條邊組成了一條鏈。N個點之間如果均有鏈互相連接，我們稱這些點和鏈組成了一個聯(lián)接圖。其中封閉的鏈做構成的圖形我們稱為回路如圖2所示。

果N個點之間都有鏈相連接，并沒有形成回路，則稱這些點和邊構成了該圖形的一個支撐樹。樹中所有邊的長度的和叫做樹的重量，連接N個結點的所有可能的支撐樹中，重量最小的叫做最小支撐樹，記做MST。

如上圖所示圖3是一個聯(lián)接圖，圖3-1與圖3-2均為圖3的支撐樹，圖3-1該支撐樹的權重為24，圖3-2支撐樹的權重為19，并且圖3-2所形成的支撐樹是圖3的最小支撐樹MST。

2最小支撐樹定理證明的相關研究

在《聚類分析》一書中書籍作者依據(jù)最小支撐樹的性質，給出了相關的定理，及其證明方法。

定理1.1：任何MST中至少包含λ（p，Q）的一個邊。定義C(P，Q)表示P，Q間一切邊的集合，λ（p，Q）表示在C(P，C中邊長值等于極小邊長值的邊的集合。

定理1.2：MST中的所有邊都屬于X的某個劃分P，Q的最小截集λ(P，Q)中。

定理1.3:設C是X的子集，若對于C的一切劃分P，Q有DP，Q

關于定理1.3的證明，作者首先通過不等式的傳遞性質得到DP，X-C>DP，Q，然后通過該不等式得出結論 λ（P，PC）＜C（P，Q），最后依據(jù)定理1.1，X的MST中至少有λ（P，x|P）||||||||||||這個邊必屬λ(P，Q)，從而表明C的MST是X的MST的一部分，得證。

3一種改進的最小支撐樹定理證明方法

依據(jù)集合論的定義，若集合A是集合B的子集，即AB，必須滿足 a∈A，必有aiB。我們按照集合子集的定義以及反證法的策略給出更為嚴謹?shù)淖C明定理1.3的方法。

定理1.3:設C是X的子集，若對于C的一切劃分P，Q有DP，Q

證明：假設CMST不是XMST的子集，則說明并不是C的MST中所有的元素都屬于X的MST，即：a∈CMST，但a。

若aiCMST， 依據(jù)定理1.2：MST中的所有邊都屬于X的某個劃分P，Q的最小截集λ(P，Q)中，則必有 )，a的值等于DP，Q；由定理1.1可知XMST 中至少包含λ，，顯然a，由于P C；所以DC，CC≤DP，Cc如果，則相對于X(P，Pc)劃分，其DP，Pc一定等于DP，Q，且 )，同時也屬于 )，不妨設這條邊為a，則與a矛盾，因此我們得出，由該不等式與已知條件DP，Q

4結論

通過反證法進行的定理1.3的證明，是一種改進的最小支撐樹定理證明方法與思路，比以往的證明方法更嚴謹、更可靠，豐富了最小支撐樹定理證明的理論與方法，具有重要的實際意義。

參考文獻

［1］方開泰.聚類分析［M］.北京：地質出版社，1982.

［2］方開泰 . 聚類分析（I）數(shù)學的實踐與認識［M］.北京：地質出版社，1978.

［3］方開泰 . 聚類分析（II）數(shù)學的實踐與認識 ［M］.北京：地質出版社，1978.