图与网络理论培训资料

《图与网络理论培训资料》由会员分享，可在线阅读，更多相关《图与网络理论培训资料（85页珍藏版）》请在金锄头文库上搜索。

1、1,第七章图与网络理论,例1 哥尼斯堡七桥问题,哥尼斯堡七桥问题哥尼斯堡城中有一条河，河上有七座连结着两岸和河中的两个小岛，如图7.1所示。问题是一个人能否从一点出发，经过每座桥一次且仅一次，回到原出发点。,图7.1,2,第一节图的基本概念,所谓图，就是顶点和边的集合，点的集合记为V=v1, v2, vn ，边的集合记为E =e1, e2, em ， vi称为图的顶点， ej称为图的边，若边ej联结vs和vt ，则记为(vs,vt )，即ej= (vs,vt ) 。 则图可以表示为：G=(V,E)， 点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个端点。

2、在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。,3,有些图的边带有方向，这样的图称为有向图。而边不带方向的图称为无向图。 图7.7是一个无向图。,图7.8是一个有向图。,4,在一个图中，若e=(u,v) ，则称u,v是边e的端点并u,v称相邻称e是点u（v及点）的关联边。若边ei,ej有一个公共的端点u，称边ei,ej相邻。若边e的两个端点是同一顶点，则称此边为环。若两顶点之间有多于一条的边，则这些边称为多重边。如图7.7中，e7是环， e1, e2是多重边。 一个不含环和多重边的图称为简单图。含有多重边的图称为多重图。我们这里所说的图，如不

3、特别指明，都是简单图。,5,以点v为端点的边的条数称为点v的度，记作d(v),如图7.7中d(v1)=3, d(v3)=1。 度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。 不难证明：在一个图中，顶点度数的总和等于边数的倍，奇顶点的个数必为偶数。,链： 由两两相邻的点及其相关联的边构成的点边序列;如: v0 ,e1 ,v1 ,e2 ,v2 ,e3 ,v3 ,vn-1, en , vn ; v0 ,vn分别为链的起点和终点； 简单链：链中所含的边均不相同； 初等链：链中所含的点均不相同； 圈：在链中，若 v0 = vn 则称该链为圈

4、； 连通图：图中任意两点之间均至少有一 条链相连 ，,6,第二节树 树是一类结构简单而又十分有用的图。一个不含圈的连通图称为树。 设图T=(V,E)，含有n个顶点，则下列命题是等价的。 （1）T是树。 （2）T的任意两顶点之间，有唯一的链相连。 （3）T连通且有n1条边。 （4）T无圈且有n1条边。 （5）T无圈但添加一条边得唯一一圈。 （6）T连通但去掉一条边则不连通。,7,给定图G=( V, E) ，若V V , E E，并且E中的边的端点都属于V ，则称G=( V , E)是G的一个子图。特别地，若V = V ，则称G为G的支撑子图。 设T是图G的一个支撑子图，若T是一树，则称T是G的一

5、个支撑树。 给定图G=( V, E),对于G的每一条边，可赋以一个实数w(e)，称为边e的权，图G连同它边上的权称为赋权图。赋权图在图论的应用中经常出现。根据实际问题的需要，权可以有不同的实际含义，它可以表示距离、流量、时间、费用等。,8,给定图G=( V, E), 设T =( V, E)是G的一个支撑树，定义树T的权为,即支撑树T上所有边的权的总和。图G的最小支撑树就是图G中权最小的支撑树。 求图G的最小支撑树的方法是建立在求图G的支撑树基础上，只需在求图G的支撑树的算法再加适当限制。因此，求最小支撑树方法也有相应的破圈法；避圈法。,9,例2分别用破圈法，避圈法求图7.17的最小支撑树。,图

6、7.17,10,v1,v5,v2,v3,v4,2,v6,v7,v8,3,4,3,4,6,2,3,6,6,4,5,8,5,解破圈法,11,v1,v5,v2,v3,v4,2,v6,v7,v8,3,4,3,4,6,2,3,6,6,4,5,8,5,避圈法：,12,第三节最短路问题 最短路问题，一般来说就是从给定的赋权图中，寻找两点之间权最小的链（链的权即链中所有边的权之和）。许多优化问题都需要求图的最短路，如选址、管道铺设、设备更新、整数规划等问题。由于所求问题不同，需要使用不同的方法。下面我们介绍常用的算法。 一、Dijkstra算法 Dijkstra算法是求赋权有向图中，某两点之间最短路的算法。实

7、际上，它可以求某一点到其它各点的最短路。它是Dijkstra于1959年提出。目前被认为是求非负权最短路的最好的算法。,13,Dijkstra算法的基本思想是基于以下原理：若vs,vl,vj是vs到vj的最短路， vi是此路中某一点，则vs,vl,vi必是从vs到vi的最短路。此算法的基本步骤是采用标号法，给图G每一个顶点一个标号。标号分两种：一种是T标号，一种是P标号。T标号也称临时标号，它表示从vs到这一点的最短路长度的一个上界，P标号也称固定标号，它表示从vs到这一点的最短路的长度（这里最短路长度是指这条路上个边权的和）。算法每一步都把某点的T标号改变为P标号。当终点得到P标号，算法结束

8、。若要求某点到其它各点的最短路，则最多经过n-1步算法结束。,14,设lij表示边(vi,vj)的权，则Dijkstra算法步骤如下： （1）给始点以P标号P（0,0），给其它各点vj以T标号T(dj, v1)，其中，dj =l1j，（若vj与v1不相邻，则令l1j =+）。 （2）在所有T标号点中，若vk的T标号最小，则把vk的T标号改为P标号。若最小的T标号不止一个，则可任取一个改为P标号。,（3）修改所有T标号T(dj, vt)；dj =min dj, dk+lk j ,若dk+lk jdj vt= vk否则不变。 （4）当终点或全部顶点都得到P标号， 算法结束，否则返回（2）。,15,

