运筹学(第6章 图与网络分析)

运筹学基础及应用(OperationsResearch)主讲：杨启明图的基本概念与模型1树图和图的最小部分树2最短路问题3第6章图与网络分析邮路问题4网络的最大流5近代图论的历史可追溯到18世纪的七桥问题—穿过Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡7桥”难题。Euler1736年证明了不可能存在这样的路线。Königsberg桥对应的图岛北区东区南区图论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图6-1就是一个表示这种关系的图。图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作：},{EVG其中:V——点集E——边集当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵陈等七人的相互认识关系我们也可以用图6-2来表示，可见图论中的图与几何图、工程图是不一样的。(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5图6-2a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图6-3如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图6-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。定义:图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=[v1,v1];e2=[v1,v2];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相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。右图中d(v1)＝４,d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次:一个图的次等于各点的次之和。链，圈，连通图图中某些点和边的交替序列，若其中各边互不相同，且对任意vi,t-1和vit均相邻称为链。用μ表示：v3e7e4e8e5e6e1e2e3v1v2v4v5},,,,,{110kkvevev起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通。二部图（偶图）图G=(V,E)的点集V可以分为两各非空子集X，Y，集X∪Y=V,X∩Y=Ø,使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二部图，(b)也是二部图，但不明显，改画为(c)时可以清楚看出。子图，部分图(支撑子图)图G1={V1、E1}和图G2={V2，E2}如果有称G1是G2的一个子图。2121EEVV和v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G图）若有，则称G1是G2的一个部分图(支撑子图)。2121EEVV，＝网络（赋权图）设图G＝（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权,赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。①②③④⑤⑥910201571419256•端点无序的赋权图称为无向网络•端点有序的赋权图称为有向网络。出次与入次有向图中，以vi为始点的边数称为点vi的出次，用d+(vi)表示；以vi为终点的边数称为点vi的入次，用表示d-(vi)；vi点的出次和入次之和就是该点的次。※有向图中，所有顶点的入次之和等于所有顶点的出次之和。图的模型应用例6.1有甲,乙,丙,丁,戊,己6名运动员报名参加A,B,C,D,E,F6个项目的比赛。下表中打√的是各运动员报告参加的比赛项目。问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—B，就是一个符合要求的考试课程表。AFEDCBAFEDCB图的基本性质：定理1任何图中，顶点次数之和等于所有边数的2倍。定理2任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：mvdvdvdVvVvVv2)()()(212m为偶数，且偶点的次之和也为偶数，所以必为偶数，即奇数点的个数必为偶数。2)(Vvvd1)(Vvvd图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等。1.邻接矩阵对于图G=（V，E），|V|=n，|E|=m，有nn阶方矩阵A=(aij)nn，其中其它之间有关联边时与当且仅当0vv1jiijav5v1v2v3v4v6433225643701010110100101011110101000110111101065432166654321vvvvvvAvvvvvv例6.2下图所表示的图可以构造邻接矩阵A如下对于赋权图G=(V,E),其中边有权,构造矩阵B=(bij)nn其中：2.关联矩阵对于图G=(V,E),|V|=n,|E|=m,有mn阶矩阵M=(mij)mn，其中:其他的一个端点是边当且仅当的两个端点是边当且仅当0ev1ev2jijiijm3.权矩阵),(jivvjiwEvvEvvwbjijijiji),(0),(101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000v1v2v3v4v5v6v7v8e1e2e3e4e5e6e7e8e9e10e11e12v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4例6.3下图所表示的图可以构造邻接矩阵M如下:M=（mij）=654321654321030303302004020576305020007204346040vvvvvvvvvvvvBv5v1v2v3v4v64332256437例6.4下图所表示的图可以构造权矩阵B如下:无向图：由点和边构成的图，记作G=（V，E）。有向图：由点和弧构成的图，记作D=（V，A）。连通图：对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。回路：若路的第一个点和最后一个点相同，则该路为回路。赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。树是图论中的重要概念，所谓树就是一个无圈的连通图。图6-11中，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。图6-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。例6.2乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。ABCDEFGH运动员例6.3某企业的组织机构图也可用树图表示。厂长人事科财务科总工程师生产副厂长经营副厂长开发科技术科生产科设备科供应科销售科检验科动力科树：无圈的连通图即为树性质1：任何树中必存在次为1的点。性质2：n个顶点的树必有n-1条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。v1v2v3v4v5v6图的最小部分树(支撑树)如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝，一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2abcfedhgbfedabcfedhgbfdgbcedabcfedhgabchabcfedhgafdgabcfedhg求树的方法：破圈法和避圈法破圈法部分树避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5赋权图中求最小树的方法：破圈法和避圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数＝n-1=5v1v2v3v4v5v643521得到最小树：MinC(T)=15避圈法（Kruskal）思想：在图中取一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈（每一步中，如果有两条或两条以上的边都是最小权的边，则从中任选一条）。5v1v2v3v4v5v6843752618v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15v1v7v4v3v2v5v620159162532817412336练习：应用破圈法求最小树v1v7v4v3v2v5v620159162532817412336v1v7v4v3v2v5v6201591625328174123v1v7v4v3v2v5v6201591625328174123v1v7v4v3v2v5v61591625328174123v1v7v4v3v2v5v61591625328174123v1v7v4v3v2v