最小樹的一種新的生成方法

洪燕君

（石河子大學(xué)師范學(xué)院石河子832003）

最小樹理論是網(wǎng)絡(luò)優(yōu)化的一個重要內(nèi)容，迭代思想是優(yōu)化理論的基本思想。迭代思想是從一個初始的狀態(tài)出發(fā)，根據(jù)判優(yōu)準(zhǔn)則判斷該狀態(tài)是否最優(yōu)，若不是最優(yōu)，依據(jù)迭代規(guī)則進(jìn)行迭代更新，得到一個優(yōu)化的狀態(tài)，繼續(xù)重復(fù)上述過程，直至得到最優(yōu)解或判斷無解。這種思想方法在通訊網(wǎng)、電力網(wǎng)、交通網(wǎng)、管道網(wǎng)、工程進(jìn)度網(wǎng)、生物信息網(wǎng)等的設(shè)計(jì)和實(shí)際生活中的許多大型優(yōu)化問題中均有廣泛的應(yīng)用。本文利用判優(yōu)準(zhǔn)則判斷任意生成樹是否最優(yōu)，如果不是最優(yōu)，則利用迭代思想進(jìn)行迭代，得到權(quán)更小的生成樹。

許多學(xué)者對最小樹問題都做了相關(guān)的研究，如文獻(xiàn)［1－3］介紹了求最小樹的常用方法，如Kruskal算法（避圈法）、破圈法、Dijkstra算法等，文獻(xiàn)［4］給出了最小樹算法的復(fù)雜性分析，C Thomassen［5］的最新研究工作表明：圖的生成樹的數(shù)目還和圖的無圈定向數(shù)有關(guān)并得到了無橋無環(huán)圖的生成樹的數(shù)目總是不超過其無圈定向數(shù)。

本文引入了關(guān)于連枝的迭代法和關(guān)于樹枝的迭代法并給出了從一棵生成樹中找最小樹的新的方法。這種方法在網(wǎng)絡(luò)設(shè)計(jì)中有重要的應(yīng)用。

1 最小樹的基本概念和性質(zhì)

本文討論的圖均為連通無向有限圖，文中未涉及的概念和術(shù)語參見文獻(xiàn)［6－9］。

無向圖G定義為一個偶對（V，E），其中V是指圖的頂點(diǎn)集，E是指圖的邊集合。不含圈的圖稱為無圈圖，連通圖的無圈圖稱為樹。在樹的任意二個點(diǎn)之間添加一條邊，稱得到的圈為一個基本圈。

設(shè)T是連通圖G的一棵樹，e（i）是樹枝。對應(yīng)e（i）存在G的割集S（i），S（i）只包括一條樹枝e（i）及某些余樹枝，且與e（i）的方向一致。稱S（i）為G

則稱w（T）為T的權(quán)（或長）。G中權(quán)最小的生成樹稱為G的最小樹。

定理1：設(shè)T是網(wǎng)絡(luò)G的一棵生成樹，則T是G的最小樹當(dāng)且僅當(dāng)對任意的邊e∈T有，w（e）＝的對應(yīng)T的一個基本割集。以上定義參見文獻(xiàn)［8］。

網(wǎng)絡(luò)G＝（V，E，W），其中V是指圖的頂點(diǎn)集，E是指圖的邊集合，W是指邊的權(quán)的集合。

定義1：給定網(wǎng)絡(luò)G＝（V，E，W），設(shè)T＝（V，E′）為G的一棵生成樹，令

定理2：設(shè)T是網(wǎng)絡(luò)G的一棵生成樹，則T是G的最小樹，當(dāng)且僅當(dāng)對任意的邊e∈T有w（e）＝

從上面定理可得下面定理。

定理3：生成樹T是網(wǎng)絡(luò)G的唯一最小樹，當(dāng)且僅當(dāng)對于任意的邊e∈G＼T，e是C（e）中唯一的最長邊。

定理4：生成樹T是網(wǎng)絡(luò)G的唯一最小樹當(dāng)且僅當(dāng)對于任意的邊e∈T，e是S（e）中唯一的最小邊。

