前言：本站為你精心整理了農(nóng)業(yè)經(jīng)濟(jì)中圖論作用范文，希望能為你的創(chuàng)作提供參考價值，我們的客服老師可以幫助你提供個性化的參考范文，歡迎咨詢。

1基本概念及定理[1]

定義1:設(shè)V是頂點(diǎn)集,E是邊集,如果對每個e∈E,有V中一個頂點(diǎn)對(u,v)和它對應(yīng),則稱V及E組成的集為一個線圖,記為G=(V,E)。頂點(diǎn)u及v稱為邊e的端點(diǎn),并稱u及v相鄰。若線圖G中任兩個頂點(diǎn)之間都有通路,則稱G是連通的。定義2:設(shè)G1=(V1,E1)和G=(V,E)為兩個線圖,如果V1V且E1E,則稱G1為G的子圖。定義3:設(shè)線圖G連通且有n個頂點(diǎn),若T是G的一個有n個頂點(diǎn)和n-1條邊的連通子圖,則稱T為G的一棵樹。設(shè)線圖G連通,若對它的每一邊eij=(vi,vj)賦以實(shí)數(shù)wij=w(eij),則稱G為賦權(quán)圖,實(shí)數(shù)wij表示邊eij上的權(quán)。在實(shí)際問題中,wij可以代表距離、運(yùn)費(fèi)、造價等。定義4:設(shè)I是G的一個頂點(diǎn)子集,如果G中每一條邊至少有一個端點(diǎn)在I中,則稱I為G的一個點(diǎn)覆蓋。頂點(diǎn)數(shù)最少的點(diǎn)覆蓋為最小點(diǎn)覆蓋。若對點(diǎn)覆蓋I中任一頂點(diǎn)x,I\(x)都不是點(diǎn)覆蓋,則說I為極小點(diǎn)覆蓋。顯然,最小點(diǎn)覆蓋一定是極小點(diǎn)覆蓋。定義5:設(shè)K是G的一個頂點(diǎn)子集,如果K中任何兩個頂點(diǎn)在G中都不鄰接,則稱K為G的獨(dú)立集。頂點(diǎn)數(shù)最多的獨(dú)立集為最大獨(dú)立集。設(shè)K為G的獨(dú)立集,若對G中任何異于K的獨(dú)立集K′,均有|K′|≤|K|,則說K是極大獨(dú)立集。定理1:設(shè)KV,則K是G的極大獨(dú)立集V\K是G的極小點(diǎn)覆蓋。

2最小造價問題

在一個地區(qū)或一個國家的地圖上,都畫有連接各城鎮(zhèn)之間的一個鐵路網(wǎng)或公路網(wǎng)。已知城市vi和vj間的直通線路的造價為wij=w(eij),要求給出一個總造價為最小的設(shè)計(jì)方案。又如一個城鎮(zhèn)中,對若干新建居民點(diǎn)供應(yīng)自來水和煤氣,已知連接各點(diǎn)間的直通管道的造價,要求給出一個造價最小的鋪設(shè)方案。尋求這樣的設(shè)計(jì)方案在農(nóng)業(yè)科學(xué)建設(shè)中有著重要的經(jīng)濟(jì)價值,而解決這些實(shí)際問題可以歸結(jié)為圖論中連通賦權(quán)圖的最優(yōu)樹問題。文獻(xiàn)[2]中給出了克魯斯克爾算法,該算法由3步組成:(1)在G的邊集E中選取邊e1,使w(e1)最小。(2)設(shè)已選好了邊e1,e2,…,ek,則從E-{e1,e2,…,ek}中選取ek+1,使(1)導(dǎo)出子圖G[{e1,e2,…,ek+1}]無回路;(2)w(ek+1)是滿足(1)的盡可能小的權(quán)。(3)當(dāng)?shù)?2)步不能繼續(xù)進(jìn)行時,則停止?？梢宰C明,由克魯斯克爾算法構(gòu)造出的樹是連通賦權(quán)圖G的一棵最優(yōu)樹。例如所示賦權(quán)圖表示某7個城市v1,v2,…,v7及預(yù)先測算出的它們之間的一些直接通信線路的造價。試給出一個既使各城市之間能夠通信又使總造價為最小的設(shè)計(jì)方案。顯然,所求即為連通賦權(quán)圖的具有最小權(quán)的一棵樹—最優(yōu)樹。利用克魯斯克爾算法,第一步,選e1=(v1,v7),w(e1)=1;第二步,選e2=(v3,v4),w(e2)=3;第三步,選e3=(v2,v7),w(e3)=4;第四步,選e4=(v3,v7),w(e4)=9;第五步,本該選權(quán)為15的邊(v2,v3)作為e5,但它與已選的e3,e4構(gòu)成回路,故舍去;當(dāng)改選權(quán)為16的邊(v4,v7)時,同樣因它與已選的e2,e4構(gòu)成回路,再次舍去,從而選取e5=(v4,v5),w(e5)=17;依次選下去,最后選e6=(v1,v6),w(e6)=23。此時7個城市均已相通且無回路,算法終止。于是由e1、e2、e3、e4、e5和e6所構(gòu)成的樹()即給出所需要的總造價最小的設(shè)計(jì)方案,其總造價為57。

3收銀臺的設(shè)置問題

許多大型商場為加強(qiáng)經(jīng)營管理,對商品的零售收入實(shí)行統(tǒng)一收款制度。為了使顧客在任何一個貨架前都能看到收銀臺,則收銀臺應(yīng)設(shè)置在什么位置并且至少要設(shè)置多少個收銀臺。構(gòu)作線圖G=(V,E)。該商場兩排貨架之間的通道為G的邊,通道交叉處為G的頂點(diǎn)。為使顧客在任何一個貨架前都能看到收銀臺,從盡可能減少設(shè)置收銀臺的數(shù)目來說,收銀臺應(yīng)設(shè)置在通道的交叉處。于是收銀臺的設(shè)置問題就歸結(jié)為在G中找出一個最小點(diǎn)覆蓋。由于最小點(diǎn)覆蓋必是極小點(diǎn)覆蓋,所以,只需確定G的所有極小點(diǎn)覆蓋。文獻(xiàn)[3]中介紹了枚舉法,由定理1,V的子集K是G的極小點(diǎn)覆蓋V\K是G的極大獨(dú)立集對每個x∈V,要么選擇x∈K,要么選擇NG(x)K(但兩者不能同時成立)。這里NG(x)表示在G中與頂點(diǎn)x相鄰的點(diǎn)的集合。這個事實(shí)提供了一個求極小點(diǎn)覆蓋的方法:對每個x∈V,要么選擇x,要么選擇NG(x)。為了有效地執(zhí)行該程序,引入下列邏輯運(yùn)算:設(shè)x、y、z是3條指令,定義x+y為“要么執(zhí)行x,要么執(zhí)行y”;xy為“同時執(zhí)行x和y”。容易驗(yàn)證這2個邏輯運(yùn)算滿足交換律、結(jié)合律、分配律、吸收律(x+x=x,xx=x,x+xy=x)。根據(jù)上述定義的邏輯運(yùn)算和求極小點(diǎn)覆蓋的程序,頂點(diǎn)集為{v1,v2,…,vn}的線圖G的所有極小點(diǎn)覆蓋可表示為C(v1,v2,…,vn)=∏ni=1(xi+∏y∈N(xi)y)。最后比較所有求出的極小點(diǎn)覆蓋,找出G中一個最小點(diǎn)覆蓋即可。