圖與網(wǎng)絡

1. 圖與網(wǎng)絡的基本概念與數(shù)據(jù)結構

  • 一個圖是由一些點以及這些點之間得連線所組成的
  • 兩點間不帶箭頭的連線為邊,帶箭頭的連線為弧
  • 若邊e = (u,v)，則稱e連接u與v；點u，v稱為e的頂點
  • 如果兩條邊有一個公共頂點，則稱這兩條邊是鄰接的；兩個頂點重合為一點的邊稱為環(huán)

1.1 無向圖

如果一個圖是由點以及邊所構成的，則稱為無向圖，記為G = (V,E）,一個圖稱為有限圖，如果它的頂點集和邊集都有限。圖G 的頂點數(shù)用符號V 表示，邊數(shù)用 |E| 表示。

1.2 有向圖

如果一個圖是由點以及弧所構成的，則稱為有向圖，記為D = (V,A)

1.3 完全圖，二分圖

  • 設G = (V,E)是一個簡單圖，當滿足
    |E|=\frac{|V|(|V|-1)}{2}時
    每一對不同的頂點都有一條邊相連的簡單圖稱為完全圖(complete graph)。
  • 設G = (V,E)是一個圖，若存在V的一個分劃(V_1,V_2),是G的每條邊有一個頂點在V_1中,另一個在V_2中，則稱G為二分圖。

1.4 子圖

1.5 頂點的度

頂點的度是指圖中與頂點V相關聯(lián)的邊的數(shù)目

1.6 圖與網(wǎng)絡的數(shù)據(jù)結構

1.6.1 鄰接矩陣表示法

定義：就是0-1矩陣，如果元素cij為“1”表示弧從第i個到第j個點，為“0”的話表示沒有。如果是無向圖則必定cij=cji。


1.6.2 稀疏矩陣表示法

當矩陣中0的個數(shù)比較少時，可以通過僅僅儲存非0元素的坐標以及值來表示一個矩陣
像這樣：

(3,1) 35
(4,1) 21
(5,1) 51
(3,2) 21
(6,5) 13

構造系數(shù)矩陣的兩種方法
  1. S=sparse(X)—將矩陣X轉化為稀疏矩陣的形式，即矩陣X中任何零元素去除，非零元素及其下標（索引）組成矩陣S。 如果X本身是稀疏的，sparse(X)返回S
 a=[1,0,2;0,0,1;0,0,6];
  >> a
 3
 a =
 
       1     0     2
       0     0     1
       0     0     6
 
>> b=sparse(a)
 
 b =
 
    (1,1)        1
    (1,3)        2
    (2,3)        1
    (3,3)        6

  1. S = sparse(i,j,s,m,n,nzmax)——由i,j,s三個向量創(chuàng)建一個m*n的稀疏矩陣（上面的B矩陣形式），并且最多含有nzmax個元素。
    例如：B=sparse([1,2,3],[1,2,3],[0,1,2],4,4,4)
    B =
    (2,2) 1

    (3,3) 2
    其中i=[1,2,3]，稀疏矩陣的行位置；j=[1,2,3]，稀疏矩陣的列位置；s=[0,1,2]，稀疏矩陣元素值。 其位置為一一對應。
    m=4(>=max(i)),n=4(>=max(j)) (注：m和n的值可以在滿足條件的范圍內任意選取)，用于限定稀疏的大小。
    nzmax=4(>=max(i or j))，稀疏矩陣最多可以有nzmax個元素。

2. 最短路問題

從圖中的某個頂點出發(fā)到達另外一個頂點的所經(jīng)過的邊的權重和最小的一條路徑，稱為最短路徑。

2.1 兩個指定頂點之間的最短路徑

解決問題的方法：

  1. 迪杰斯特拉算法（Dijkstra算法）-----經(jīng)典

  2. 弗洛伊德算法（Floyd算法）-----用三層循環(huán)
    通過Floyd計算圖G=(V,E)中各個頂點的最短路徑時，需要引入矩陣，
    矩陣S中的元素 map[i][j] 表示頂點i(第i個頂點)到頂點j(第j個頂點)的距離。
    假設圖G中頂點個數(shù)為N，則需要對矩陣D和矩陣P進行N次更新。
    初始時，矩陣D中頂點 map[i][j] 的距離為頂點i到頂點j的權值；
    如果i和j不相鄰，則 map[i][j]=∞。 接下來開始，對矩陣D進行N次更新。
    第1次更新時，如果”a[i][j]的距離” > “a[i][k]+a[k][j]”
    a[i][0]+a[0][j]表示”i與j之間經(jīng)過第1個頂點的距離”，則更新a[i][j]為”a[i][0]+a[0][j]”。 同理，第k次更新時，如果”a[i][j]的距離” > “a[i][k-1]+a[k-1][j]”，則更新a[i][j]為”a[i][k-1]+a[k-1][j]”。更新N次之后，操作完成！

可以通過調用matlab圖論工具箱中的graphshortestpath函數(shù)直接進行計算

3. 最小生成樹問題

一般可以使用matlab圖論工具箱中的graphminspantree()函數(shù)來求得最小生成樹。
【例】



clc
clear
%將數(shù)據(jù)寫成三元組的形式
x = [2,3,3,4,4,4,5,5,5,5,6,6,6,6,6];
y = [1,1,2,1,2,3,1,2,3,4,1,2,3,4,5];
w = [56,35,21,21,57,36,51,78,68,51,60,70,68,61,13];
a = sparse(x,y,w,6,6);%轉為稀疏矩陣
ug = tril(a+a');%轉化為下三角行列式
view(biograph(ug,[],'ShowArrows','off','ShowWeight','on'));

[st,pred]=graphminspantree(ug)%生成最小生成樹
nodestr = ['L','M','N','Pe','T'];
h=view(biograph(st,nodestr,'ShowArrows','off','ShowWeights','on'));

Edges=getedgesbynodeid(h);%提取無向圖h的邊集
set(Edges,'LineColor',[0 0 0]);%設置顏色屬性
set(Edges,'LineWidth',1.5)%設置邊值屬性
>>
st =

   (3,1)       35
   (4,1)       21
   (5,1)       51
   (3,2)       21
   (6,5)       13


pred =

     0     3     1     1     1     5

其中st是一個代表生成樹的稀疏矩陣，pred是包含最小生成的祖先節(jié)點的向量
該圖的網(wǎng)絡如下：



該圖的最小生成樹如下：


4. 網(wǎng)絡最大流問題

假設現(xiàn)在有一個地下水管道網(wǎng)絡，有m根管道，n個管道交叉點，現(xiàn)在自來水廠位于其中一個點，向網(wǎng)絡中輸水，鄰居在另外一個點接水，已知由于管道修建的年代不同，有的管道能承受的水流量較大，有的較小，現(xiàn)在求在自來水廠輸入的水不限的情況下，鄰居能接到的水的最大值？
為解決該問題，可以將輸水網(wǎng)絡抽象成一個聯(lián)通的有向圖，每根管道是一條邊，交叉點為一個結點，從u流向v的管道能承受的最大流量稱為容量，設為cap[u][v]，而該管道實際流過的流量設為flow[u][v]，自來水廠稱為源點s，隔壁老王家稱為匯點t，則該問題求的是最終流入?yún)R點的總流量flow的最大值。

4.1 思路分析

關于最大流問題的解法大致分為兩類：增廣路算法和預流推進算法。增廣路算法的特點是代碼量小，適用范圍廣，因此廣受歡迎；而預流推進算法代碼量比較大，經(jīng)常達到200+行，但運行效率略高

為了便于理解，先引入一個引理：最大流最小割定理。
在一個連通圖中，如果刪掉若干條邊，使圖不聯(lián)通，則稱這些邊為此圖的一個割集。在這些割集中流量和最小的一個稱為最小割。
最大流最小割定理：一個圖的最大流等于最小割。
大開腦洞一下，發(fā)現(xiàn)此結論顯而易見，故略去證明（其實嚴格的證明反而不太好寫，但是很容易看出結論是對的，是吧）。這便是增廣路算法的理論基礎。
在圖上從s到t引一條路徑，給路徑輸入流flow，如果此flow使得該路徑上某條邊容量飽和，則稱此路徑為一條增廣路。增廣路算法的基本思路是在圖中不斷找增廣路并累加在flow中，直到找不到增廣路為止，此時的flow即是最大流?？梢钥闯觯怂惴ㄆ鋵嵕褪窃跇嬙熳钚「?。

可以通過matlab中的graphmaxflow求解,調用格式如下：
[MaxFlow, FlowMatrix, Cut] = graphmaxflow(G, SNode, TNode)
[...] = graphmaxflow(G, SNode, TNode, ...'Capacity', CapacityValue, ...)
[...] = graphmaxflow(G, SNode, TNode, ...'Method', MethodValue, ...)
【注意】有的時候K為二維矩陣，即存在不唯一的割集。

給出例子如下：


clc
clear
a = zeros(6);
x = [1,1,2,2,3,3,4,5,5];
y = [2,4,3,4,4,6,5,3,6];
w = [8,7,9,5,2,5,9,6,10];
z = sparse(x,y,w,6,6);
h = view(biograph(z,[],'ShowWeights','on'));
[M,F,K] = graphmaxflow(z,1,6)
view(biograph(F,[],'ShowWeights','on'))
set(h.Nodes(K(1,:)),'Color',[1 0 0])
>>
M =

    14


F =

   (1,2)        8
   (2,3)        5
   (1,4)        6
   (2,4)        3
   (4,5)        9
   (3,6)        5
   (5,6)        9


K =

  1×6 logical 數(shù)組

   1   1   1   1   0   0

5. 最小費用最大流問題

最小費用最大流是解決這么一種問題: 對于圖中的每一條邊來說, 除了有一個最大容量的屬性以外，還有一個費用屬性, 即流過這條邊的單位流量的花費。求解的問題為在保證從源點到匯點的流量最大的前提下使得花費最少。




【例】


下面自己編寫mincostmaxflow函數(shù)（matlab中無工具箱可以調用）：

%最小費用最大流函數(shù) 

function[flow,val]=mincostmaxflow(rongliang,cost,flowvalue); 

%第一個參數(shù)：容量矩陣；第二個參數(shù)：費用矩陣； 

%前兩個參數(shù)必須在不通路處置零 

%第三個參數(shù)：指定容量值（可以不寫，表示求最小費用最大流） 

%返回值 flow 為可行流矩陣,val 為最小費用值 

global M 

flow=zeros(size(rongliang));allflow=sum(flow(1,:));

if nargin<3 

   flowvalue=M; 

end 

while allflow<flowvalue 

   w=(flow<rongliang).*cost-((flow>0).*cost)'; 

   path=floydpath(w);%調用 floydpath 函數(shù)

   if isempty(path) 

       val=sum(sum(flow.*cost)); 

       return; 

   end 

   theta=min(min(path.*(rongliang-flow)+(path.*(rongliang-flow)==0).*M)); 

   theta=min([min(path'.*flow+(path'.*flow==0).*M),theta]); 

   flow=flow+(rongliang>0).*(path-path').*theta; 

   allflow=sum(flow(1,:)); 

end 

val=sum(sum(flow.*cost));

其中用到floydpath函數(shù)求最短路徑：

%求最短路徑函數(shù) 

function path=floydpath(w); 

global M num 

w=w+((w==0)-eye(num))*M; 

p=zeros(num); 

for k=1:num 

  for i=1:num 

     for j=1:num 

        if w(i,j)>w(i,k)+w(k,j) 

           w(i,j)=w(i,k)+w(k,j); 

           p(i,j)=k; 

        end 

     end 

  end 

end 

if w(1,num) ==M 

   path=[]; 

else 

   path=zeros(num); 

   s=1;t=num;m=p(s,t); 

   while ~isempty(m) 

       if m(1) 

           s=[s,m(1)];t=[t,t(1)];t(1)=m(1); 

           m(1)=[];m=[p(s(1),t(1)),m,p(s(end),t(end))]; 

       else 

           path(s(1),t(1))=1;s(1)=[];m(1)=[];t(1)=[]; 

       end 

   end 

end

最后編寫求解函數(shù)：

function mainexample19 

clear;clc; 

global M num 

c=zeros(6);u=zeros(6); 

c(1,2)=2;c(1,4)=8;c(2,3)=2;c(2,4)=5; 

c(3,4)=1;c(3,6)=6;c(4,5)=3;c(5,3)=4;c(5,6)=7;

u(1,2)=8;u(1,4)=7;u(2,3)=9;u(2,4)=5; 

u(3,4)=2;u(3,6)=5;u(4,5)=9;u(5,3)=6;u(5,6)=10;

num=size(u,1);M=sum(sum(u))*num^2; 

[f,val]=mincostmaxflow(u,c) 
>>
f =

     0     8     0     6     0     0
     0     0     7     1     0     0
     0     0     0     2     0     5
     0     0     0     0     9     0
     0     0     0     0     0     9
     0     0     0     0     0     0


val =

   205

6. matlab 圖論工具箱

命令名 功能
graphallshortestpaths 求圖中所有頂點對之間的最短距離
graphconncomp 找無向圖的連通分支，或有向圖的強弱連通分支
graphisdag 測試有向圖是否含有圈，不含圈返回1，否則返回0
graphisomorphism 確定兩個圖是否同構，同構返回1，否則返回0
graphisspantree 確定一個圖是否是生成樹，是返回1，否則返回0
graphmaxflow 計算有向圖的最大流
graphminspantree 在圖中找最小生成樹
graphpred2path 把前驅頂點序列變成路徑的頂點序列
graphshortestpath 求圖中指定的一對頂點間的最短距離和最短路徑
graphtopootder 執(zhí)行有向無圈圖的拓撲排序
graphtraverse 求從一頂點出發(fā)，所能遍歷圖中的頂點

給出例子如下：

【例】用matlab求解從Node1到Node11的最短路徑及長度


clc, clear
a(1,2)=2;a(1,3)=8;a(1,4)=1;
a(2,3)=1;a(2,3)=6;a(2,5)=1;
a(3,4)=7;a(3,5)=5;a(3,6)=1;a(3,7)=2;
a(4,7)=9;
a(5,6)=3;a(5,8)=2;a(5,9)=9;
a(6,7)=4;a(6,9)=6;
a(7,9)=3;a(7,10)=1;
a(8,9)=7;a(8,11)=9;
a(9,10)=1;a(9,11)=2;
a(10,11)=4;
a=a';   %matlab工具箱要求數(shù)據(jù)是下三角矩陣
[i,j,v]=find(a);
b=sparse(i,j,v,11,11) %構造稀疏矩陣
[x,y,z]=graphshortestpath(b,1,11,'Directed',false) % Directed是標志圖為有向或無向的屬性，該圖是無向圖，對應的屬性值為false，或0。
h = view(biograph(b,[],'ShowArrows','off','ShowWeights','on'))
set(h.Nodes(y),'Color',[1 0.4 0.4])
 fowEdges = getedgesbynodeid(h,get(h.Nodes(y),'ID'));
 revEdges = getedgesbynodeid(h,get(h.Nodes(fliplr(y)),'ID'));
 edges = [fowEdges;revEdges];
 set(edges,'LineColor',[1 0 0])
 set(edges,'LineWidth',1.5)

>>
x =

    13


y =

     1     2     5     6     3     7    10     9    11


z =

     0     1     6     1     2     5     3     5    10     7     9

得到最短路線如下：


【說明】

  1. find函數(shù)可以返回元素的橫縱坐標，以及值
  2. 記得變成下三角行列式
  3. sparse函數(shù)創(chuàng)造系數(shù)矩陣，只記錄矩陣中非零元素的左邊以及值
  4. graphshortestpath的第一個參數(shù)代表最短路程，第二個參數(shù)為途中的標號即最短路徑是13，最短路徑為1-2-5-6-3-7-10-9-11

7. 計劃評審法和關鍵路線法

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

  • 1. 圖的定義和基本術語 線性結構中，元素僅有線性關系，每個元素只有一個直接前驅和直接后繼；樹形結構中，數(shù)據(jù)元素（...
    yinxmm閱讀 5,656評論 0贊 3
  • 圖的定義與術語 1、圖按照有無方向分為無向圖和有向圖。無向圖由頂點和邊構成，有向圖由頂點和弧構成?；∮谢∥埠突☆^之...
    unravelW閱讀 497評論 0贊 0
  • 主要知識點 圖的概述 圖的存儲結構 圖的遍歷 最小生成樹 最短路徑 拓撲排序 關鍵路徑 一、圖的概念 圖的定義： ...
    JiaJianHuang閱讀 1,866評論 0贊 0
  • 圖的基本概念 圖由結點的有窮集合V和邊的集合E組成。圖中常常將結點成為頂點，邊是頂點的有序偶對。若兩個頂點之間存在...
    桔子滿地閱讀 1,547評論 0贊 0
  • 他緩慢的走著 步履蹣跚 一句 回來了啊 平靜的臉龐遮不住那顫抖的音嗓 忽然轉身 然而還是看到了他眼角含包的淚 走吧...
    野浪花閱讀 511評論 0贊 1

友情鏈接更多精彩內容