數(shù)學(xué)建模圖論

1、圖論一最短路問題問題描述：尋找最短路徑就是在指定網(wǎng)絡(luò)中兩結(jié)點(diǎn)間找一條距離最小的路。最短路不僅僅指一般地理意義上的距離最短,還可以引申到其它的度量,如時(shí)間、費(fèi)用、線路容量等。將問題抽象為賦權(quán)有向圖或無向圖，邊上的權(quán)均非負(fù)對(duì)每個(gè)頂點(diǎn)定義兩個(gè)標(biāo)記（，），其中：表示從頂點(diǎn)到的一條路的權(quán)：的父親點(diǎn)，用以確定最短路的路線：具有永久標(biāo)號(hào)的頂點(diǎn)集1.1Dijkstra算法：即在每一步改進(jìn)這兩個(gè)標(biāo)記，使最終為最短路的權(quán)輸入：的帶權(quán)鄰接矩陣步驟：（1） 賦初值：令，對(duì)，令， 。（2） 對(duì)每個(gè) （即不屬于上面集合的點(diǎn)），用 代替，這里表示頂點(diǎn)和之間邊的權(quán)值。計(jì)算，把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，令。（3） 若，則停

2、止；若，則用代替，轉(zhuǎn)（2）算法結(jié)束時(shí)，從到各頂點(diǎn)的距離由的最后一次編號(hào)給出。在進(jìn)入之前的編號(hào)叫標(biāo)號(hào)，進(jìn)入之后的編號(hào)叫標(biāo)號(hào)。算法就是不斷修改各頂點(diǎn)的標(biāo)號(hào)，直至獲得標(biāo)號(hào)。若在算法運(yùn)行過程中，將每一頂點(diǎn)獲得標(biāo)號(hào)所由來的邊在圖上標(biāo)明，則算法結(jié)束時(shí)，至各頂點(diǎn)的最短路也在圖上標(biāo)示出來了。理解：貪心算法。選定初始點(diǎn)放在一個(gè)集合里，此時(shí)權(quán)值為0初始點(diǎn)搜索下一個(gè)相連接點(diǎn)，將所有相連接的點(diǎn)中離初始點(diǎn)最近的點(diǎn)納入初始點(diǎn)所在的集合，并更新權(quán)值。然后以新納入的點(diǎn)為起點(diǎn)繼續(xù)搜索，直到所有的點(diǎn)遍歷。Matlab代碼：Dijk.mfunctionmydistance,mypath=Dijk(a,sb,db);%sb為起點(diǎn)，d

3、b為終點(diǎn)n=size(a,1);visited(1:n)=0;%n為結(jié)點(diǎn)數(shù) visited為結(jié)點(diǎn)標(biāo)號(hào)distance(1:n)=inf;distance(sb)=0;%起點(diǎn)到各終點(diǎn)距離的初始化visited(sb)=1;u=sb;%u為新的P標(biāo)號(hào)頂點(diǎn)（初始點(diǎn)）parent(1:n)=0;%父節(jié)點(diǎn)的初始化%經(jīng)過以下一個(gè)for.end便可以找到最短路徑及該最短路徑對(duì)應(yīng)的最短路程for i=1:n-1%(找所有未標(biāo)號(hào)的點(diǎn)) id=find(visited=0);%查找未標(biāo)號(hào)的頂點(diǎn) for v=id %找到一個(gè)未標(biāo)號(hào)的點(diǎn)v if a(u,v)+distance(u)distance(v)%uv之間的距

4、離+起點(diǎn)到u的距離小于 v到起點(diǎn)的距離（第一次是無窮大的，所以第一次肯定滿足，下一次則找比這個(gè)點(diǎn)到u距離小的v） distance(v)=distance(u)+a(u,v);%修改標(biāo)號(hào)值 則v到原點(diǎn)的距離（權(quán)）修改。 parent(v)=u; %u是v的父節(jié)點(diǎn) end end temp=distance;%以上面的distance作為臨時(shí)的最小距離，如果下一次循環(huán)的未標(biāo)號(hào)頂點(diǎn)有更小的距離則替換 temp(visited=1)=inf;%已標(biāo)號(hào)的點(diǎn)距離換為無窮，避免再次搜索 t,u=min(temp);%找出距離最小的點(diǎn) （t是最小值，u是最小值的下標(biāo)） 最后一次循環(huán)會(huì)得到一個(gè)最小距離的點(diǎn) v

