null 网 络 分 析 网 络 分 析马建华运筹学课件网络分析网络分析图与子图
图的连通与割集
树与支撑树
最小树
最短有向路
最大流
最小费用流
最大对集运筹学课件图
与
子
图图
与
子
图图与网络
无向图的基本概念
网络的基本概念
关联矩阵和邻接矩阵
关联矩阵
邻接矩阵
主要结论
子图
运筹学课件网络分析无
向
图
的
基
本
概
念
无
向
图
的
基
本
概
念
无向图G:一个有序二元组(N,E),记为G=(N,E)
G的点集合: (例如:图(1)中的
N=(1,2,3,4,5)是一个无向图 的点的集合)
G的边集合:E={eij}且eij={ni,nj}为 图(1)无序二元组
eij的端点:有eij={ni,nj},则称ni和nj
为eij的端点,且称eij 连接点 ni和nj
圈:两个端点重合为一点的边 (例如图(1)中的e11)
孤立点:不与任何边关联的点 (例如图(1)中的n5) 续(1)续(1)关联:一条边的端点称为这条边的关联
邻接:与同一条边关联的端点称为是邻接的,同时如果两条边有一个公共端点,则称这两条边是邻接的
有限图:点和边都是有限集合的图
空图:没有任何边的图
平凡图:只有一个点的图
简单图:既没有圈也没有两条边连接同一对点的图
续(2)续(2)完全图:每一对点之间均有一条边相连的图
二分图 G=(N,E):存在的一个二分划(S,T),使得G的每 条边有一个端点在S中,另一个端点在T中
完全二分图 G=(S,T,E):S中的每个点与T中的每个点都相连的简单二分图
简单图G的补图 :与G有相同顶点集合的简单图,
且 中的两个点相邻当且仅当它们在G中 不相邻返回网
络
的
基
本
概
念网
络
的
基
本
概
念运筹学课件♂有向图G:一个有序二员组(N,A),记为G=(N,A)
G的弧集合:A={aij}且aij={ni,nj}为有序二元组 ,
若aij={ni,nj},则称aij从ni连向nj, ni称为aij的尾, nj为 aij的头,ni称为nj的先辈,nj称为 ni的后继
有向图G的基本图:对于G的每条弧用一条边代替后得到的无向图
(有向)网络G:对(有向)图G的每条边(弧)都赋予一个实数,
并称为边(弧)的权,则连同它边(弧)上的权称为(有向)网络
关
联
矩
阵关
联
矩
阵运筹学课件关
联
矩
阵
示
例关
联
矩
阵
示
例图(7)的关联矩阵是
图(8)的关联矩阵是
返回邻
接
矩
阵邻
接
矩
阵邻
接
矩
阵
示
例邻
接
矩
阵
示
例图(7)的邻接矩阵是
图(8)的邻接矩阵是
返回主
要
结
论主
要
结
论运筹学课件网络分析♂子
图子
图运筹学课件网络分析♂图的连通与割集 图的连通与割集 图的连通
无向图
有向图
图的割集
概 念
主要结论
♂运筹学课件网络分析无
向
图
的
路无
向
图
的
路运筹学课件网络分析图G中路:一个点和边交替序列 (ni,eij,nj,…,nk,ekl,nl),
简单路:边不重的路
初级路:点不重的路
回路:在G中,一条至少包含一个边并且ni=nl的{ ni,nl}路
简单回路:边不重的回路
初级回路:点不重的回路
连
通
性连
通
性点i和j点是连通的:G中存在一条(i,j)路
G是连通的:G中任意两点都是连通的
连通分支:G的极大连通子图
命
6.2.1 设 G有p个连通分支,则G的邻接矩阵可以
示成分块矩阵
返回有
向
路有
向
路运筹学课件有向图G中的一条有向路:个点和弧的交错序列
(ni,aij,nj,…,nk,akl,nl),记为(ni,nl)有向路
简单有向路:弧不重的有向路
初级有向路:点不重的有向路
有向回路:至少包含一条弧且ni=nj的(ni,nj)有向路
简单有向回路:弧不重的有向回路
初级有向回路:点不重的有向回路
点i和点j是强连通的:G中存在一条(i,j)有向路,也存在一条(j,i)有向路
G是强连通的:G中任意两点都是强连通的
G的强连通分支:G的极大连通子图
命题6.2.2 设G有p个强连通分支,则G的邻接矩阵可以表示成如下形式:返回强连通性割
集割
集运筹学课件♂割
集
的
性
质割
集
的
性
质运筹学课件网络分析♂树
与
支
撑
树树
与
支
撑
树树及其基本性质
概念及符号
基本性质
支撑树及其基本性质
概念及符号
基本性质
♂运筹学课件网络分析概
念
及
符
号概
念
及
符
号♂运筹学课件网络分析树
的
基
本
性
质树
的
基
本
性
质♂运筹学课件网络分析概
念
及
符
号概
念
及
符
号♂运筹学课件网络分析支
撑
树
的
基
本
性
质支
撑
树
的
基
本
性
质♂运筹学课件网络分析最
小
树最
小
树最小树及其性质
求最小树的Kruskal算法
算法步骤
算例
算法复杂性
Dijkstra算法
算法步骤
算例
算法复杂性
Scilab实现♂运筹学课件网络分析最
小
支
撑
树
最
小
支
撑
树
♂运筹学课件算
法
步
骤 算
法
步
骤 运筹学课件♂算
例 算
例 运筹学课件网络分析计
算
的
迭
代
过
程 计
算
的
迭
代
过
程 运筹学课件网络分析♂算
法
复
杂
性 算
法
复
杂
性 运筹学课件网络分析♂算
法
步
骤 算
法
步
骤 运筹学课件网络分析♂算
例 算
例 运筹学课件网络分析计
算
的
迭
代
过
程 计
算
的
迭
代
过
程 运筹学课件网络分析♂算
法
复
杂
性 算
法
复
杂
性 运筹学课件网络分析♂Scilab
实
现Scilab
实
现用Scilab语句求解下列网络的最小树
1 3
2 4 2
4
2 4Scilab
命
令
及
结
果Scilab
命
令
及
结
果clear
tail=[1 1 2 2 2 3 3 4];
head=[2 3 3 4 5 4 5 5];
g=make_graph('g',0,5,tail,head); //制图
weight=[1 2 2 4 3 4 4 2]; //权向量
g('edge_weight')=weight;
t = min_weight_tree(g) //用Scilab命令求解
t = ! 1. 2. 8. 5. ! //结果
返回最短有向路最短有向路最短有向路方程
求最短有向路的Dijkstral算法
算法步骤
算例
算法复杂性
Scilab实现♂运筹学课件网络分析最
短
有
向
路
方
程最
短
有
向
路
方
程♂运筹学课件算
法
步
骤 算
法
步
骤 运筹学课件♂算
例 算
例 运筹学课件计算的迭代过程 计算的迭代过程 运筹学课件网络分析♂算
法
复
杂
性 算
法
复
杂
性 运筹学课件网络分析♂Scilab
实
现Scilab
实
现 用Scilab语言求解上述算例所示网络的最短有向路
Scilab语句:
tail=[1 1 1 2 2 3 4 4 5 5 6];
head=[2 4 6 3 4 6 3 5 2 3 5];
g=make_graph('g',1,6,tail,head); //制图
weight=[5 3 4 3 2 2 7 5 4 1 6]; //权重
g('edge_weight')=weight; //将权重赋给已制的图
[p,lp] = shortest_path(1,6,g) //用Scilab命令求解点1和点6之间的最短有向路结
果结
果 lp = 1.
p = 3. //结果
[p,lp] = shortest_path(1,5,g) //用Scilab命令求解点1和点5之间的最短有向路
lp = 2.
p = ! 2. 8. ! //结果
返回最
大
流最
大
流最大流最小割定理
基本概念
主要结论
最大流算法
算法步骤
算例
算法复杂性
Scilab实现♂运筹学课件网络分析基
本
概
念基
本
概
念♂运筹学课件主
要
定
理主
要
定
理运筹学课件网络分析算
法
步
骤 算
法
步
骤 运筹学课件算
例 算
例 运筹学课件计
算
的
迭
代
过
程 计
算
的
迭
代
过
程 运筹学课件网络分析♂算
法
复
杂
性 算
法
复
杂
性 运筹学课件♂Scilab
实
现Scilab
实
现用Scilab语言求解以上算例所示网络的最大流
Scilab语句:
clear
tail=[1 1 2 2 3 3 4 5 5 5];
head=[2 3 3 4 4 5 6 2 4 6];
g=make_graph('g',1,6,tail,head); //制图
maxcap=[8 2 6 5 5 8 9 3 6 7]; //容量
g('edge_max_cap')=maxcap; //将容量赋给已制的图
[v,phi,flag] = max_flow(1,6,g) //用Scilab语句求解最大流 结
果结
果flag = 1.
phi = ! 8. 2. 3. 5. 4. 1. 9. 0. 0. 1. !
v = 10.返回最
小
费
用
流最
小
费
用
流最小费用流算法
规划形式
算法步骤
算例
算法复杂性
最特殊的最小费用流--运输问题
规划形式
算法步骤
算例
Scilab实现♂运筹学课件问
题问
题♂运筹学课件网络分析线
性
规
划
形
式线
性
规
划
形
式运筹学课件网络分析对
偶
规
划对
偶
规
划运筹学课件网络分析♂算
法
步
骤 算
法
步
骤 运筹学课件♂算
例 算
例 运筹学课件网络分析计算的迭代过程(1) 计算的迭代过程(1) 运筹学课件网络分析 1,2,0 3,4,0
1,2,0
3,1,0 1,2,0(+s,2)(+s,2)(+a,2)计算的迭代过程(2)计算的迭代过程(2)
1,2,2 3,4,0
1,2,2
3,1,0 1,2,2 (+s,2)(+a,2)(+b,2)(-b,1)(+s,1)计算的迭代过程(3)计算的迭代过程(3)返回(-b,1)(+s,1)(+a,1)算法复杂性 算法复杂性 运筹学课件网络分析♂Scilab
实
现Scilab
实
现用Scilab语言求解以上算例所示网络的最小费用流
Scilab语句:
clear
tail=[1 1 2 2 3];
head=[2 3 3 4 4];
g=make_graph('g',1,4,tail,head);
cost=[1 3 1 3 1];
max_cap=[2 1 2 4 2];续续g('edge_cost')=cost;
g('edge_max_cap')=max_cap;
demd=[-3,0,0,3];
g('node_demand')=demd;
[c,phi,flag] = min_lcost_flow2(g)
结
果结
果flag =
1.
phi =
! 2. 1. 1. 1. 2. !
c =
11.
返回运
输
问
题运
输
问
题运筹学课件网络分析对
偶
规
划对
偶
规
划运筹学课件网络分析♂算
法
步
骤算
法
步
骤运筹学课件♂算例 算例 运筹学课件网络分析求如图所示运输问题的最优解
-45-20-30-30355040 8
6
9
9
9
12
13
7
14
9
16
5
迭
代
过
程 迭
代
过
程 运筹学课件网络分析 15
20
30
20
10
30
初始原可行解
续(1)续(1)86121014对偶解检验数null续(2)续(2)
15-
20
30+
20-
10
30调整原始可行解续(3)续(3)03666101对偶解检验数续(4)续(4)
20- 45
15+
5
10-
30调整原始可行解续(5)续(5)03366102对偶解检验数
返回最
大
对
集最
大
对
集二分图对集
基本概念
主要定理
二分图的最大基数对集
基本思想
算法步骤
算例
算法复杂性
Scilab实现
二分图的最大权对集--分派问题
规划形式
算法步骤
算例
Scilab实现 ♂运筹学课件网络分析基
本
概
念基
本
概
念♂运筹学课件网络分析主
要
定
理主
要
定
理运筹学课件网络分析♂基
本
思
想基
本
思
想运筹学课件网络分析♂算
法
步
骤 算
法
步
骤 运筹学课件网络分析♂算
例 算
例 运筹学课件网络分析求下图a所示的二分图G的最大基数对集,若初始解如下图b所示
a b
迭
代
过
程(1)迭
代
过
程(1)运筹学课件31333333517810标号 增广路
标号 增广路
迭
代
过
程(2)迭
代
过
程(2)
标号 增广路
1257108返回算
法
复
杂
性 算
法
复
杂
性 运筹学课件♂Scilab
实
现Scilab
实
现用Scilab语言求解以上算例所示网络的最大基数对集
Scilab语句:
clear
tail=[1 2 2 3 3 3 3 4 5 5 5];
head=[7 7 8 6 8 9 10 10 7 8 10];
g=make_graph('g',0,10,tail,head); //制图
[card,match] = best_match(g) //用Scilab命令求解
结
果结
果match = ! 7. 8. 6. 10. 0. 3. 1. 2. 0. 4. !
card = 4. 返回分
派
问
题分
派
问
题运筹学课件对
偶
规
划对
偶
规
划运筹学课件网络分析♂算
法
步
骤 算
法
步
骤 运筹学课件♂算
例 算
例 运筹学课件网络分析 1
2
3
2
2
1 3
2
4
2
3求如图所示的二分网络中的最大权对集
计算的迭代过程 (1)计算的迭代过程 (1)运筹学课件网络分析 4 4 4 4 4 4 4 4 0 0 0 0 0 0 0 0 2 4 2 4 1 0 2 1 2 1 3 1 2 2 3 2 标号 标号 =4 =1 =1 标号 标号 增广路计算的迭代过程(2)计算的迭代过程(2) 3 3 3 4 3 3 3 4 0 0 0 0 0 0 0 0 2 3 2 3 1 3 4 3 0 0 1 1 2 0 2 1 标号 标号 标号 标号 增广路 =3 =1 =1计算的迭代过程(3)计算的迭代过程(3) =1 =1 =2 4 4 4 4 2 3 2 3 0 1 0 0 1 1 0 0 1 3 4 3 1 1 1 0 1 0 1 1 标号 标号 标号 标号 增广路计算的迭代过程(4)计算的迭代过程(4) =1 =1 =1 1 返回 2 3 3 2 3 0 1 0 0 1 1 2 4 0 0 1 0 标号 标号 3Scilab
实
现Scilab
实
现用Scilab语言求解上述算例中所示二分网络的最大权对集
Scilab语句:
Clear
ta=[9,9,9,9,1,1,2,2,2,3,3,3,4,4,4,5,6,7,8];
hea=[1,2,3,4,5,6,5,6,7,5,6,8,6,7,8,10,10,10,10];
n=10;
g=make_graph('foo',1,n,ta,head); //制图
maxed=ones(1,19);
g('edge_max_cap')=maxed;
cost=[0,0,0,0,4,3,2,3,3,4,2,3,1,3,2,0,0,0,0];
g('edge_cost')=cost;
demd=[0,0,0,0,0,0,0,0,-4,4];
g('node_demand')=demd;
[c,phi,flag] = min_lcost_flow2(g)返回结
果结
果 flag =
1.
phi =
column 1 to 11
! 1. 1. 1. 1. 1. 0. 0. 0. 1. 0. 0. !
column 12 to 19
! 1. 1. 0. 0. 1. 1. 1. 1. !
c =
11.
返回