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

1基本概念及定理[1]

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

2最小造價問題

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

3收銀臺的設置問題

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