5、isited(u)=1;%標(biāo)記已經(jīng)標(biāo)號(hào)的頂點(diǎn)end%下面一段代碼用于輸出pathmypath=;%定義mypath為一個(gè)空矩陣if parent(db)=0%如果存在路 =為不等于即前面有parent點(diǎn) t=db;%終點(diǎn)標(biāo)號(hào)賦給t mypath=db%將終點(diǎn)放入路徑集合里 while t=sb%當(dāng)終點(diǎn)不是初始點(diǎn) P = parent(t);%終點(diǎn)的父節(jié)點(diǎn)令為P mypath=P mypath; t=P;%把上一個(gè)點(diǎn)的父節(jié)點(diǎn)令為下一輪循環(huán)的節(jié)點(diǎn)，繼續(xù)搜索父節(jié)點(diǎn) endendmydistance=distance(db);%最短路程main.mn=29; a=zeros(n);a(1,2)=2;a

6、(1,10)=2;a(1,13)=180;a(1,20)=216;a(1,27)=131;a(2,3)=2;a(3,4)=2;a(4,5)=2;a(5,6)=2;a(6,7)=2;a(6,22)=35;a(7,8)=2;a(8,9)=2;a(9,10)=2;a(11,12)=2;a(12,13)=2;a(13,14)=2;a(13,20)=108;a(14,15)=2;a(15,16)=2; a(16,29)=41;a(17,18)=2;a(18,19)=2;a(18,23)=309; a(18,21)=134;a(19,20)=2;a(20,24)=145;a(20,27)=281;a(20

7、,26)=206;a(21,24)=24;a(22,25)=60;a(22,28)=142;a(23,27)=126;a(24,26)=145;a(26,29)=77;a(28,29)=115;a=a+a; a(a=0)=inf; %把所有零元素替換成無窮a(1:n+1:n2)=0; %對(duì)角線元素替換成零，Matlab中數(shù)據(jù)是逐列存儲(chǔ)的for i=1:10mydistance,mypath = Dijk( a,21,i );%從公交南北到A1-A10的最短路徑mypathend二floyed算法：2.1基本思想：直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法依次構(gòu)造出個(gè)矩陣、 、，使最后得到的矩陣成

8、為圖的距離矩陣，同時(shí)也求出插入點(diǎn)矩陣以便得到兩點(diǎn)間的最短路徑。2.2基本原理2.2.1求距離矩陣把帶權(quán)鄰接矩作為距離矩陣的初值，即(1)，其中 是從到的只允許作為中間點(diǎn)的路徑中最短路的長度(2)，其中 是從到的只允許、作為中間點(diǎn)的路徑中最短路的長度%解釋：為從；為從 ()，其中是從到的只允許、作為中間點(diǎn)的路徑中最短路的長度，即是從到中間可插入任何頂點(diǎn)的路徑中最短路的長，因此即是距離矩陣。2.2.2求路徑矩陣在建立距離矩陣的同時(shí)可建立路徑矩陣，的含義是從到的最短路要經(jīng)過點(diǎn)號(hào)為的點(diǎn)， %初值每求得一個(gè)時(shí)，按下列方式產(chǎn)生相應(yīng)的新的 即當(dāng)被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在中，依次求時(shí)求得，可由來查