2 迭代法在最小樹理論中的應(yīng)用

2．1 任意生成樹是否為最小樹的判斷

定理5：設(shè)T是網(wǎng)絡(luò)G的任意生成樹，對于每條連枝e′∈G＼T，根據(jù)最小樹的性質(zhì)，給出e′的檢驗(yàn)數(shù)數(shù)均為非負(fù)數(shù)，則該生成樹為最小樹。

證明：若連枝e′∈G＼T的檢驗(yàn)數(shù)δ（e′）≥0，說明e′的權(quán)在基本圈C（e′）的所有邊中是最長邊，根據(jù)定理1可知：生成樹T為最小樹。

推論1：若每條連枝邊的檢驗(yàn)數(shù)均大于0，則該生成樹為唯一的最小樹。

定理6：設(shè)T是網(wǎng)絡(luò)G的任意生成樹，對于每條樹枝邊e∈T，根據(jù)最小樹的性質(zhì)，給出e的檢驗(yàn)數(shù)δ均為非負(fù)數(shù)，則該生成樹為最小樹。

證明：若樹枝e∈T的檢驗(yàn)數(shù)δ（e）≥0，說明e的權(quán)在基本割集S（e）的所有邊中是最小邊，根據(jù)定理2可知：生成樹T為最小樹。

推論2：若每條樹枝邊的檢驗(yàn)數(shù)均大于0，則該生成樹為唯一的最小樹。

2．2 利用迭代法求最小樹的算法

2．2．1 關(guān)于連枝的迭代法（利用連枝的檢驗(yàn)數(shù)）

該方法的主要步驟為：

1）任給一棵生成樹T0。

3）在小于0的檢驗(yàn)數(shù)中選取最小的，不妨設(shè)為e′的檢驗(yàn)數(shù)最小，則在e′確定的基本圈C（e′）中換進(jìn)e′，換出C（e′）中的最長邊。迭代后得到一棵新的生成樹T′，轉(zhuǎn)2）。

由最小樹必定存在，則經(jīng)過有限次迭代后，必會得到圖G的最小樹。

2．2．2 關(guān)于樹枝的迭代法（利用樹枝的檢驗(yàn)數(shù)）

該方法的主要步驟如下：

1）任給一棵生成樹T0。

2）根據(jù)定理6求出所有樹枝邊的檢驗(yàn)數(shù)，若全為非負(fù)數(shù)，則該生成樹為最小樹；否則，轉(zhuǎn)3）。

3）在小于0的檢驗(yàn)數(shù)中選取最小的，不妨設(shè)e的檢驗(yàn)數(shù)最小，在e確定的基本割集S（e）中換出邊e，換進(jìn)S（e）中最小邊。迭代后得到一棵新的生成樹T′，轉(zhuǎn)2）。

由最小樹必定存在，則經(jīng)過有限次迭代后，必會得到圖G的最小樹。

面對全球氣候日益惡劣，霧霾天氣頻現(xiàn)的情況，大華透霧技術(shù)不僅提升了監(jiān)控感知產(chǎn)品的感知力和穩(wěn)定性，進(jìn)一步維護(hù)了大眾的安全和利益，而且也為霧霾、煙塵、水汽頻發(fā)的特定場景，筑起了一道視頻防控的堅(jiān)實(shí)屏障。

2．3 退化的情形［9］

當(dāng)關(guān)于連枝的迭代法和關(guān)于樹枝的迭代法中的檢驗(yàn)數(shù)都是非負(fù)數(shù)的情況下，若有檢驗(yàn)數(shù)為0，則表示該網(wǎng)絡(luò)的最小樹不是唯一的，否則，網(wǎng)絡(luò)具有唯一的最小樹，即全部檢驗(yàn)數(shù)均大于0的情形。

3 實(shí)例及分析

例1：判斷圖1給的生成樹T0＝｛e1，e2，e5，e6｝是否為最小樹。

圖1 生成樹和最小樹Fig．1Spanning tree and minimal tree

解法一：使用關(guān)于連枝的迭代法（利用定理5）。

生成樹T0的連枝集為｛e3，e4，e7，e8｝，因而由它們確定的基本圈分別為：

