运筹学与图论PPT课件.ppt

图与网络分析( Graph Theory and Network Analysis )1.图的基本概念与模型图的基本概念与模型2. 最小生成树问题最小生成树问题3.最短路问题最短路问题本章主要内容：本章主要内容：本章主要内容：本章主要内容：•图论–运筹学的重要分支–主要应用领域•物理学、化学、控制论、信息论、科学管理、电子计算机等–图论理论和方法应用实例•在组织生产中，为完成某项生产任务，各工序之间怎样衔接，才能使生产任务完成得既快又好•一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短•各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便•图论的起源与发展–欧拉在1736年发表了图论方面的第一篇论文，解决了著名的哥尼斯堡七桥问题–七桥问题：•哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座桥当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点图(a)–欧拉将此问题归结为如图(b)所示图形的一笔画问题即能否从某一点开始，不重复地一笔画出这个图形，最后回到出发点。

欧拉证明了这是不可能的，因为图(b)中的每个点都只与奇数条线相关联，不可能将这个图不重复地一笔画成图：由点及点与点的连线构成，反映了实际生活中某些对象之间的某些特定关系 点：代表研究的对象； 连线：表示两个对象之间特定的关系图：是反映对象之间关系的一种抽象 一般情况下，图中点的相对位置如何，点与点之间连线的长短曲直，对反映对象之间的关系并不重要1.图的基本概念与模型(v1)赵赵(v2)钱钱孙孙(v3) 李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的可见图论中的图与几何图、工程图是不一样的例如：在一个人群中，对相互认识这个关系我们可以用图来例如：在一个人群中，对相互认识这个关系我们可以用图来表示a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈 如果我们把上面例子中的如果我们把上面例子中的“相互认识相互认识”关系改为关系改为“认识认识” 的关系，那么只用两点之间的联线就很难刻画他们之间的的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。

下图就关系了，这是我们引入一个带箭头的联线，称为弧下图就是一个反映这七人是一个反映这七人“认识认识”关系的图相互认识用两条反向关系的图相互认识用两条反向的弧表示的弧表示无向图：由点和边构成的图，记作无向图：由点和边构成的图，记作G=（（V，，E）有向图：由点和弧构成的图，记作有向图：由点和弧构成的图，记作D=（（V，，A）•图的概念–图是由一些点及一些点之间的连线(不带箭头或带箭头)组成的图形–两点之间不带箭头的连线称为边边，带箭头的连线称为弧弧–如果一个图G由点及边所构成，则称之为无向无向图图(也简称为图)，记为 ，式中V，E分别是G的点集合和边集合一条连结点 的边记为［ ］(或［ ］)–如果一个图D由点及弧所构成，则称为有向有向图图，记为D=(V，A)，式中V，A分别表示D的点集合和弧集合一条方向是从vi指向vj的弧，记为( )•无向图的例子 其中无向图无向图•有向图的例子 其中有向图有向图v3e7e4e8e5e6e1e2e3v1v2v4v5 边边e可表示为可表示为e=[vi,vj]，称，称vi和和vj是是边边e的的端点端点，反之称边，反之称边e为点为点vi或或vj的的关联边关联边。