9、找任何點(diǎn)對(duì)之間最短的路徑2.2.3查找最短路徑若，則點(diǎn)是點(diǎn)到點(diǎn)的最短路的中間點(diǎn)。然后用同樣的方法再分頭查找。若：(1)向點(diǎn)追溯得：(2)向點(diǎn)追溯得： 步驟：到的距離：到之間的插入點(diǎn)輸入：帶權(quán)鄰接矩陣 (1) 賦初值：對(duì)所有 (2) 更新對(duì)所有，若，則 (3) 若，停止。否則，轉(zhuǎn)(2)Matlab代碼：floyed.m%輸出最短距離矩陣和最短路徑矩陣function d,r=floyd(w)n=length(w);for i=1:n for j=1:n d(i,j)=w(i,j); r(i,j)=j; endendfor k=1:n for i=1:n for j=1:n if d(i,k)+d

10、(k,j)a(i,k)+a(k,j) %如果i,j距離大于從i到k加上從k到j(luò)的距離 a(i,j)=a(i,k)+a(k,j) %則i,j距離被更新 path(i,j)=k; %k點(diǎn)加入最短路徑 end end endenddist = a(sb,db);%打印pathparent = path(sb,:); %起點(diǎn)到終點(diǎn)最短路上各頂點(diǎn)的父親點(diǎn)parent(parent=0)=sb; %如果父親點(diǎn)為0則表示該頂點(diǎn)為起點(diǎn)mypath=db;t=db; %終點(diǎn)放入路徑中while t=sb %但某點(diǎn)的父親點(diǎn)不是不是初始點(diǎn)時(shí)，繼續(xù)循環(huán) p = parent(t); %把該點(diǎn)的父親點(diǎn)賦給p mypat

11、h = p,mypath; %把p加入path中 t = p; %把p作為新的點(diǎn)繼續(xù)循環(huán)找父親點(diǎn)的父親點(diǎn)end可測試數(shù)據(jù)：n=29; a=zeros(n);a(1,2)=2;a(1,10)=2;a(1,13)=180;a(1,20)=216;a(1,27)=131;a(2,3)=2;a(3,4)=2;a(4,5)=2;a(5,6)=2;a(6,7)=2;a(6,22)=35;a(7,8)=2;a(8,9)=2;a(9,10)=2;a(11,12)=2;a(12,13)=2;a(13,14)=2;a(13,20)=108;a(14,15)=2;a(15,16)=2; a(16,29)=41;a(

12、17,18)=2;a(18,19)=2;a(18,23)=309; a(18,21)=134;a(19,20)=2;a(20,24)=145;a(20,27)=281;a(20,26)=206;a(21,24)=24;a(22,25)=60;a(22,28)=142;a(23,27)=126;a(24,26)=145;a(26,29)=77;a(28,29)=115;a=a+a; a(a=0)=inf; %把所有零元素替換成無窮a(1:n+1:n2)=0; %對(duì)角線元素替換成零，Matlab中數(shù)據(jù)是逐列存儲(chǔ)的% for i=1:10d,r=floyd(a)%從公交南北到A1-A10的最短路徑%

13、 end 二最小生成樹在連通賦權(quán)圖上求權(quán)最小的生成樹。賦權(quán)圖的具有最小權(quán)的生成樹叫做最小生成樹。1.Prim算法（貪心算法）圖論中的一種算法，可在加權(quán)連通圖里搜索最小生成樹。意即由此算法搜索到的邊子集所構(gòu)成的樹中，不但包括了連通圖里的所有頂點(diǎn)（英語：Vertex (graph theory)），且其所有邊的權(quán)值之和亦為最小。構(gòu)造連通賦權(quán)圖的最小生成樹(是鄰接矩陣)，設(shè)置兩個(gè)集合和，其中用于存放的最小生成樹中的頂點(diǎn)，集合存放的最小生成樹中的邊。令集合的初值為(即初始(出發(fā))點(diǎn)為)，集合的初值為(空集)。算法思想：從的邊中，選取具有最小權(quán)值的邊，將頂點(diǎn)加入集合中，將邊加入集合中，如此不斷重復(fù)，直到

14、時(shí)，最小生成樹構(gòu)造完畢，這時(shí)集合中包含了最小生成樹的所有邊。算法過程： ，。while 找最小邊，其中； end代碼：clcclear all;%初始化鄰接矩陣a = zeros(7);a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;a=a+a;a(a=0)=inf;%算法主體result = ; %定義一個(gè)空集放結(jié)果p=1;tb=2:length(a); %p為起點(diǎn) tb為下一個(gè)點(diǎn)while size(result,2)=length(a)-