它們對應(yīng)的檢驗(yàn)數(shù)分別為：

根據(jù)定理5可知，該生成樹T0不是最小樹。

解法二：使用關(guān)于樹枝的迭代法（利用定理6）。

生成樹T0＝｛e1，e2，e5，e6｝，因而由它們確定的基本割集分別為：

它們對應(yīng)的檢驗(yàn)數(shù)分別為：

根據(jù)定理6可知，該生成樹T0不是最小樹。

例2：從例1給定的生成樹T0＝｛e1，e2，e5，e6｝出發(fā)，求該網(wǎng)絡(luò)的最小樹。

解：使用關(guān)于連枝的迭代法（利用連枝的檢驗(yàn)數(shù)）。

由例1可知，e7的檢驗(yàn)數(shù)最小，故連枝e7應(yīng)該換入，而樹枝e5應(yīng)被換出。此時，得到一棵新的生成樹T1＝｛e1，e2，e6，e7｝（T1的權(quán)比T0的權(quán)?。缓笥?jì)算關(guān)于生成樹T1的所有連枝的檢驗(yàn)數(shù)。為此求出所有的基本圈如下：

從而它們對應(yīng)的檢驗(yàn)數(shù)分別為：

根據(jù)定理5可知，該生成樹T1不是最小樹。e8的檢驗(yàn)數(shù)最小，故連枝e8應(yīng)被換入，而樹枝e6應(yīng)被換出，此時，得到一棵新的生成樹T2＝｛e1，e2，e8，e7｝（T2的權(quán)比T1的權(quán)?。缓笤儆?jì)算關(guān)于生成樹T2的所有連枝的檢驗(yàn)數(shù)。為此先求出所有的基本圈為：

它們對應(yīng)的檢驗(yàn)數(shù)分別為：

由定理5可知，生成樹T2是最小樹，且該最小樹不是唯一的。

使用關(guān)于樹枝的迭代法（利用樹枝的檢驗(yàn)數(shù)），并根據(jù)關(guān)于連枝的迭代法可類似求出最小樹。

4 結(jié)語

1）本文給出了從一棵生成樹中找最小樹的新方法。這種方法和網(wǎng)絡(luò)計(jì)劃圖上優(yōu)化問題的算法以及一般的組合最優(yōu)化問題有著比較密切的關(guān)系。

2）實(shí)際生活中的許多問題都可以轉(zhuǎn)化為最小樹問題來求解，并且其算法的復(fù)雜性是多項(xiàng)式級別的，如假設(shè)要建造一個連接若干城市的鐵路網(wǎng)絡(luò)，并且知道任意二個城市之間的直通鐵路的造價時，使用我們的算法就可以設(shè)計(jì)出一個總造價最小的鐵路網(wǎng)絡(luò)。

3）本文的算法可以生成一棵最小樹，并且這棵最小樹一般是最優(yōu)的。

［1］ Kruskal J B．On the shortest spanning subtree of a graph and the traveling saleman problem ［J］．Proc AMS，1956，7：48－50．

［2］Dijkstra E W．A note on two problem in connexion with graph［J］．Numer Math，1959，1：269－271．

［3］Floyd R W．Algorithm 97，shortest path［J］．Comm ACM，1962，5：345－345．

［4］Edmonds J．Path，trees and flowers［J］．Canad J Math，1965，17：449－467．

［5］Thomassen C．Spanning trees and orientations of graphs［J］．J Combinatorics 2010，1（2）：101－111．

［6］胡運(yùn)權(quán)，等．運(yùn)籌學(xué)基礎(chǔ)及其應(yīng)用［M］．4版．北京：高等教育出版社，2004：119－136．

［7］劉家壯，王建方．網(wǎng)絡(luò)優(yōu)最優(yōu)化［M］．武漢：華中工學(xué)院出版社：36－79．

［8］田豐．圖與網(wǎng)絡(luò)流理論［M］．北京：科學(xué)出版社，1987：15－42．

［9］刁在筠，劉桂真，宿潔，等．運(yùn)籌學(xué)［M］．3版．北京：高等教育出版社，2007：198－203．