最小生成樹問題的數(shù)學(xué)模型及其證明

孫培　劉凱

摘要：對圖論中賦權(quán)無向圖中最小生成樹問題的數(shù)學(xué)模型，分析了建立的過程，并證明了各邊不構(gòu)成圈的一個等價條件，最后推廣到有向圖中，為用數(shù)學(xué)軟件求解圖論問題打下基礎(chǔ)。

關(guān)鍵詞：最小生成樹；賦權(quán)無向圖；賦權(quán)有向圖

中圖分類號：O221.4 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）28-6682-03

1 概述

迄今為止，許多學(xué)者對賦權(quán)無向圖中的最小生成樹問題已經(jīng)進(jìn)行了研究，提出了很多有效地求解算法，例如破圈法、避圈法等。其實最小生成樹問題也可以用整數(shù)規(guī)劃來表示，謝金星教授已給出了最小生成樹問題的數(shù)學(xué)表達(dá)式[1]，但其中的無圈等價條件沒有證明，并且無圈的等價條件還有許多種表示方法[2-9]，這些表示方法雖然數(shù)學(xué)表達(dá)式不同，但本質(zhì)上是相同的。因此，該文將對無圈的等價條件給出證明，并給出賦權(quán)有向圖中最小生成樹問題的數(shù)學(xué)模型。

2 賦權(quán)無向圖中最小生成樹問題的數(shù)學(xué)模型

對一賦權(quán)無向圖G，我們假定G無重邊和環(huán)，即G為簡單圖，事實上，若G不是簡單圖，則有以下引理保證也可以求G的最小生成樹。

引理：給定賦權(quán)無向圖G，若G有重邊和環(huán)，則去掉后結(jié)果不會比原來的差。

證明：若G有環(huán)，直接去掉，若G有重邊，則將重邊按權(quán)從大到小排列，只留下邊權(quán)最小的邊，其余的重邊全去掉，得到新圖G*。由于最小生成樹問題是要求權(quán)最小的生成樹，故由G*的生成方式知，G*的最小生成樹就是G的最小生成樹。

我們用有向圖的思想來解決無向圖的最小生成樹問題。事實上，我們把無向圖中的邊加倍，看成是不同方向的雙弧，這樣，就把無向圖轉(zhuǎn)化成了有向圖。我們首先給出有向樹及其相關(guān)概念。

定義1 如果有向圖在不考慮邊的方向時，是一棵樹，那么這個有向圖稱為有向樹。進(jìn)一步，如果有一顆有向樹T，恰有一個頂點的入度為0，其余頂點的入度都為1，則稱T為根樹。

定義2 在有向樹T=（V，A）中，當(dāng)（u，v）∈A時，稱u是v的父親，v是u的兒子。

給定賦權(quán)無向圖G（V，E），我們將它變成有向圖，用[dij]表示兩頂點[vi]與[vj]之間的距離，即邊的權(quán)值；用決策變量[xij]表示頂點vi與vj之間的父子關(guān)系，xij=1表示頂點vi是vj的父輩，xij=0表示vi不是vj的父親。在賦權(quán)無向圖的最小生成樹中，我們可以指定任一個分枝點為樹的根，故不妨設(shè)頂點[v1]為生成樹的根。則該問題的數(shù)學(xué)模型為：

[minD=（vi，vj）∈Edijxij；s.t.vj∈Vx1j≥1，vj∈Vxji=1， i≠1，xij=0或1.各邊不構(gòu)成圈.]

其中第一組約束表示根[v1]至少有一條邊連接到其它的頂點；第二組約束表示除根外，每個頂點只能有一條邊進(jìn)入；同時注意到，各條邊均不構(gòu)成圈.目標(biāo)函數(shù)表示總距離最小。

對于數(shù)學(xué)模型（1.1）中的“各邊不構(gòu)成圈”的條件，從模型應(yīng)用和實現(xiàn)的角度，我們給出各邊不構(gòu)成圈的充要條件：

定理1 設(shè)T（V， A）是有向圖，且存在一點v1∈V，滿足d-（v1）=0，而對任意的vi（i≠1）有d-（vi）=1，則T無圈當(dāng)且僅當(dāng)存在一組[l（vi）∈1，…，n-1]，[i=2，…，n，]使得

[lvj≥l（vi）+xij-（n-2）?1-xij+n-3?xji，i，j=2，3，…，n，i≠j，]

其中xij=1表示（vi，vj）∈A； xij=0表示（vi，vj）[?]A.

證明：

1） 必要性

假設(shè)T（V， A）無圈，則由根樹的定義，T為一根樹，v1為根，現(xiàn)將T的頂點從根開始按下標(biāo)從小到大排列，則排列后的頂點滿足：若[vi]是[vj]的父親，則i

下證不等式[lvj≥l（vi）+xij-（n-2）?1-xij+n-3?xji，i，j=2，3，…，n，i≠j]成立。