9、例3求图7.20中，v1到v8的最短路。,16,图 7.20,v4,v2,v1,v3,v6,v5,v7,v8,9,8,3,8,3,4,2,5,6,7,6,7,10,9,4,解,P(0,0),T(9, v1),T(3, v1),T(8, v1),17,图 7.20,v4,v2,v1,v3,v6,v5,v7,v8,9,8,3,8,3,4,2,5,6,7,6,7,10,9,4,解,P(0,0),T(9, v1),T(7, v3),T(3, v1),T(8, v1),P(3, v1),18,图 7.20,v4,v2,v1,v3,v6,v5,v7,v8,9,8,3,8,3,4,2,5,6,7,6,7,1

10、0,9,4,解,P(0,0),T(9, v1),T(7, v3),T(8, v1),P(3, v1),P(7, v3),T(14, v6),T(16, v6),19,图 7.20,v4,v2,v1,v3,v6,v5,v7,v8,9,8,3,8,3,4,2,5,6,7,6,7,10,9,4,解,P(0,0),T(9, v1),T(8, v1),P(3, v1),P(7, v3),T(14, v6),P(9, v1),P(8, v1),T(17, v2),T(16, v6),20,图 7.20,v4,v2,v1,v3,v6,v5,v7,v8,9,8,3,8,3,4,2,5,6,7,6,7,10,9

11、,4,解,P(0,0),P(3, v1),P(17, v2),P(7, v3),T(14, v6),P(9, v1),P(8, v1),T(17, v2),T(16, v6),P(14, v6),P(16, v6),21,图 7.20,v4,v2,v1,v3,v6,v5,v7,v8,9,8,3,8,3,4,2,5,6,7,6,7,10,9,4,解,P(0,0),P(3, v1),P(17, v2),P(7, v3),P(9, v1),P(8, v1),P(14, v6),P(16, v6),22,例4 求图7.22中，v1到其它各点的最短路。,Dijkstra算法同样可用于求无向图的最短路。,

12、23,解,P(0,0),T(3, v1),T(4, v1),T(2, v1),24,解,P(0,0),T(3, v1),T(4, v1),T(2, v1),P(2, v1),T(7, v4),T(3, v4),P(3, v1),T(8, v2),T(9, v2),25,解,P(0,0),P(2, v1),T(7, v4),T(3, v4),P(3, v1),T(8, v2),T(9, v2),P(3, v4),T(6, v3),26,解,P(0,0),P(2, v1),T(7, v4),P(3, v1),T(8, v2),P(3, v4),T(6, v3),P(6, v3),T(7, v6),

13、T(15, v6),27,解,P(0,0),P(2, v1),T(7, v4),P(3, v1),P(3, v4),P(6, v3),T(7, v6),P(7, v6),T(15, v6),T(11, v5),P(7, v4),28,解,P(0,0),P(2, v1),P(3, v1),P(3, v4),P(6, v3),P(7, v6),T(11, v5),P(7, v4),P(11, v5),29,解,P(0,0),P(2, v1),P(3, v1),P(3, v4),P(6, v3),P(7, v6),P(7, v4),P(11, v5),30,二、逐次逼近法 前面介绍的Dijkstra

14、 算法，只适用于权为非负的赋权图中求最短路问题。逐次逼近法可用于存在负权，但无负有向回路的赋权图的最短路问题。 因为，如果dj是从v1到vj的最短路的长度，而这从条最短路的最后一条边为(vk, vj)，则从v1到vj的最短路中，从v1到vk这一段，必然也是从v1到vk的最短路。若其长度记为dk，lk j表示边(vk, vj)的权，那么dj，dk和lk j应满足下列方程：,31,逐次逼近法就是用迭代方法解这个方程。第一次逼近是找点v1到点vj由一条边所组成的最短路，其长记为dj(1)；第二次逼近是求从v1到点vj不多于两条边组成的最短路，其长记为dj(2)；以此类推，第m次逼近是求从v1到vj不

15、多于m条边组成的最短路，其长记为dj(m)。因为图中，不含负有向回路，所以从v1到vj的最短路上最多有n-1条边。从而可知，最多做n-1次逼近就可求出从v1到vj的最短路。,32,逐次逼近法步骤如下： (1) 首先令dj(1)= l1j (j =1,2,n)，若v1 与vj之间无边时，lij =+，而ljj =0；,(3) 若对所有的j，有dj(m)= dj(m-1)，则计算结束，dj(m) (j =1,2,n)即为v1到其它各点的最短路的长度，否则返回（2）。,33,例4求下图中，v1到其它各点的最短路。,34,35,36,37,38,39,40,41,42,43,44,例5求图7.24中，

16、v1到其它各点的最短路。,45,46,第四节最大流问题 给定一个有向图G = (V,E)，每条边(vi,vj)给定一个非负数cij称为边(vi,vj)容量。假设G中只有一个入度为零的点vs称为发点，只有一个出度为零的点vt称为收点，其余点称为中间点，这样的有向图称为容量网络，记为G = (V,E,C)。,47,例如图7.25就是一个容量网络。如果vs表示油田，vt表示炼油厂，图7.25表示从油田到炼油厂的输油管道网。边上的数字表示该管道的最大输油能力，中间点表示输油泵站。现在要问如何安排各管道输油量，才能使从vs到vt输油量最大？这就是本节所要介绍的最大流问题。,48,一、基本概念 给定一个容量网络G = (V,E,