运筹学与图论

1、图与网络分析( Graph Theory and Network Analysis ),1.图的基本概念与模型 2. 最小生成树问题 3.最短路问题,本章主要内容：,图论 运筹学的重要分支 主要应用领域 物理学、化学、控制论、信息论、科学管理、电子计算机等 图论理论和方法应用实例 在组织生产中，为完成某项生产任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。 一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。 各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便。,图论的起源与发展 欧拉在1736年发表了图论方面

2、的第一篇论文，解决了著名的哥尼斯堡七桥问题。 七桥问题： 哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座桥。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。图(a) 欧拉将此问题归结为如图(b)所示图形的一笔画问题。即能否从某一点开始，不重复地一笔画出这个图形，最后回到出发点。欧拉证明了这是不可能的，因为图(b)中的每个点都只与奇数条线相关联，不可能将这个图不重复地一笔画成。,图：由点及点与点的连线构成，反映了实际生活中某些对象之间的某些特定关系。 点：代表研究的对象； 连线：表示两个对象之间特定的关系。 图：是反映对象之间关系的一种

3、抽象。 一般情况下，图中点的相对位置如何，点与点之间连线的长短曲直，对反映对象之间的关系并不重要。,1.图的基本概念与模型,可见图论中的图与几何图、工程图是不一样的。,例如：在一个人群中，对相互认识这个关系我们可以用图来表示。,如果我们把上面例子中的“相互认识”关系改为“认识” 的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。下图就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。,无向图：由点和边构成的图，记作G=（V，E）。 有向图：由点和弧构成的图，记作D=（V，A）。,图的概念 图是由一些点及一些点之间的连线(不带箭头或带箭头

4、)组成的图形。 两点之间不带箭头的连线称为边，带箭头的连线称为弧。 如果一个图G由点及边所构成，则称之为无向图(也简称为图)，记为 ，式中V，E分别是G的点集合和边集合。一条连结点 的边记为 (或 )。 如果一个图D由点及弧所构成，则称为有向图，记为D=(V，A)，式中V，A分别表示D的点集合和弧集合。一条方向是从vi指向vj的弧，记为( )。,无向图的例子 其中,无向图,有向图的例子,其中,有向图,边e可表示为e=vi,vj，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。,端点,

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

6、称为无向网络，端点有序的赋权图称为有向网络。,网络（赋权图）,图的模型应用,例6.1 有甲,乙,丙,丁,戊,己6名运动员报名参加A,B,C,D,E,F 6个项目的比赛。下表中打的是各运动员报告参加的比赛项目。问6个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。,解：用图来建模。把比赛项目作为研究对象，用点表示。如果2个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。,在图中找到一个点序列，使得依次排列的两点不相邻，即能满足要求。如： 1) A,C,B,F,E,D 2) D,E,F,B,C,A,一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分

7、人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。,思考题,思考题解答： 以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如CEAFDB，就是一个符合要求的考试课程表。,A,F,E,D,C,B,A,F,E,D,C,B,树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。 树就是一个无圈的连通图。

8、,上图中，(a)就是一个树，而(b)因为图中有圈所以就不是树， (c)因为不连通所以也不是树。,2. 最小生成树问题,例6.2 乒乓求单打比赛抽签后，可用树图来表示相遇情况，如下图所示。,运动员,例6.3 某企业的组织机构图也可用树图表示。,性质1：任何树中必存在次为1的点。 性质2：n 个顶点的树必有n-1 条边。 性质3：树中任意两个顶点之间， 恰有且仅有一条链。 性质4：树连通，但去掉任一条边，必变为不连通。 性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。,给了一个图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，称之为G的生成子

9、图。在下图中，(b)和(c)都是(a)的生成子图。 如果图G的一个生成子图还是一个树，则称这个生成子图为生成树，在下图中，(c)就是(a)的生成树。 最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。,(a),(b),(c),(1)破圈法,求生成树的方法：破圈法和避圈法,生成树,（2）避圈法,破圈法：算法的步骤： 1、在给定的赋权的连通图上任找一个圈。 2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。 3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。

10、,v1,v2,v3,v4,v5,v6,4,3,5,2,1,边数n-1=5,赋权图中求最小树的方法：破圈法和避圈法,得到最小树：,Min C(T)=15,避圈法: 去掉G中所有边，得到n个孤立点；然后加边。 加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,Min C(T)=15,练习：应用破圈法求最小树,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23

11、,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,

12、23,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,min=1+4+9+3+17+23=57,练习：应用避圈法求最小树,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16

13、,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,min=1+4+9+3+17+23=57,3.最短路问题,问：如何用最短的线路将三部电话连起来？ 此问题可抽象为设ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如ABAC）。,A,B,C

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

15、 vs,v1.vn-1 必为从vs 到vn-1的最短路。,假定v1v2 v3 v4是v1 v4的最短路，则v1 v2 v3 一定是v1 v3的最短路，v2 v3 v4也一定是v2 v4的最短路。,求网络图的最短路，设图的起点是vs,终点是vt ,以vi为起点vj为终点的弧记为 (i, j) ，距离为dij,P标号(临时标号)：b(j) 起点vs到点vj的最短路长； 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的最短路长及最短路线。,0,8,6,2,2,5,4,4,11,14,7,5,10,7,12,11,v7已标号，计算结束。从v1到v7的最短路长是 11, 最短路线：