若xij=0，①xji=0，此時

[l（vi）+xij-（n-2）?1-xij+n-3?xji=l（vi）-n-2≤n-1-n-2≤lvj，]

②xji=1，表明vj是vi的父親，此時

[l（vi）+xij-（n-2）?1-xij+n-3?xji=l（vi）-1=lvj.]

不等式成立。

若xij=1， 表明vi是vj的父輩，此時xji=0，則有

[l（vi）+xij-（n-2）?1-xij+n-3?xji=l（vi）+1=lvj，]

不等式成立。

2） 充分性

由于T（V， A）是有向圖，且存在一點v1∈V，滿足d-（v1）=0，而對任意的vi（i≠1）有d-（vi）=1，故假定T中有圈[（vi1，vi2，...，vim，vi1），]則有[xi1xi2=xi2xi3=…=xim-1xim=ximxi1=1，]故有

[l（i2）-l（i1）≥1，l（i3）-l（i2）≥1，…，l（im-1）-l（im）≥1，l（i1）-l（im）≥1，]相加得0≥n，矛盾，所以T無圈。

定理2 賦權(quán)無向圖的最小生成樹問題的數(shù)學(xué)模型為：

[minD=（vi，vj）∈Edijxij；s.t.vj∈Vx1j≥1，vj∈Vxji=1， i≠1，xij=0或1.lvj≥lvi+xij-n-2?1-xij+n-3?xjilvi=0，1，2，…，n-1.]

3 賦權(quán)有向圖最小生成樹問題的數(shù)學(xué)模型

設(shè)T（V，A）是一棵根樹，vk（k=1，2，…，n）為樹根，則有以下定理：

定理3 當(dāng)G（V，A）為賦權(quán)有向圖時，G的最小生成樹問題的數(shù)學(xué)模型為：

[minD=i=1nj=1j≠indijxij；s.t.vj∈Vj≠kxkj≥1，vj∈Vj≠ixji=1， i≠k，xij=0或1.lvj≥lvi+xij-n-2?1-xij+n-3?xjilvi=0，1，2，…，n-1.]

其中第一組約束表示根[vk]至少有一條邊連接到其它的頂點；第二組約束表示除根外，每個頂點只能有一條邊進(jìn)入；同時注意到，各條邊均不構(gòu)成圈.目標(biāo)函數(shù)表示總距離最小.模型（1.4）可以利用lingo、matlab數(shù)學(xué)軟件等求解。

4 實例驗證

例：考慮具有8個頂點v1，v2，…，v8的賦權(quán)無向圖，定義在邊上的權(quán)重如表1所示，求該圖的最小生成樹。

5 結(jié)論

本文對于賦權(quán)無向圖的最小生成樹問題，分析了數(shù)學(xué)模型，給出了其中無圈的證明，并推廣到賦權(quán)有向圖中，從而使得借助于lingo程序可以方便地求解最小生成樹問題。同時，我們還發(fā)現(xiàn)，將目標(biāo)函數(shù)換成max，就可以求圖G的權(quán)和最大的生成樹。賦權(quán)無向圖最小生成樹模型的建立，有助于研究其他圖論問題，如旅行商問題，最短路問題等。

參考文獻(xiàn)：

[1] 謝金星，薛毅.優(yōu)化建模與lindo/lingo軟件[M].北京：清華大學(xué)出版社，2005.

[2] 馮俊文.賦權(quán)有向圖中最小生成樹問題的顯式整數(shù)規(guī)劃模型[J].系統(tǒng)工程與電子技術(shù)，1998（11）：32-36.

[3] 胡紅.最小生成樹的應(yīng)用及拓展探討[J].洛陽師范學(xué)院學(xué)報，2012（31）.

[4] 李萍，王春紅，王文霞，任姚鵬.最小生成樹算法在旅行商問題中的應(yīng)用[J].電腦開發(fā)與應(yīng)用，2011（25）：62-63.

[5] 李洪波，陳軍.Prim最小生成樹算法的動態(tài)優(yōu)化[J].計算機(jī)工程與應(yīng)用，2007，43（12）：69-72.

[6] 江波，張黎.基于Prim算法的最小生成樹優(yōu)化研究[J].計算機(jī)工程與設(shè)計，2009，30（31）：3244-3247.

[7] 李萍，王春紅，王文霞，任姚鵬. 最小生成樹算法在旅行商問題中的應(yīng)用[J]. 電腦開發(fā)與應(yīng)用，2011，25（1）：62-64.

[8] 崔承宗，馬漢杰.基于最小生成樹的加權(quán)中值濾波算法[J].計算機(jī)工程，2010，36（23）：209-212.

[9] 姚建華，楊成濤.用最小生成樹解決TSP問題[J].湖北師范學(xué)院學(xué)報，2004，24（4）：52-54.