[0,3,2,0,0,0;0,0,1,3,0,0;0,0,0,1,2,0;0,0,0,0,0,3;0,0,0,1,0,2;0,0,0,0,0,0]
最后, 命令窗出现“The maximum flow is:”时, 按“Enter”键,得到
0 0 f 0 0 0 0
MATLAB 程序运行结束.
[inf,1,3,2;1, inf,3,2;3,3, inf,4;2,2,4, inf]
最后, 命令窗出现“ The weight adjacent matrix of the Minimum Spanning Tree of the graph
inf 1 is: ”时, 按“Enter”键, 得到“ MST inBiblioteka inf① 1200 3
② 2
③ 1302 2 00 4
④ 2 3
⑤
⑥
⑦
⑧
在命令窗口的程序执行过程和结果如下: 在 MATLAB 的命令窗口输入 wmatch 命令窗出现“Enter the vertices number of 命 令 窗 出 现 “Enter the matrix of
S T
=n=”时, 输入 4 输 入
3. 最大流问题
Dinic 算法适用于非负权运输网络求最大流, 当 a ij A 时, cij 0 . 程序名: MF.m 执行实例: 用 Dinic 算法求解下图所示运输网络中自点 1 到点 6 的最大流. 其中, 每条弧上的数表示其容量. ② 3 ④ 3 3 ① 1 1 1 ⑥ 2 2 ③ 2 ⑤ 在命令窗口的程序执行过程和结果如下: 在 MATLAB 的命令窗口输入 MF 命令窗出现“ Enter the vertices number of the graph : n= ”时, 输入 6 命令窗出现“Enter the capacity adjacent matrix of the graph : [C (1,1),..., C ( n, n)] =”时, 输 入
[inf,4,7,3, inf,10; inf, inf,3, inf,2,3; inf, inf, inf, inf, inf,2; inf, inf, inf, inf,2, inf; inf, inf, inf, inf, inf,1; inf, inf, inf, inf, inf, inf]
1 inf 3 2
inf 3 inf inf
inf 2 ”. inf inf
如果该网络不含最小树, 则此时窗口中出现“ The graph doesn’t include a Minimum Spanning Tree. ” MATLAB 程序运行结束. 因此, 由 MATLAB 程序运行结果可得最小树为: ① 1 ② 2 ④ 3 ③
在命令窗口的程序执行过程和结果如下: 在 MATLAB 的命令窗口输入 MST_k 命令窗出现“ Enter the vertices number of the graph : n= ”时, 输入 4 命令窗出现“ Enter the weight adjacent matrix of the graph： [W (1,1),..., W ( n, n)] = ”时, 输 入
2. 最短有向路问题
Dijkstra 算法适用于非负权有向网络求最短有向路, 当 a ij A 时, wij . 程序名: SP_d.m 执行实例: 用 Dijkstra 算法求解下图所示有向网络中自点 1 到其他各点的最短路 . 其中, 每条弧上的数表示其权 值. 4 ① 3 ④ 2 ② 7 10 2 ⑤ 1 3 3 ③ 2 ⑥
[0,3,2,0,0,0;0,0,1,3,0,0;0,0,0,1,2,0;0,0,0,0,0,3;0,0,0,1,0,2;0,0,0,0,0,0]
最后, 命令窗出现“The minimum cost flow is:”时, 按“Enter”键, 得到
0 0 0 “ f 0 0 0
2 inf inf inf 1 1 inf inf inf 3 graph is: ”时, 按“Enter”键, 得到“ MST 2 inf inf inf inf ”. inf inf inf inf 2 inf 3 inf 2 inf 如果该网络不含最小树, 则此时窗口中出现“ The graph doesn’t include a Minimum Spanning Tree. ” MATLAB 程序运行结束. 因此, 由 MATLAB 程序的运行结果可得网络 G 的最小树为: ② 1 3 ① ④ 2 ⑤ 2 ③
最后, 命令窗出现 “The pre-vertix labelling of the Shortest Path (from 1 to the other) is:”时, 按“Enter”键, 得到“ SP [0,1,1,1,4,5] ” . MATLAB 程序运行结束. 因此, 由 MATLAB 程序的运行结果可知网络 G 中自点 1 到其他各点的最短路为: ② ③ 4 7 ① ⑥ 3 1 ④ 2 ⑤
3 0 0 0 0 0
2 0 0 0 0 0
0 3 0 0 0 0
0 0 2 0 0 0
0 0 0 3 2 0
命令窗出现“The maximum flow value is:”时, 按“Enter”键, 得到“ Vf 5 ”
因此, 由 MATLAB 程序的运行结果可知网络 G 中自点 1 到点 6 的最大流为: ② 3.3 ④ 3.3 3.3 ① 1.0 1.0 1.0 ⑥ 2.2 2.2 ③ 2.2 ⑤
在命令窗口的程序执行过程和结果如下： 在 MATLAB 的命令窗口输入文件名 SP_d 命令窗出现“ Enter the vertices number of the graph : n= ”时, 输入 6 命令窗出现“ Enter the weight adjacent matrix of the graph： [W (1,1),..., W (n, n)] = ”时, 输 入
第六章 图与网络分析
本章, 我们介绍解决几种网络优化问题的 MATLAB 程序.
1. 最小树问题
1.1 Dijkstra 算法 Dijkstra 算法适用于一般非负权的无向网络求最小树, 当 e E 时, w(e) . 程序名: MST_d.m 执行实例： 用 Dijkstra 算法求解下图所示网络的最小树. 其中, 每条边上的数表示该边的权值. ② 1 4 3 ① 2 ④ 2 ⑤ 2 4 4 ③ 在命令窗口的程序执行过程和结果如下： 在 MATLAB 的命令窗口输入 MST_d (Enter) 命令窗出现“ Enter the vertices number of the graph : n= ”时, 输入 5 命令窗出现“ Enter the weight adjacent matrix of the graph： [W (1,1),..., W ( n, n)] = ”时, 输 入
0 0 0 ” 1 0
MATLAB 程序运行结束. 因此, 由 MATLAB 程序的运行结果可知二分图 G 的最大基数匹配为: ① ② ③ ④ ⑤
⑥
⑦
⑧
⑨
⑩
5.2 二分图最大权对集――分派问题 增广算法适用于一般二分图求最大基数匹配, 当 eij E 时, eij 0 . 命令式文件名: WMATCH.m 执行实例: 用增广算法求解下图所示二分网络的最大权匹配. 其中, 每条边上的数表示该边的权值.
5. 最大对集问题
5.1 二分图最大基数对集 匈牙利算法算法适用于一般二分图求最大权匹配, 当 eij E 时, eij 0 且 wij 0 . 命令式文件名: MATCH.m 执行实例: 用匈牙利算法求解下图所示二分图的最大基数对集 ① ② ③ ④ ⑤
⑥
⑦
⑧
⑨
⑩
在命令窗口的程序执行过程和结果如下: 在 MATLAB 的命令窗口输入 MATCH 命令窗出现“Enter the vertices number of S : s=”时, 输入 5 命令窗出现“Enter the vertices number of T : t=”时, 输入 5 命令窗出现“Enter the matrix of the graph： [W (1,1),..., W ( s, t )] =”时, 输入
4. 最小费用流问题
该算法适用于一般非负权的运输网络求最小费用流, 当 a ij A 时, cij 0 , 且 wij . 命令式文件名: MCF.m 执行实例: 求解下图所示运输网络中自点 1 到点 6 其值为 2 的最小费用流. (每条弧上的第一个数表示其单位流的 费用, 第二个数表示其容量) ② 4.3 ④ 2.3 1.3 ① 1.1 2.1 1.1 ⑥ 5.2 2.2 ③ 2.2 ⑤ 在命令窗口的程序执行过程和结果如下: 在 MATLAB 的命令窗口输入 MCF 命令窗出现“ Enter the vertices number of the graph : n= ”时, 输入 6 命令窗出现“Enter the cost adjacent matrix of the graph : [W (1,1),..., W ( n, n)] =”时, 输入 [0,2,5,0,0,0;0,0,1,4,0,0;0,0,0,2,2,0;0,0,0,0,0,1;0,0,0,1,0,2;0,0,0,0,0,0] 命令窗出现“Enter the capacity adjacent matrix of the graph : [C (1,1),..., C ( n, n)] =”时, 输 入
1.2 Kruskal 算法 Kruskal 算法适用于一般非负权的无向网络求最小树, 当 e E 时, w(e) .
程序名: MST_k.m 执行实例： 用 Kruskal 算法求解下图所示网络的最小树. 其中, 每条边上的数表示该边的权值. ① 1 ② 3 2 2 3 ④ 4 ③