若点若点vi、、vj与同一条边关联，与同一条边关联，称点称点vi和和vj相邻；若边相邻；若边ei和和ej具有公具有公共的端点，称边共的端点，称边ei和和ej相邻相邻端点端点端点端点, ,关联边关联边关联边关联边, ,相邻相邻相邻相邻 如果边如果边e的两个端点相重合，称该的两个端点相重合，称该边为边为环环如右图中边如右图中边e1为环如果两为环如果两个点之间多于一条，称为个点之间多于一条，称为多重边多重边，如，如右图中的右图中的e4和和e5，对无环、无多重边，对无环、无多重边的图称作的图称作简单图简单图v3e7e4e8e5e6e1e2e3v1v2v4v5环环, 多重边多重边, 简单图简单图 图中某些点和边的交替序列，若其中各边互不相同，且对任意vi,t-1和vit均相邻称为链用μ表示：v3e7e4e8e5e6e1e2e3v1v2v4v5 起点与终点重合的链称作圈如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通链，圈，连通图链，圈，连通图 设图设图G＝（＝（V，，E），对），对G的每一条边的每一条边(vi,vj)相应赋予数量指标相应赋予数量指标wij，，wij称为边称为边(vi,vj)的的权权,赋予权的图赋予权的图G称为网络称为网络(或或赋权图）赋权图）。

权可以代表距离、费用、通过能力权可以代表距离、费用、通过能力(容量容量)等等 端点无序的赋权图称为端点无序的赋权图称为无向网络无向网络，端点有序的赋权图称为，端点有序的赋权图称为有有向网络①①②②③③④④⑤⑤⑥⑥910201571419256 网络（赋权图）网络（赋权图）图的模型应用例6.1 有甲,乙,丙,丁,戊,己6名运动员报名参加A,B,C,D,E,F 6个项目的比赛下表中打√的是各运动员报告参加的比赛项目问6个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛ABCDEF甲√√乙√√√丙√√丁√√戊√√√己√√√解：用图来建模把比赛项目作为研究对象，用点表示如果2个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图ABCDEF 在图中找到一个点序列，使得依次排列的两点不相邻，即能满足要求如：1) A,C,B,F,E,D2) D,E,F,B,C,A 一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。

思考题思考题思考题思考题思考题解答： 以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如C—E—A—F—D—BC—E—A—F—D—B，就是一个符合要求的考试课程表A AF FE ED DC CB BA AF FE ED DC CB B 树是图论中结构最简单但又十分重要的图在自然和社会领域应用极为广泛树树就是一个无圈的连通图就是一个无圈的连通图 上图中，上图中，(a)就是一个树，而就是一个树，而(b)因为图中有圈所以就不是因为图中有圈所以就不是树，树， (c)因为不连通所以也不是树因为不连通所以也不是树v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)2. 最小生成树问题 例6.2 乒乓求单打比赛抽签后，可用树图来表示相遇情况，如下图所示AB CDEF GH运动员运动员例6.3 某企业的组织机构图也可用树图表示厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科销售科检验科检验科动力科动力科性质1：任何树中必存在次为1的点。

性质2：n 个顶点的树必有n-1 条边性质3：树中任意两个顶点之间， 恰有且仅有一条链性质4：树连通，但去掉任一条边，必变为不连通性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈v1v2v3v4v5v6 给了一个图给了一个图G=(V,E)G=(V,E)，我们保留，我们保留G G的所有点，而删掉部分的所有点，而删掉部分G G的边或者说保的边或者说保留一部分留一部分G G的边，所获得的图的边，所获得的图G G，称之为，称之为G G的生成子图在下图中，的生成子图在下图中，(b)(b)和和(c)(c)都是都是(a)(a)的生成子图的生成子图 如果图如果图G G的一个生成子图还是一个树，则称这个生成子图为生成树，在的一个生成子图还是一个树，则称这个生成子图为生成树，在下图中，下图中，(c)(c)就是就是(a)(a)的生成树的生成树 最小生成树问题最小生成树问题就是指在一个赋权的连通的无向图就是指在一个赋权的连通的无向图G G中找出一个生成树，中找出一个生成树，并使得这个生成树的所有边的权数之和为最小并使得这个生成树的所有边的权数之和为最小。

a)(b)(c)(1)(1)破圈法破圈法破圈法破圈法求生成树的方法：破圈法和避圈法求生成树的方法：破圈法和避圈法生成树（（（（2 2）避圈法）避圈法）避圈法）避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5破圈法破圈法：：算法的步骤：算法的步骤：1、在给定的赋权的连通图上任找一个圈在给定的赋权的连通图上任找一个圈2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）边，则任意去掉其中一条）3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第第1步5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数＝边数＝n-1=5赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法v1v2v3v4v5v643521得到最小树：得到最小树：Min C(T)=15避圈法:去掉G中所有边，得到n个孤立点；然后加边。

