1. 图与网络的基本概念与数据结构
- 一个图是由一些点以及这些点之间得连线所组成的
- 两点间不带箭头的连线为边,带箭头的连线为弧
- 若边
，则称e连接u与v；点u，v称为e的顶点
- 如果两条边有一个公共顶点，则称这两条边是邻接的；两个顶点重合为一点的边称为环
1.1 无向图
如果一个图是由点以及边所构成的，则称为无向图，记为,一个图称为有限图，如果它的顶点集和边集都有限。图G 的顶点数用符号
表示，边数用
表示。
1.2 有向图
如果一个图是由点以及弧所构成的，则称为有向图，记为
1.3 完全图，二分图
- 设
是一个简单图，当满足
时
每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。 - 设
,是G的每条边有一个顶点在
中,另一个在
中，则称G为二分图。
1.4 子图
1.5 顶点的度
顶点的度是指图中与顶点相关联的边的数目
1.6 图与网络的数据结构
1.6.1 邻接矩阵表示法
定义：就是0-1矩阵，如果元素cij为“1”表示弧从第i个到第j个点，为“0”的话表示没有。如果是无向图则必定cij=cji。
1.6.2 稀疏矩阵表示法
当矩阵中0的个数比较少时，可以通过仅仅储存非0元素的坐标以及值来表示一个矩阵
像这样：
(3,1) 35
(4,1) 21
(5,1) 51
(3,2) 21
(6,5) 13
构造系数矩阵的两种方法
- 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
-
S = sparse(i,j,s,m,n,nzmax)——由i,j,s三个向量创建一个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. 最短路问题
从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径。
2.1 两个指定顶点之间的最短路径
解决问题的方法：
迪杰斯特拉算法（Dijkstra算法）-----经典
弗洛伊德算法（Floyd算法）-----用三层循环
通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入矩阵，
矩阵S中的元素 map[i][j] 表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。
假设图G中顶点个数为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之间经过第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函数直接进行计算
3. 最小生成树问题
一般可以使用matlab图论工具箱中的graphminspantree()函数来求得最小生成树。
【例】
clc
clear
%将数据写成三元组的形式
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是包含最小生成的祖先节点的向量
该图的网络如下：
该图的最小生成树如下：
4. 网络最大流问题
假设现在有一个地下水管道网络，有m根管道，n个管道交叉点，现在自来水厂位于其中一个点，向网络中输水，邻居在另外一个点接水，已知由于管道修建的年代不同，有的管道能承受的水流量较大，有的较小，现在求在自来水厂输入的水不限的情况下，邻居能接到的水的最大值？
为解决该问题，可以将输水网络抽象成一个联通的有向图，每根管道是一条边，交叉点为一个结点，从u流向v的管道能承受的最大流量称为容量，设为，而该管道实际流过的流量设为
，自来水厂称为源点
，隔壁老王家称为汇点
，则该问题求的是最终流入汇点的总流量
的最大值。
4.1 思路分析
关于最大流问题的解法大致分为两类：增广路算法和预流推进算法。增广路算法的特点是代码量小，适用范围广，因此广受欢迎；而预流推进算法代码量比较大，经常达到200+行，但运行效率略高
为了便于理解，先引入一个引理：最大流最小割定理。
在一个连通图中，如果删掉若干条边，使图不联通，则称这些边为此图的一个割集。在这些割集中流量和最小的一个称为最小割。
最大流最小割定理：一个图的最大流等于最小割。
大开脑洞一下，发现此结论显而易见，故略去证明（其实严格的证明反而不太好写，但是很容易看出结论是对的，是吧）。这便是增广路算法的理论基础。
在图上从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 数组
1 1 1 1 0 0
5. 最小费用最大流问题
最小费用最大流是解决这么一种问题: 对于图中的每一条边来说, 除了有一个最大容量的属性以外，还有一个费用属性, 即流过这条边的单位流量的花费。求解的问题为在保证从源点到汇点的流量最大的前提下使得花费最少。
【例】
下面自己编写mincostmaxflow函数（matlab中无工具箱可以调用）：
%最小费用最大流函数
function[flow,val]=mincostmaxflow(rongliang,cost,flowvalue);
%第一个参数：容量矩阵；第二个参数：费用矩阵；
%前两个参数必须在不通路处置零
%第三个参数：指定容量值（可以不写，表示求最小费用最大流）
%返回值 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 函数
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函数求最短路径：
%求最短路径函数
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
最后编写求解函数：
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 | 执行有向无圈图的拓扑排序 |
| graphtraverse | 求从一顶点出发，所能遍历图中的顶点 |
给出例子如下：
【例】用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工具箱要求数据是下三角矩阵
[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
得到最短路线如下：
【说明】
- find函数可以返回元素的横纵坐标，以及值
- 记得变成下三角行列式
- sparse函数创造系数矩阵，只记录矩阵中非零元素的左边以及值
- graphshortestpath的第一个参数代表最短路程，第二个参数为途中的标号即最短路径是13，最短路径为1-2-5-6-3-7-10-9-11
