洪燕君

（石河子大學師范學院石河子832003）

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

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

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

1 最小樹的基本概念和性質

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

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

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

則稱w（T）為T的權（或長）。G中權最小的生成樹稱為G的最小樹。

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

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

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

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

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

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

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

2 迭代法在最小樹理論中的應用

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

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

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

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

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

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

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

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

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

該方法的主要步驟為：

1）任給一棵生成樹T0。

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

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

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

該方法的主要步驟如下：

1）任給一棵生成樹T0。

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

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

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

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

2．3 退化的情形［9］

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

3 實例及分析

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

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

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

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

它們對應的檢驗數(shù)分別為：

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

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

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

它們對應的檢驗數(shù)分別為：

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

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

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

由例1可知，e7的檢驗數(shù)最小，故連枝e7應該換入，而樹枝e5應被換出。此時，得到一棵新的生成樹T1＝｛e1，e2，e6，e7｝（T1的權比T0的權?。?，然后計算關于生成樹T1的所有連枝的檢驗數(shù)。為此求出所有的基本圈如下：

從而它們對應的檢驗數(shù)分別為：

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

它們對應的檢驗數(shù)分別為：

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

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

4 結語

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

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

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］胡運權，等．運籌學基礎及其應用［M］．4版．北京：高等教育出版社，2004：119－136．

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

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

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