@sum(node(j): f(j,9))=flow;
@for(arc:@bnd(0,f,c));
data: c= 0 2.5 0 5.6 6.1 0 0 0 0 0 0 7.1 0 0 3.6 0 0 0 0 0 0 0 0 0 0 3.4 0 0 0 0 0 4.9 0 7.4 0 0 0 2.4 0 0 0 7.2 5.7 0 0 0 0 3.8 0 0 0 0 5.3 4.5 0 0 0 0 0 3.8 0 0 6.7 0 0 0 0 0 0 0 0 7.4 0 0 0 0 0 0 0 0 0; enddata
x=[1,1,1,2,2,3,4,4,5,5,5,6,6,6,7,7,8,9]; y=[2,4,5,3,6,8,5,7,2,6,7,3,8,9,6,9,9,9]; z=[2.5,5.6,6.1,7.1,3.6,3.4,4.9,7.4,2.4,7.2,5.7,3.8,5.3,4.5,3.8,6.7,7.4,0];
v1 2.5
5.6
6.1
4.9
v4
5.7 7.4
v7
v2 7.1 v3
3.6 3.8 3.4
2.4
7.2
5.3
v8
v5
v6 4.5
3.8
7.4
v9
6.7
设fij为从vi到vj的实际流量，得一个9阶方阵：F=( fij)
0 2.5 0 5.6 6.1 0 0 0 0 0 0 7.1 0 0 3.6 0 0 0 0 0 0 0 0 0 0 3.4 0 记容量矩阵为C = 0 0 0 0 4.9 0 7.4 0 0 0 2.4 0 0 0 7.2 5.7 0 0
99
z min
cij xij
i1 i1
s.t：
sets: city /1..9/:u; link(city,city):c,x; endsets
9
[OBJ]min=@sum(link:c*x);
ui uj nxij n 1， 0 ui n 2, 2 i j n 1.
则可以避免产生子巡回。
TSP问题的数学规划模型：
nn
目标函数：z min
cij xij
i1 i1
n
xij 1, j=1,2,3,…,n
i1
n
xij 1,
s.t：
j1
i=1,2,3,…,n
ui uj nxij n1, 2 i j n,
.
u jV
fij
u jV
f
ji
0V, ( V
f (
), i
f ),
i 1 1,9
i9
0F C,
@for(node(i)|i#ne#1#and#i#ne#9:
@sum(node(j):f(i,j))=@sum(node(j):f(j,i)));
@sum(node(j): f(1,j))=flow;
V ( f ),
若：
f
(v,u)
f
(u,v
)
0,
uV
uV
V ( f ),
则称该网络称为守恒网络。
v vs v vs ,vt
v vt
守恒网络中的流 f 称为可行流。
若存在一个可行流f *，使得对所有可行流 f 都 有V(f *)≥ V(f )成立，则称f *为最大流。
最大流模型：
maxV ( f )
0 0 3.8 0 0 0 0 5.3 4.5
0 0 0 0 0 3.8 0 0 6.7
v1 2.5
v2 7.1
v3
0 0
0 0
00 00
0 0
0 0
0 0
0 0
7.4 0
5.6
6.1
3.6 3.8 2.4
3.4
4.9
7.2
5.3
v8
v4
v5
5.7
v6 4.5
3.8
7.4
7.4
v9
v7
1 0
0 0 0 0
0 5
A
1
0 3
0
4
0
二、最大流问题
定义：设G(V,E)为有向图，若在每条边e上定义一个非 负权c，则称图G为一个网络，称c为边e的容量函数， 记为c(e)。 若在有向图G(V,E)中有两个不同的顶点vs与vt ， 若顶点vs只有出度没有入度，称vs为图G的源， 若顶点vt只有入度没有出度，称为G的汇， 若顶点v 既不是源也不是汇，称为v中间顶点。
到目前为止，TSP问题还没有有效解决方法，现有 的方法都是寻找近似最优的哈密顿圈，常用方法有边 替换法、遗传算法、模拟退火法、蚁群算法等。
对规模不大的TSP问题可将其转化为数学规划问题：
引入0-1变量：xij=
1，由第i城市进入第j城市，且i ≠ j
0，其它
nn
目标函数：z min
cij xij
该程序运行结果：
最大流：14.2
F(1,2)=2.5, F(1,4)=5.6,F(1,5)=6.1,F(2,3)=3.4,F(2,6)=1.5,
F(3,8)=3.4,F(4,5)=3.3,F(4,7)=2.3,F(5,2)=2.4,F(5,6)=7,
F(6,8)=4,F(6,9)=4.5,F(7,9)=2.3,F(8,9)=7.4,
v1 8 v2
4
vs
7
3
7
v3
3Leabharlann 5vtv4 7
设u,v网络G(V,E)的相邻顶点，边(u,v)上的函数f(u,v)
称为边(u,v)上的实际流量；
若对网络G(V,E)的任意相邻顶点u,v 均成立：
0≤ f(u,v) ≤ c(u,v) ，
称该网络为相容网络。
v1 8 v2
若v为网络G(V,E)的中间顶点， 4
无向图G v2
v4
v1
v3
v2
4
5
3
v4
v3 1
v1
邻接矩阵A=(aij)
0 1 1 0
A
1 1
0 1
1 0
1 0
0 1 0 0
0 5 1
A
5 1
0 3
3 0
4
4 0
有向图G v2
v4 v3
v1
v2
4
5
3
v4
v3 1
v1
邻接矩阵A=(aij)
0 1 0 0
A
0 1
0 1
0 0
三、旅行售货员问题（TSP问题）
一个旅行商，从城市1出发，要遍访城市1,2,3,…,n 各一次，最后返回城市1。若从城市i到j的旅费为cij，
问他应按怎样的次序访问这些城市，能使得总旅费 最少？
用图论语言描述：在赋权图中，寻找一条经过所有 节点，并回到原点的最短路。
包含图G的每个顶点的路称为哈密顿路；闭的哈密 顿路称为哈密顿圈。
e1 v1
4) 若一对顶点之间有两条以上的边联结，则这些边 称为重边．
5)既没有环也没有重边的图，称为简单图．
6) 若图G的每一条边e 都赋以一个实数w(e)，
称w(e)为边e的权，G连同边上的权称为赋权图 ,
记为：G(V,E,W)， W={w(e)| e∈E}
7) 图G的中顶点的个数，
5
称为图G的阶；图中与某 个顶点相关联的边的数目，
v4
称为该顶点的度。
v2
3 2
v3
v1
8）完全图：若无向图的任 意两个顶点之间都存在着 一条边，称此图为完全图。
2.图的矩阵表示 邻接矩阵: (以下均假设图为简单图).
图G的邻接矩阵是表示顶点之间相邻关系的矩阵： A=(aij)，
其中： aij 10或或权∞，值，若若vvii与与vvjj相不邻相邻
clc,clear x=[1,1,1,2,2,3,4,4,5,5,5,6,6,6,7,7,8,9]; y=[2,4,5,3,6,8,5,7,2,6,7,3,8,9,6,9,9,9]; z=[2.5,5.6,6.1,7.1,3.6,3.4,4.9,7.4,2.4,7.2,5.7,3.8,5.3,4.5,3.8,6. 7,7.4,0]; f=sparse(x,y,z) [flow,flowmat]=graphmaxflow(f,1,9) name1([1:9],1)='v'; name2=int2str([1:9]'); name=cellstr(strcat(name1,name2)); view(biograph(flowmat,name,'ShowWeights','on'))
v1 2.5
5.6
6.1
4.9
v4
5.7 7.4
v7
v2 7.1 v3
3.6 3.8 3.4
2.4
7.2
5.3
v8
v5
v6 4.5
3.8
7.4
v9
6.7
Matlab中求最大流的命令： graphmaxflow(f,a,b)
0 2.5 0 5.6 6.1 0 0 0 0 0 0 7.1 0 0 3.6 0 0 0 0 0 0 0 0 0 0 3.4 0 0 0 0 0 4.9 0 7.4 0 0 0 2.4 0 0 0 7.2 5.7 0 0 0 0 3.8 0 0 0 0 5.3 4.5 0 0 0 0 0 3.8 0 0 6.7 0 0 0 0 0 0 0 0 7.4 00 00 0 0000
6.7
maxV ( f )
fij
f ji 0V, ( f ),
i 1 i 1,9
s.t .u jV
u jV
V ( f ), i 9
0 F C,