《《带权图的最短路径》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《带权图的最短路径》PPT课件.ppt（38页珍藏版）》请在三一办公上搜索。
1、定义 设 G(V,E)是简单图，若对于每一个e，均有一正实数W(e)与之对应，则称W是G的权函数，并称G为带权图，记为 G(V,E,W)。我们研究带权图，一个重要的内容就是寻找某类具有最小（最大）权的子图，其中之一就是最短路问题，例如：给定一个连接各城市的铁路网络（连通的带权图），在这个网络中的两个指定的城市之间确定一条最短路。定义 设G(V,E,W)是带权图，(ei1,ei2,eik)是G中的一条路，的路长为W()W(ei)。从u到v的最短路P是指满足下列条件的路 W(P)minW()|为从u到v的路 由上述定义可以看到，如果每条边的权函数值为1，则带权图的路长与一般图的路长是一致的。,带权
2、图的最短路径,求最短路长的算法是于1959年提出来的，这是至今公认的求最短路长的最好算法，我们称它为Dijkstra算法。Dijkstra算法功能：在连通的带权图中，求从v0到v的最短路的路长。No1.p0 v0；P v0；T Vv0;d(p0)0；(tT)(d(t)；No2.(tT)(d(t)min(d(t)，d(p0)+W(p0,t)；No3.在T中选取t0,使(tT)(d(t0)d(t)；No4.p0 t0；P Pt0；T Tt0；No5.if p0 v then goto No2 else end。,例1.求图1中从v0到v5的最短路径.1.p0 v0,P v0,T v1,v2,v3,
3、v4,v5 d(p0)0,d(v1)d(v2)d(v3)d(v4)d(v5).2.d(v1)1,d(v2)4,d(v3)d(v4)d(v5).3.t0 v1 4.p0 t0 v1,P v0,v1,T v2,v3,v4,v5.5.p0v5,GoTo 2.2.d(v2)3,d(v3)8,d(v4)6,d(v5).3.t0 v2 4.p0 t0 v2,P v0,v1,v2,T v3,v4,v5 5.p0v5,GoTo 2.,2.d(v3)8,d(v4)4,d(v5).3.t0 v4.4.p0 t0 v4,P v0,v1,v2,v4,T v3,v5.5.p0v5,GoTo 2.2.d(v3)7,d(v
4、5)10.3.t0 v3 4.p0 t0 v3,P v0,v1,v2,v3,v4,T v5 5.p0 v5,GoTo 2.2.d(v5)9.3.t0 v5.4.p0 t0 v5,P v0,v1,v2,v3,v4,v5,T.5.p0 v5.,Dijkstra算法的基本思想是：将图 G 中结点集合 V 分成两部分，一部分称为具有 P 标号的集合，另一部分称为具有 T 标号的集合。所谓结点的 P标号是指从 v0 到的最短路的路长，而结点的标号是指从 v0 到的某条路径的长度。Dijkstra算法中首先将 v0 取为 P 标号结点，其余的点均为 T 标号结点，然后逐步地将具有 T 标号的结点改为 P
5、标号结点，当结点 v 也被改为 P 标号时，就找到了从 v0 到v 的最短路径的长度。,6 Euler图,Euler图的来历为konigsberg七桥问题。定义1 设 G(V,E)是无向连通图。1)若存在一条路 P，此路通过 G 中每条边且仅一次，则称此路为Euler路。2)若存在一圈 C，此圈通过 G 中每条边一次且仅一次，则称此圈为Euler圈。3)若G中有Euler 圈，则称G为Euler图。这类通过各边恰好一次的问题就是通常所说的一笔画 问题（即笔不离纸，线不重复）。,定理1 设 G(V,E)是无向连通图，那么，G是Euler图当且仅当G中每个结点都是偶结点。例1 图G如图所示，问图G
6、是否为Euler图，若是，求出其Euler圈。由于G中的六个结点均为偶结点且G连通，根据Euler定理可知，G为Euler图，仿照定理证明的办法，可得到G中的Euler圈。具体步骤如下：,在图中任意找一简单圈C(1,2,3,1)，发现还有7条边不在此圈中，边3,4不在C中且与圈中的结点3相关联。由结点3出发经过边3,4可得一简单圈C(3,4,5,3)，将C并入C得到一个新的更长的简单圈 C(1,2,3,4,5,3,1)。此时仍有4条边不在C中，边4,6不在C中且与结点4关联。由结点4出发经过边4,6又可得到一简单圈C(4,6,5,2,4)，将C并入C得到一个更长的简单圈C(1,2,3,4,6,
7、5,2,4,5,3,1)。由于G中所有的边都已在C中，故知此圈C为G中的一个Euler圈。例2在哥尼斯堡七桥问题中，由于每个结点均为奇结点，故由 Euler定理的充要条件知，该图中 不存在经过每条边一次且仅一次 的Euler圈。即该问题无解。,推论 设G为连通无向图，G中有Euler路的充要条件为G中恰有两个奇结点。证：由条件知G中有一条Euler路，除了Euler路的起点和终点外，其余的结点都是此路中所经过的点，将Euler路的起点和终点连一条边，则得到一个新的图G，G连通且是Euler图，故G中每个结点为偶结点，将G中添入的边删去，则G中恰有两个奇结点。若G中恰有两个奇结点，将这两个奇结点
8、连一条边就得到一个新图G，G连通且无奇结点，则G是Euler图，即G中有Euler圈。在G中将新添的边删去，就得到G且G中有一条Euler路。,定义2 设G(V,E)是无向图，eE，若W(Ge)W(G)。则称e为G的割边，其中W(G)表示G的连通支数。如何在恰有两个奇结点的连通图中寻找Euler路，可参考下面的方法。Fleury算法，从一个奇结点出发走到另一个奇结点：1）从一个奇结点出发，每走一边抹去一边；2）在走边的过程中，除非没有其它选择时才走割边。例3 在右图中，恰有两个奇结点4和9，故存在Euler路，按照Fleury算法可得其中一条Euler路为(9,7,8,9,10,11,12,1
9、0,3,2,1,3,4,5,6,4)。,定理2 设 G(V,E)是强连通的有向图，G中有Euler圈当且仅当G中每个结点的出度等于入度。定理3 设 G(V,E)是强连通的有向图，G中有Euler路当且仅当G中有一个结点的入度比出度多1，有一个结点的出度比入度多1，其余每个结点的出度等于入度。,7.Hamilton 图,Hamilton爵士（18051865）在1859年发明了一种游戏，用一个正实心的十二面体，它的二十个顶点标有二十个城市的名字，要求游戏者找一条沿着各边通过每个顶点一次且仅一次的闭合回路，即绕行世界问题。Hamilton以25个金币的代价将他的设计卖给了一个玩具商。由于正十二面体
10、是由12个相同的正五边形组成，且有20个顶点，该问题为怎样才能沿着12面体的棱旅行，经过每个城市恰好一次，然后回到家中。Hamilton给出了这个问题的肯定的答复。,定义1 设 G(V,E)是无向连通图 1）若存在一条路,此路通过G中每一个结点一次且仅一次,则称此路为H路。2）若存在一圈，此圈通过G中每个结点一次且仅一次，则称此圈为H圈。3）若G中有圈，则称G为H图。要指出的是，尽管从表面上看Hamilton问题和Euler问题似乎很相似，但它们之间并无必然的联系。例,是Euler图不是Hamilton图,是Hamilton图不是Euler图,定理1 设G(V,E)是H图，那么对于V的任一非空
11、子集S，有W(GS)|S|，其中W(G)表示G的连通支数。例 在图(a)中，有9个结点。当将中间层上的三个结点删去时，此时图2(a)变为图2(b)，而图2(b)的连通支数为4，由定理知它不是图。,图2(b),图2(a),定理 设G(V,E)是具有n个结点的简单无向连通图，若对任意u,vV，均有 deg(u)+deg(v)n1，则中有一条路。容易看出，定理2中的条件对图中是否存在H路是充分的而不是必要的。如图 5中的六边形G虽然不满足定理2中的条件，但G中有H路。定理3 设G(V,E)是n个结点的简单无向连通图。若对于任意的u,vV，均有deg(u)+deg(v)n，则G是H图。定理4 设G(V
12、,E)是个竞赛图(即G中任两点间有且只有一条有向边)，则G中存在一条H路。,8 二分图（二部图，偶图）,二分图的来历是各委员会选主任委员的问题。现有l个委员会，这l个委员会共有m个成员，要在这m个成员中选出各委员会的主任委员，其条件为：1)每个委员会只能有一个主任委员；2)每个委员会的主任委员必须是该委员会的成员；3)每个人最多只能担任一个委员会的主任委员（不能兼职）。问在什么条件下该问题有解，并求解。要想一般性地解决这类问题，通常分成三步来完成:1)建立数学模型；2)找出解的存在条件；3)求解。,现在为选举主任委员问题建立一个数学模型。令各委员会以及各委员会的成员为结点。若某个人是某个委员会
13、的成员，则该两结点间有边相连，否则无边相连。于是就得到了用图论方法表示的这个问题的数学模型。V1 c1,c2,c3,c4,c5,c6,c7 为委员会的集合，V2 m1,m2,m3,m4,m5,m6,m7,m8,m9为各委员会成员的集合。V1中每个结点的度数表示每个委员会有多少个成员 V2中每个结点的度数代表每个人参加了多少个委员会 这个图的特点是委员会之间无关系，各成员之间无关系，只有在委员会和成员之间才可能有关系。,定义1 设G(V,E)是简单无向图，若存在V的一个划分V1,V2，使得EV1&V2，则称G是二分图，同时称V1，V2是V的互补结点集合。当 EV1&V2 时，称G是完全二分图，记
14、为Km,n。其中 m|V1|，n|V2|。例1 令V1 v1,v2,v3 V2 v4,v5,v6 EV1&V2这是一个完全二分图，记为K3,3。例2 判断下图是否为二分图。令V1 标号为A的结点 V2 标号为B的结点 E V1&V2由二分图的定义知该图是二分图。,定理1 设G(V,E)是简单无向图，G是二分图的充要条件为G中每个圈的长度为偶数。由定理1的充要条件知此图不是二分图，因为存在长度为奇数的圈。,我们注意到，此问题的解中，任意两边均不衔接。因为若有两边在V1中衔接，则该委员会有两个主任委员，不合题意。若有两边在V2中衔接，则有人成为两个委员会的主任委员，不合题意。为了解决解的存在性问题
15、，先引入解的概念。定义2 设G(V,E)是二分图。EV1&V2,ME且M。1)若 M 中任意两边均不衔接,则称 M 是 G 中的一个匹配。Matching.2)具有边数最多的匹配称为最大匹配。Maximum Matching.3)若|M|V1|，则称 M 是从V1到V2的匹配。Matching from V1to V2.4)若|M|V1|V2|,则称 M 是完美匹配。Perfect Matching.,要解决各委员会主任委员的问题就是要找出从V1到V2的匹配。定理2 设G(V,E)是二分图。G 中有从V到V的匹配的充分必要条件是V中的任意 k 个结点至少连通V中的 k 个结点。定理3 设G(V
16、,E)是二分图。若存在正整数t,使得 1)对于V中的每个结点,至少有t条边与之关联；2)对于V中的每个结点,至多有t条边与之关联；则G中有从V到V的匹配。,因此，当给出一个二分图后。先找出V中的每个结点的度数，令rminvV1d(v)。再找出V中的每个结点的度数，令RmaxvV2 d(v)。若rR，则问题有解，取t为r即可。但这只是充分条件，若不满足，则还要用充要条件来判断。由定理3可知，若存在t0，每个委员会至少有t个成员，每个成员至多参加t个委员会，则问题一定有解。由定理2可知，若任意k个委员会至少有k个成员，则问题有解。否则无解。这就将问题解的存在性问题解决了。最后看一下求解过程。,求二
17、分图中从V到V的匹配可采用逐步调整的方法。先在图中随便找一个匹配M，然后将M调整为一个新的匹配M。调整的原则是使|M|M|。不断进行调整,直到无法调整为止。第一次选边 Mu,v,u,v,u,v,u,v,u,v,从v6开始找一条路(v,u,v,u,v,u)。在此路中,边序列交替出现在M中或不出现在M中，而且首尾两条边不在M中，称这样的路为M一增广路。在此增广路中，使用不在M中的边，删去在M中的边，得到一个新的匹配M且|M|M|。于是有 Mu,v,u,v,u,v,u,v,u,v，u,v 由于|M|V|，故M是从V到V的一个匹配。,9 平面图 Planar Graph,平面图的来历是公用设备问题。现
18、有三座楼房，三条管道，问这三条管道是否能不交叉地在一个平面内通向这三座楼房。,定义1 设 G(V,E)是无向连通图。如果存在 G 的一种图示，使得任意两条边不相交，则称 G 为平面图。定义2 在平面图的图示中，一个极小的初级圈所包围的部分称为平面图的一个区域。称该初级圈的边为此区域的边界。平面图中最大的初级圈之外的部分称为平面图的无穷域。该初级圈的边称为无穷域的边界。所谓极小初级圈是指:在此圈内不再含有其它更小的初级圈，但不排斥圈内可以有其它结点。此外，当图中无圈时，整个平面即为无穷域。一个图有且只有一个无穷域。,例1 下图是一个平面图,图中共有4个区域,它们的边界为:区域1-(a,b,f,a
19、)区域2-(b,d,f,b)区域3-(b,c,d,b)区域4-(a,b,c,d,f,a)区域4为无穷域 1750年，Euler提出凸多面体的顶点数，棱数及面数之间有如下关系：nmr2 此关系称为Euler公式。有趣的是Euler 公式同样刻划了平面图中结点的个数，边的条数及区域数之间的数量关系。,定理(Euler 1750).设G(V,E)是连通平面图，|V|n,|E|m,则nmr2。Euler公式是平面图应满足的必要条件，利用它可以判断一个图为非平面图，但对于某些图其区域数 r 不易从图示中看出，这给Euler公式的使用造成了一定的困难，为此给出下面的推论。推论设G(V,E)是简单连通的平面
20、图，|V|n,|E|m，若G中每个区域至少由三条边围成，则m3n6。例 利用推论可以判断出5个结点的完全图 K5 不是平面图，此时n5，m10，于是有 m103569.即推论1中的条件不满足，故 K5 不是平面图。例 然而用推论的结论却判断不出K3,3是否是平面图。,推论 设G(V,E)是简单连通平面图，|V|n,|E|m，若G中每个区域至少由4条边围成，则m2n4。证：由条件知G中每个区域至少由4条边围成，故诸区域的边数总和4r，又因为每条边至多是两个区域的公共边，故诸区域的边数总和2m，于是有4r2m，即rm/2，代入Euler公式得nmm/22即m2n4。由推论2知 K3,3 不是平面图
21、，因为在 K3,3 中n6，m9,于是有 91248。由上面的讨论可以看到：K5 和 K3,3 是非平面图的最小模型。1930年，波兰数学家kuratowski 给出了判别一个图是否是平面图的充分必要条件。,先介绍 K-技术：1.当两点间已有边时，在两点间增加重复边或删去重复边。2.当两点间已有边时，在边上增加一个结点，使一条边变成两条边。3.当两个结点都与第三个结点相邻，而第三个结点的度数为，删去第三个结点使两条边合为一条边。对一个图使用 K-技术不会使图的平面性有所改变，即原来是平面图使用 K-技术后仍为平面图，而本来不是平面图的，使用 K-技术后也不会成为平面图。定义 设G1,G2是两个
22、无向图，若G1与G2同构，或G1与G2通过K技术同构，则称G1与G2 K-同构。定理(Kuratowski)设G(V,E)是无向图，G是平面图的充要条件是G中不含有与 K5 或 K.K-同构的子图。,例 下面的petersen图不是平面图。去掉结点10和与之关联的边，再使用K-技术得到一个与K.同构的子图。故由kuratowski定理知petersen图不是平面图。,10 无向树(自由树)Undirected Tree,定义1 设G(V,E)是无向图，若G 连通且无圈，则称 G 为无向树。树中度数为1的结点称为树叶，树中度数大于1的结点称为分支点。定理1 设G(V,E)是无向图，|V|n，|E
23、|m，则下面六种说法是等价的。G 是树(连通，无圈)。G 无圈，且 mn1。G 连通,且 mn1。G 无圈且若给G中任一对结点间加一条边，则G中恰有一圈。G 连通且若在 G 中删去任一边，则 G 成为两个连通分图。G 中任一对结点间有且只有一条路可达。,定义2 设G(V,E)是无向图，G(V,E)是 G的生成子图，若G 是树，则称 G 是G 的生成树。定理2 设G(V,E)是无向图，G中有生成树的充要条件为G是连通图。定义2是生成树的数学模型，定理2是G中有生成树的存在性条件，下面是生成树的求解方法。破圈算法(管梅谷)(在连通的无向图G中寻找生成树)若G中无圈，结束。在G中任取一圈，删去其一条
24、边ei，GG ei，GoTo。避圈算法(Kruskal)(在连通的无向图G中寻找生成树)k0，T。若kn1，则结束。在G中任取一边 e，若T e 无圈，则T T e，kk1，GoTo。删除边 e，GG e，GoTo。,管梅谷算法是求 G 的一个连通无圈的生成子图。Kruskal 算法是求 G 的一个无圈且 mn1 的生成子图。由生成树的定义可知，这两种算法求出来的生成子图都是G 的生成树。定义3 设G(V,E,W)是无向带权图，|V|n.若 Te1,e2,en-1 是 G 的一棵生成树且 W(e i)在诸生成树中最小，则称 T 是G 的最小生成树(Optional Tree)。在一个无向带权图
25、 G 中，存在一棵最小生成树的充要条件为 G是连通的。,由于最小生成树是在带权图中产生的，故前面两个求最小生成树的算法要相应地修改一下。破圈算法(管梅谷)(在连通的无向带权图中寻找最小生成树)若G中无圈，结束。任取一圈，删去圈中具有最大权值的边e，GG e，GoTo。避圈算法(Kruskal)(在连通的无向带权图中寻找最小生成树)先将 G 中的边按权值由小到大排队，即：Ee1,e2,em。k0;T;i0。若 kn1，则结束。i i1;若T ei无圈，则T T ei;k k1;GoTo。删除边ei;GG ei;GoTo。,11 有根树 Rooted tree,定义1 设G(V,E)是有向图，若
26、1）G中有一个特殊结点r,deg(r)0；2)对于G中其它任何结点 vr,均有 deg(v)1；3)r 到 G 中任何结点均有路可达；则称G为有根树。其中，1）入度为零的结点称为根，2）出度为零的结点称为叶子，3）出度不为零的结点称为分支点。,定义2 设 T 为有根树，若给 T 的每一层结点规定了顺序，则称 T 为有序树。定义3 设T为有根树，若对于任意结点v，有 deg(v)m,则称此有根树为m叉树。如果对每个结点v有deg(v)m或者deg(v)0,则称此有根树为完全m叉树。定义4 设 T 为 m 叉有序树，而且 T 的每一层上诸结点都有规定的位置，则称 T 为 m 叉位置树。在 m 叉位置树中最重要的一种是二叉位置树，它在计算机科学中有着十分重要的应用。,
