孫培　劉凱

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

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

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

1 概述

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

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

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

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

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

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

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

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

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

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

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

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

定理1 設(shè)T（V， A）是有向圖，且存在一點(diǎn)v1∈V，滿足d-（v1）=0，而對(duì)任意的vi（i≠1）有d-（vi）=1，則T無(wú)圈當(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）無(wú)圈，則由根樹(shù)的定義，T為一根樹(shù)，v1為根，現(xiàn)將T的頂點(diǎn)從根開(kāi)始按下標(biāo)從小到大排列，則排列后的頂點(diǎn)滿足：若[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，此時(shí)

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

②xji=1，表明vj是vi的父親，此時(shí)

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

不等式成立。

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

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

不等式成立。

2） 充分性

由于T（V， A）是有向圖，且存在一點(diǎn)v1∈V，滿足d-（v1）=0，而對(duì)任意的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無(wú)圈。

定理2 賦權(quán)無(wú)向圖的最小生成樹(shù)問(wè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ù)問(wèn)題的數(shù)學(xué)模型

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

定理3 當(dāng)G（V，A）為賦權(quán)有向圖時(shí)，G的最小生成樹(shù)問(wèn)題的數(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]至少有一條邊連接到其它的頂點(diǎn)；第二組約束表示除根外，每個(gè)頂點(diǎn)只能有一條邊進(jìn)入；同時(shí)注意到，各條邊均不構(gòu)成圈.目標(biāo)函數(shù)表示總距離最小.模型（1.4）可以利用lingo、matlab數(shù)學(xué)軟件等求解。

4 實(shí)例驗(yàn)證

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

5 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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