第五章排队论.ppt

第五章排队论.ppt网络分析
授课教师:夏少刚
运筹学课件
网络分析
图与子图
图的连通与割集
树与支撑树
最小树
最短有向路
最大流
最小费用流
最大对集
运筹学课件
图与子图
图与网络
无向图的基本概念
网络的基本概念
关联矩阵和邻接矩阵
关联矩阵
邻接矩阵
主要结论
子图
运筹学课件
网络分析
无向图的基本概念
无向图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)
3
4
5
1
2
运筹学课件
续(1)
关联:一条边的端点称为这条边的关联
邻接:与同一条边关联的端点称为是邻接的,同时如果两条边有一个公共端点,则称这两条边是邻接的
有限图:点和边都是有限集合的图
空图:没有任何边的图
平凡图:只有一个点的图
简单图:既没有圈也没有两条边连接同一对点的图
运筹学课件
续(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)的关联矩阵是
1
3
4
5
2
1
3
4
2
运筹学课件
邻接矩阵示例
图(7)的邻接矩阵是

图(8)的邻接矩阵是
1
3
4
5
2
1
3
4
2
运筹学课件