加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)5v1v2v3v4v5v6843752618v1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=15v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 6202015159 9161625253 3282817174 41 123233636练习：练习：练习：练习：应用破圈法求最小树应用破圈法求最小树v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 6202015159 9161625253 3282817174 41 123233636v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 6202015159 9161625253 3282817174 41 12323v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 6202015159 9161625253 3282817174 41 12323v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 615159 9161625253 3282817174 41 12323v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 615159 9161625253 3282817174 41 12323v v1 1v v7 7v v4 4v v3 3v v2 2v5v5v6v69 9161625253 3282817174 41 12323v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 69 9161625253 3282817174 41 12323v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 69 925253 3282817174 41 12323v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 69 925253 3282817174 41 12323v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 69 93 3282817174 41 12323v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 69 93 3282817174 41 12323v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 69 93 317174 41 12323min=1+4+9+3+17+23=57练习：练习：练习：练习：应用避圈法求最小树应用避圈法求最小树应用避圈法求最小树应用避圈法求最小树v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 6202015159 9161625253 3282817174 41 123233636v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 6202015159 9161625253 3282817174 41 123233636v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 6202015159 9161625253 3282817174 41 123233636v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 6202015159 9161625253 3282817174 41 123233636v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 6202015159 9161625253 3282817174 41 123233636v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 6202015159 9161625253 3282817174 41 123233636v v1 1v v7 7v v4 4v v3 3v v2 2v v5 5v v6 6202015159 9161625253 3282817174 41 123233636min=1+4+9+3+17+23=57min=1+4+9+3+17+23=573.最短路问题问：如何用最短的线路将三部连起来？ 此问题可抽象为设△ABC为等边三角形，，连接三顶点的路线（称为网络）。

这种网络有许多个，其中最短路线者显然是二边之和（如AB∪AC）ABCABCP 但若增加一个周转站（新点P），连接4点的新网络的最短路线为PA＋PB＋PC最短新路径之长N比原来只连三点的最短路径O要短这样得到的网络不仅比原来节省材料，而且稳定性也更好最短路问题： 从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 . 有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题因此这类问题在生产实际中得到广泛应用最短路问题的求解算法----狄克斯拉狄克斯拉(Dijkstra)(Dijkstra)标号算法标号算法狄克斯拉狄克斯拉(Dijkstra)(Dijkstra)标号算法的基本思路：标号算法的基本思路： 若序列{ vs,v1…..vn-1,vn }是从vs到vt间的最短路，则序列{ vs,v1…..vn-1 } 必为从vs 到vn-1的最短路假定v1→v2 →v3 →v4是v1 →v4的最短路，则v1 →v2 →v3一定是v1 →v3的最短路，v2 →v3 →v4也一定是v2 →v4的最短路。

v1v2v3v4v5 求网络图的最短路，设图的起点是vs,终点是vt ,以vi为起点vj为终点的弧记为 (i, j) ，距离为dijP P标号标号标号标号( (临时标号临时标号临时标号临时标号) )：b(j) —起点vs到点vj的最短路长；T T标号标号标号标号( (固定标号固定标号固定标号固定标号) )： k(i,j)=b(i)+dij，步骤：步骤： 1. 令起点令起点vs的标号为：的标号为：b(s)＝＝0 2. 找出所有找出所有vi已标号已标号vj未标号的弧集合未标号的弧集合 B={(i, j)} 如果这样的如果这样的弧不存在或弧不存在或vt已标号则计算结束；已标号则计算结束；3. 计算集合计算集合B中弧中弧k(i，，j)=b(i)+dij的标号的标号4. 选一个点标号选一个点标号 在终点在终点vl处标处标号号b(l), 返回到第返回到第2步例1 求下图v1到v7的最短路长及最短路线①①②②③③④④⑤⑤⑥⑥⑦⑦86252353421057086225441114751071211v7已标号，计算结束。

从v1到v7的最短路长是 11,最短路线： v1→ v4 → v6 → v7P标号T标号标号 从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj 注：无向图最短路的求法只将上述步骤注：无向图最短路的求法只将上述步骤2中的中的““弧弧””改改成成““边边””即可例2 求下图v1到各点的最短距离及最短路线①①②②③③④④⑤⑤⑥⑥⑦⑦⑧⑧4526178393261216180452231039612641166188122482418 所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。