运筹学第6章-网络分析

1、第1页,网络分析Network Analysis,第2页,网 络 分 析,图与子图 图的连通与割集 树与支撑树 最小树 最短有向路 最大流 最小费用流 最大对集,第3页,图 与 子 图,图与网络 无向图的基本概念 网络的基本概念 关联矩阵和邻接矩阵 关联矩阵 邻接矩阵 主要结论 子图,第4页,无向图的基本概念,无向图G：一个有序二元组(N,E),记为G=(N,E) G的点集合： （例如：图（1）中的 N=（1，2，3，4，5）是一个无向图 的点的集合） G的边集合：E=eij且eij=ni,nj为右图无序二元组 eij的端点：有eij=ni,nj，则称ni和nj为 eij的端点，且称eij 连

2、接点 ni和nj 圈：两个端点重合为一点的边 （例如右图中的e11） 孤立点：不与任何边关联的点 （例如右图中的n5）,第5页,续（1）,关联：一条边的端点称为这条边的关联 邻接：与同一条边关联的端点称为是邻接的，同时如果两条边有一个公共端点，则称这两条边是邻接的 有限图：点和边都是有限集合的图 空图：没有任何边的图 平凡图：只有一个点的图 简单图：既没有圈也没有两条边连接同一对点的图,第6页,完全图：每一对点之间均有一条边相连的图 二分图 G=(N,E)：存在的一个二分划(S,T)，使得G的每条边有一个端点在S中，另一个端点在T中 完全二分图 G=(S,T,E)：S中的每个点与T中的每个点都

3、相连的简单二分图 简单图G的补图 :与G有相同顶点集合的简单图， 且中的两个点相邻当且仅当它们在G中 不相邻,续（2）,第7页,网络的基本概念,有向图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的每条边（弧）都赋予一个实数，并称为边（弧）的权，则连同它边（弧）上的权称为（有向）网络。,第8页,关联矩阵,第9页,

4、关联矩阵示例,右图的关联矩阵是 右图的关联矩阵是,第10页,邻接矩阵示例,图（7）的邻接矩阵是 图（8）的邻接矩阵是,第11页,主要结论,第12页,子 图,第13页,图的连通与割集,图的连通 无向图 有向图 图的割集 概 念 主要结论,第14页,无向图的路,图G中路：一个点和边交替序列 (ni,eij,nj,nk,ekl,nl)， 简单路：边不重的路 初级路：点不重的路 回路：在G中，一条至少包含一个 边并且ni=nl的 ni,nl路 简单回路：边不重的回路 初级回路：点不重的回路,第15页,连通性,点i和j点是连通的：G中存在一条（i，j）路 G是连通的：G中任意两点都是连通的 连通分支：G

5、的极大连通子图 命题6.2.1 设G有p个连通分支，则G的邻接矩 阵可以表示成分块矩阵,第16页,有 向 路,有向图G中的一条有向路：个点和弧的交错序列 (ni,aij,nj,nk,akl,nl)，记为(ni,nl)有向路 简单有向路：弧不重的有向路 初级有向路：点不重的有向路 有向回路：至少包含一条弧且ni=nj的(ni,nj)有向路 简单有向回路：弧不重的有向回路 初级有向回路：点不重的有向回路,第17页,点i和点j是强连通的：G中存在一条(i,j)有向路，也存在一条(j,i)有向路 G是强连通的：G中任意两点都是强连通的 G的强连通分支：G的极大连通子图 命题6.2.2 设G有p个强连通

6、分支，则G的邻接矩阵可以表示成如下形式：,强连通性,第18页,割 集,第19页,割集的性质,第20页,树与支撑树,树及其基本性质 概念及符号 基本性质 支撑树及其基本性质 概念及符号 基本性质,第21页,概念及符号,第22页,树的基本性质,第23页,概念及符号,第24页,支撑树的基本性质,第25页,最小树,最小树及其性质 求最小树的Kruskal算法 算法步骤 算例 算法复杂性 Dijkstra算法 算法步骤 算例 算法复杂性,第26页,最小支撑树,第27页,算法步骤,第28页,算例,第29页,计算的迭代过程,第30页,算法复杂性,第31页,算法步骤,第32页,算例,第33页,计算的迭代过程,

7、第34页,算法复杂性,第35页,最短有向路,最短有向路方程 求最短有向路的Dijkstral算法 算法步骤 算例 算法复杂性,第36页,最短有向路方程,第37页,算法步骤,第38页,算例,第39页,计算的迭代过程,第40页,算法复杂性,第41页,最大流,最大流最小割定理 基本概念 主要结论 最大流算法 算法步骤 算例 算法复杂性,第42页,基本概念,第43页,主要定理,第44页,算法步骤,第45页,算例,第46页,计算的迭代过程,第47页,算法复杂性,第48页,最小费用流,最小费用流算法 规划形式 算法步骤 算例 算法复杂性 最特殊的最小费用流运输问题 规划形式 算法步骤 算例,第49页,问

8、题,第50页,线性规划形式,第51页,对偶规划,第52页,算法步骤,第53页,算例,第54页,计算的迭代过程（1）,第55页,计算的迭代过程（2）,第56页,计算的迭代过程（3）,第57页,算法复杂性,第58页,运输问题,第59页,对偶规划,第60页,算法步骤,第61页,算例,求如图所示运输问题的最优解,第62页,迭代过程,第63页,续（1）,对偶解,第64页,第65页,续（2）,调整原始可行解,第66页,续（3）,对偶解,第67页,第68页,续（4）,20- 45 15+ 5 10- 30,调整原始可行解,第69页,续（5）,10,第70页,第71页,最大对集,二分图对集 基本概念 主要定理 二分图的最大基数对集 基本思想 算法步骤 算例 算法复杂性 二分图的最大权对集分派问题 规划形式 算法步骤 算例,第72页,基本概念,第73页,主要定理,第74页,基本思想,第75页,算法步骤,第76页,算例,求下图a所示的二分图G的最大基数对集，若初始解如下图b所示,第77页,迭代过程（1）,第78页,迭代过程（2）,第79