圖論中一些簡單的計算，并用R語言實現。

目錄

• 最短路問題
• • Dijkstra算法
  • R語言實現
• 最大流與最小割
• • 割集的定義
  • 割集的容量
  • 最大流-最小割問題
  • R語言實現

最短路問題

求連通圖任意兩點間總權最小的路

Dijkstra算法

對每一個頂點給出一組標號，其中第一位代表從始點到該點最短路權的上界，第二位代表該點的上一個點，第三位是T或P，T表示試探性標號，是一種臨時標 號，P表示永久性標號，即這個標號不會改變。標有P的點，其第一位標號即為最短路權。算法的每一步都把某一點的T標號改為P標號，當終點被標上P時，全部計算結束。

以這個圖為例，我們要求O到T的最短路：

第一步：
（注意，從O無法一步到達的點，路權標為∞，此時只有A，B，C有路權）

第二步：
比較A，B，C的路權大小，取最小的點A，將T改為P
從A點出發，修改相鄰的B，D點的路權

第三步：
發現B的路權小于D，因此將B改為P標號
從B點出發，修改相鄰的D，E點的路權
因為從B出發到C的路權為4+1=5，小于從O直接到C的路權，因此C點路權不變，但也改為P標號

第四步：
發現E的路權小于D，因此將E改為P標號
從E點出發，修改相鄰的D，T點的路權
D點路權不變（所以第二位不用改），且小于T，改為P標號

第五步：
從D出發，修改相鄰T點的路權
T點改為P標號
算法結束

R語言實現

為了將圖用編程語言展現，我們需要將圖存為鄰接矩陣

鄰接矩陣中的$a_{ij}$表示$v_i$到$v_j$的路權，若不能一步到達則記為0，若是自己到自己也記為0

將點O,A,B,C,D,E,T分別記為1，2，3，4，5，6，7

library('igraph') library('magrittr') a1 = c(0,2,5,4,rep(0,3)) a2 = c(2,0,2,0,7,0,0) a3 = c(5,2,0,1,4,3,0) a4 = c(4,0,1,0,0,4,0) a5 = c(0,7,4,0,0,1,5) a6 = c(0,0,3,4,1,0,7) a7 = c(0,0,0,0,5,7,0) a = rbind(a1,a2,a3,a4,a5,a6,a7) g = graph.adjacency(a, mode = c('undirected'), weighted = TRUE) #生成圖,無向，數字為權重,否則當作多重邊處理 shortest.paths(g,1,7) #1到7的最短路

算出的答案為13，即O到T的最短路

還可以順便看一下最小生成樹。
樹是指連通且不含圈的無向圖，若圖的生成子圖是一棵樹，則稱為該圖的生成樹，其中具有最小權的生成樹稱為最小生成樹。

minimum.spanning.tree(g) #有權重 minimum.spanning.tree(g, algorithm = 'unweighted') #無權重

最大流與最小割

最大流問題是指在交通運輸網絡中使運輸量最大化，圖上的數字代表運輸量限制，例如下圖

割集的定義

容量網絡G=(V,E,C),$v_s,v_t$為發、收點，若有邊集E‘為E的子集，滿足：G(V,E-E’)不連通；E’’為E的真子集，而G(V,E-E’’)仍聯通，則稱E’為G的割集，記為E’=$(S,S\overline{)}$.
即：將容量網絡分為互補的兩部分，分別包含發、收點，連通這兩部分的邊稱為割集。

割集的容量

割集$(S,S\overline{)}$中所有始點在$S$，終點在$\overline{S}$的邊的容量之和

例如，邊集$(v_s,v_1),(v_1,v_3),(v_2,v_3),(v_3,v_t),(v_4,v_t)$是G的割集，按這些邊畫一條線，將圖分成$S$和$\overline{S}$，則邊集中所有從$S$指向$\overline{S}$的邊上的容量才被算作割集的容量（圖中已標黃），因此這個割集的容量是9.

最大流-最小割問題

在容量網絡中割集是由$v_s$到$v_t$的必經之路，所以任何一個可行流的流量都不會超過任一割集的容量。因此若能找到一個可行流的流量等于某一割集的容量，則該可行流為最大流，相應的割集為最小割。

以這幅圖為例，每條邊上的前一個數字表示流量限制，后一個數字表示初始可行流。

R語言實現

從$v_s$開始輸入，同理，自己到自己標為0，無法到達標為0，逆流（如$v_1$到$v_s$）也標為0.

library('igraph') #輸入的數字為流量限制 r1 = c(0,5,4,3,rep(0,4)) r2 = c(rep(0,4),5,3,0,0) r3 = c(rep(0,5),3,2,0) r4 = c(rep(0,6),2,0) r5 = c(0,5,rep(0,5),4) r6 = c(rep(0,7),3) r7 = c(rep(0,7),5) r8 = rep(0,8) adj = rbind(r1,r2,r3,r4,r5,r6,r7,r8) g = graph.adjacency(adj, mode = c('directed'), weighted = TRUE) vcount(g) #頂點數 ecount(g) #邊數 E(g) #邊的方向 E(g)$weight #表示每條邊的最大承載力（流量限制） flow1 = graph.maxflow(g,1,8,E(g)$weight) flow1

結果中cut為割集，value為最大流，flow是具體流量

總結

以上是生活随笔為你收集整理的运筹学-图论实例的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。