15、1 %size(result,2)取矩陣result的第二列 temp = a(p,tb); %所有以1為起點(diǎn)的權(quán)值 temp = temp(:); %temp=temp(:)把所有的元素都拿出來，從左到右一列一列的拿，變?yōu)橐涣小?d = min(temp); %最小權(quán)值 jb,kb = find(a(p,tb)=d,1); %找出起點(diǎn)集到終點(diǎn)集的最小權(quán)值的下一個(gè)點(diǎn)（第一個(gè)）所在位置：行jb和列kb j = p(jb);k = tb(kb); result = result,j;k;d; p = p,k; tb(find(tb=k)=;endKruskal算法：從邊出發(fā)，從所有的邊當(dāng)中選一條最

16、小的邊（如果最小的邊不止一條，則任選一條即可）然后判斷這條邊的兩個(gè)端點(diǎn)是否在同一棵樹中（并查集判斷），如果已經(jīng)在同一棵樹中，則舍去這條邊，因?yàn)樵谶@之前已經(jīng)有一條比這條還短的邊連接這兩個(gè)節(jié)點(diǎn)了，如果不在，則把這兩個(gè)節(jié)點(diǎn)連到一棵樹中，并且記錄下這條邊，以此類推，直到邊數(shù)達(dá)到，此時(shí)個(gè)點(diǎn)已經(jīng)在同一棵樹中了，算法結(jié)束。輸入：圖G輸出：圖G的最小生成樹具體流程：(1)選，使得是權(quán)值最小的邊(2)若已選好，則從中選取，使得中無圈；是中權(quán)值最小的邊。(3)直到選得為止代碼：clcclear all;%初始化鄰接矩陣a(1,2,3) = 50,60;a(2,4,5) = 65,40;a(3,4,7) = 52,

