《运筹学》课程电子教案（PPT课件讲稿）第八章 图与网络分析

第八章图与网络分析 引论哥尼斯堡七桥问题 A D C B 简捷表示事物之间的 本质联系,归纳事物 之间的一般规律 D OR3 B

OR3 1 第八章 图与网络分析 引论 哥尼斯堡七桥问题 A B D C A B C D 简捷表示事物之间的 本质联系，归纳事物 之间的一般规律

引论图的用处 豢A、B、C、D、E 某公司的 五支球队进行循环赛 组织机构设置图 A 总公司分公司厂或 办事处 C OR3

OR3 2 引论 图的用处  A、B、C、D、E 某公司的 五支球队进行循环赛 组织机构设置图 A B C D E 总公司 分公司 工厂或 办事处

8.1图的基本概念 蜂图是由点和线构成的 点的集合V表示,V=W 不带箭头的连线叫做边(edge),边的集 合记为E={e},一条边可以用两点 [vv]表示,e=[v,] 壽带箭头的连线叫做弧(arc),弧的集合记为 A,A={ak},条弧也是用两点表示, ak=[v,v]弧有方向:v为始点,为终 OR3

OR3 3 8.1 图的基本概念 图是由点和线构成的。 点的集合V表示，V={vi} 不带箭头的连线叫做边(edge)，边的集 合记为E= { ej } ，一条边可以用两点 [ vi,vj ]表示,ej= [ vi,vj ]. 带箭头的连线叫做弧(arc),弧的集合记为 A，A= { ak },一条弧也是用两点表示， ak= [ vi,vj ],弧有方向：vi为始点，vj为终 点

图的基本概念(续) 由点和边组成的图叫做无向图,记为G=(V,E) 由点和弧组成的图叫做有向图,记为D=(V,A) 秦例1 e1 V1 e2 V3 a8 810 e3 e4 a4 a6 as a11 V6 a2 a7 V2 a5 V4 e7 无向图:点集、边集 有向图:点集、弧集 OR3

OR3 4 图的基本概念(续)  由点和边组成的图叫做无向图，记为G=（V，E）  由点和弧组成的图叫做有向图，记为D=（V，A）  例1. v1 v2 v3 v4 v1 v2 v3 v4 v5 v6 v7 e1 e2 e3 e4 e5 e6 e7 a1 a2 a8 a4 a3 a5 a6 a9 a7 a10 a11 无向图：点集、边集 有向图：点集、弧集

图的基本概念(续) 以点u为端点的边的条数,叫做点u的次 为1的点叫做悬挂点;次为0的点叫做 孤立点;次为奇数则称奇点;次为偶数 则称偶点。 癱点弧交替序列称为链;闭合的链称为圈 癱首尾相接的链称为路;闭合的路称回路 任意两点之间都有边相连,称为连通图 OR3

OR3 5 图的基本概念(续) 以点u为端点的边的条数，叫做点u的次 次为1的点叫做悬挂点；次为0的点叫做 孤立点；次为奇数则称奇点；次为偶数 则称偶点。 点弧交替序列称为链；闭合的链称为圈 首尾相接的链称为路；闭合的路称回路 任意两点之间都有边相连，称为连通图

82树 无圈的连通图称之为树 赋权无向图G=(V,E)的最小基干称为 最小支撑树 赋权有向图D=(V,A),从始点到终点 的权值最小的路称为最短路、 OR3

OR3 6 8.2 树 无圈的连通图称之为树 赋权无向图G=（V，E）的最小基干称为 最小支撑树 赋权有向图D=（V，A），从始点到终点 的权值最小的路称为最短路

8.3最短路问题 癱例6某交通网络如下图,求v到v8的最短 路线 解:用双标号法 16) V5 2(35) 6 8(v512 V8 4104 3(v3) 410 10 4V7 10 7(v59) V6 V4(v1) 6(V5,10) OR3

OR3 7 8.3 最短路问题 例6 某交通网络如下图，求v1到v8的最短 路线 解：用双标号法 v1 v2 v4 v3 v5 v6 v7 v8 6 3 1 2 2 1 6 10 4 3 10 4 4 6 v1 V2(v3,5) V3(v1,3) V4(v1,1) V5(v2,6) V6(v5,10) V7(v5,9) V8(v5,12) 6 3 1 2 2 1 6 10 4 10 4 3 6 4 V2(v1,6）

84最大流问题 引例:如下输水网络,南水北调工程, 从vs到v送水,弧旁数字前者为管道容量, 后者为现行流量,如何调整输水最多? (43 V4 (5,3) 1)(1,1 Vt (5,1) 2,1) (22) OR3

OR3 8 8.4 最大流问题 引例：如下输水网络，南水北调工程， 从vs到vt送水，弧旁数字前者为管道容量， 后者为现行流量，如何调整输水最多？ vs vt v2 v1 v4 v3 (3,3) (5,1) (1,1) (4,3) (1,1) (2,2) (3,0) (2,1) (5,3)

最大流问题的相关概念 冈络:给定了弧的容量C(v,)的有向图D= (V,A,C)叫做一个网络 可行流:各点流入量=流出量,且v的流出量 =ⅵ的流入量,这样的流称之为可行流 截集:分离始点vs和终点v的弧的集合,叫做 截集 癱截量:截集的容量叫做截量 癱增广链:一条从到的链,前向弧上可增加,后 向弧上可减少,则称此链为增广链 OR3

OR3 9 最大流问题的相关概念  网络：给定了弧的容量C（vi,vj）的有向图D= （V，A，C）叫做一个网络。  可行流：各点流入量=流出量，且vs的流出量 =vt的流入量，这样的流称之为可行流  截集：分离始点vs和终点vt的弧的集合，叫做 截集  截量：截集的容量叫做截量  增广链：一条从到的链，前向弧上可增加，后 向弧上可减少，则称此链为增广链

求最大流的方法 方法很简单:首先找到一条增广链,沿 此进行最大可能调整,再找增广链,再 调整,直到没有增广链。 秦寻找增广链的标号法:先给v标号(0, +∞),而后依次审查各条弧(v,):对 前向弧,饱和否?不饱和,给Ⅵ点标号 (v,w);对后向弧,可否减少?可 V标号(-v,l(w)),直到给v标上号,就得 到了增广链。 OR3 10

OR3 10 求最大流的方法 方法很简单：首先找到一条增广链，沿 此进行最大可能调整，再找增广链，再 调整，直到没有增广链。 寻找增广链的标号法：先给vs标号（0， +∞）,而后依次审查各条弧（vi,vj）：对 前向弧，饱和否？不饱和，给vj点标号 （vi，l(vj));对后向弧，可否减少？可，给 vj标号（-vi, l(vj) ）,直到给vt标上号，就得 到了增广链