17、45;a(4,5,6) = 50,30; %鄰接矩陣另一種輸入方式a(4,7) = 42;a(5,7) = 70;i,j,b= find(a); %a中非零值data = i;j;b; %存放所有非零值位置及值index = data(1:2,:); %存放非零的兩點(diǎn)loop = length(a)-1;result = ;%算法主體while length(result)loop temp = min(data(3,:); %權(quán)值最小 flag = find(data(3,:)=temp); flag = flag(1); v1 = index(1,flag); %權(quán)值最小兩點(diǎn)的第一個(gè)點(diǎn) v

18、2 = index(2,flag); %權(quán)值最小兩點(diǎn)的第二個(gè)點(diǎn) if v1=v2 %如果兩點(diǎn)不是同一個(gè)點(diǎn) result = result,data(:,flag); %加入結(jié)果集中 end index(find(index = v2) = v1; %讓兩個(gè)端點(diǎn)相同，則后面搜索時(shí)不再被選 data(:,flag) = ; index(:,flag) = ;endresult三網(wǎng)絡(luò)最大流在一定條件下，求解給定系統(tǒng)的最大流量。應(yīng)用背景：鐵路運(yùn)輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題，控制系統(tǒng)中的信息流問題，常見的人流，物流，水流，氣流，電流，現(xiàn)金流等。為解決該問題，首先引入一些必要的概念：1.網(wǎng)絡(luò)

19、與流給一個(gè)有向圖，其中為弧集，在中指定了一點(diǎn)，稱為發(fā)點(diǎn)（記為），另一點(diǎn)稱為收點(diǎn)（記為），其余的點(diǎn)叫中間點(diǎn)，對(duì)于每一條弧，對(duì)應(yīng)有一個(gè)（或簡寫為），稱為弧的容量。通常把這樣的有向圖叫做一個(gè)網(wǎng)絡(luò)，記為，其中。所謂網(wǎng)絡(luò)上的流，是指定義在弧集合，并稱為弧上的流量。2.可行流與最大流滿足下列條件的流稱為可行流：（1） 容量限制條件：對(duì)每一弧。（2） 平衡條件：對(duì)于中間點(diǎn)，流出量=流入量，即對(duì)于每個(gè)，有 ，對(duì)于發(fā)點(diǎn)，記 ，對(duì)于收點(diǎn) ，記，式中：為這個(gè)可行流的流量，即發(fā)點(diǎn)的凈輸出量。可行流總是存在的，如零流。最大流問題可以寫為如下的線性規(guī)劃模型： 3.增廣路給定一個(gè)可行流，把網(wǎng)絡(luò)中使的弧稱為飽和弧，使的弧稱為

20、非飽和弧。把稱為零流弧，的弧稱為費(fèi)零流弧。若是網(wǎng)絡(luò)中聯(lián)接發(fā)點(diǎn)和收點(diǎn)的一條路，定義路的方向是從到，則路上的弧被分為兩類：一類是弧的方向與路的方向一致，稱為前向弧，前向弧的全體即為；另一類弧與路的方向相反稱為后向弧，后向弧的全體稱為。定義：設(shè)是一個(gè)可行流， 是從到的一條路，若滿足：前向弧是非飽和弧，后向弧是非零流弧，則稱為（關(guān)于可行流）一條增廣路。Ford-Fulkerson算法流程：其中，每個(gè)頂點(diǎn)的標(biāo)號(hào)值有兩個(gè)，第一個(gè)標(biāo)號(hào)值表示在可能的增廣路上，的前驅(qū)頂點(diǎn)；的第二個(gè)編號(hào)值記為，標(biāo)志在可能的增廣路上可以調(diào)整的流量。初始化給發(fā)點(diǎn)標(biāo)號(hào)，對(duì)已標(biāo)號(hào)頂點(diǎn)的鄰接頂點(diǎn)按以下規(guī)則標(biāo)號(hào)：若，且時(shí)，令，則給頂點(diǎn)標(biāo)號(hào)為

21、，若，則不給頂點(diǎn)標(biāo)號(hào)。，且，令，則給標(biāo)號(hào)為，這里第一個(gè)標(biāo)號(hào)值，表示在可能的增廣路上，為反向??；若，則不給標(biāo)號(hào)。增流過程： 令。 若的標(biāo)號(hào)為，則；若的標(biāo)號(hào)為，則。Ford_Fulkerson.m%n表示節(jié)點(diǎn)數(shù)，C表示容量矩陣function f,wf,No=Ford_Fulkerson(n,C)for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f為零流for(i=1:n)No(i)=0;d(i)=0;end %No,d 記錄標(biāo)號(hào)while(1) No(1)=n+1; d(1)=Inf; %給發(fā)點(diǎn)vs 標(biāo)號(hào) while(1)pd=1; %標(biāo)號(hào)過程 for(i=

22、1:n)if(No(i) %選擇一個(gè)已標(biāo)號(hào)的點(diǎn)vi for(j=1:n)if(No(j)=0&f(i,j)d(i)d(j)=d(i);end elseif(No(j)=0&f(j,i)0) %對(duì)于未給標(biāo)號(hào)的點(diǎn)vj, 當(dāng) vjvi 為非零流弧時(shí) No(j)=-i;d(j)=f(j,i);pd=0; if(d(j)d(i)d(j)=d(i);end;end;end;end;end if(No(n)|pd)break;end;end %若收點(diǎn)vt得到標(biāo)號(hào)或者無法標(biāo)號(hào), 終止標(biāo)號(hào)過程 if(pd)break;end %vt 未得到標(biāo)號(hào), f 已是最大流, 算法終止 dvt=d(n);t=n; %進(jìn)入調(diào)整過程, dvt 表示調(diào)整量 while(1) if(No(t)0)f(No(t),t)=f(No(t),t)+dvt; %前向弧調(diào)整 elseif(No(t)0&f(i,j)=0)a(i,j)=b(i,j);elseif(C(i,j)0&f(i,j)=C(i,j)a(j,i)=-b(i,j);elseif(C(i,j)0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;endfor(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 賦初值for(k=1:n)pd=1; %求有向賦權(quán)圖中