道路与回路课件.ppt

《道路与回路课件.ppt》由会员分享，可在线阅读，更多相关《道路与回路课件.ppt（59页珍藏版）》请在优知文库上搜索。

1、1第二章 道路与回路22.1 2.1 道路与回道路与回路路3有向道路有向道路 有向图G=(V,A)中，一条有向道路有向道路指的是一个首尾相接的弧的有限非空序列 P=a1 a2 ak (k1)其中 viV(i=0.k),ajA(j=1.k)且 aj=(j=1.k)v0 和vk分别称为P的起点起点和终点终点，k称为P的长度长度。在简单图中，也可记作 P=(v0，v1，v2，vk)或 v0 v1 v2 vp 2.1 2.1 道路与回路道路与回路4简单道路简单道路 若对任意的ij有ai aj，称之为简单有向道简单有向道路路(simple path,没有重复边的路径)回路回路 若 v0=vn，称之为封闭

2、的封闭的。简单封闭有向道路（闭迹）称为有向简单回路有向简单回路。初级道路初级道路若对任意的ij有 vi vj，称之为初级道路初级道路/基本道路基本道路/路径路径(elementry or primary)。圈圈若对任意的ij有vi vj 而例外地v0=vn，称之为初初级回路级回路/圈圈(cycles)。无向图具有完全类似的定义。2.1 2.1 简单道路与圈简单道路与圈52.1 2.1 道路与回路道路与回路练习：找出上图结点1至结点9的简单道路和初级道路，1到1的有向回路和圈。6容易证明：定理定理2-1（1）基本道路是简单道路；（2）如果存在u到v的道路，则存在u到v 的基本道路；(3)n阶图的

3、基本道路长度不超过n-1;(4)n阶图的圈的长度不超过n.2.1 基本道路基本道路7定理定理2-2 无向图G=(V,E)，u,v V 且 uv。若 u,v 之间存在两条不同的路，则 G 中存在一条回路。证明证明（构造法）定理定理2-3 无向图G=(V,E)中每个顶点的度均为偶数，且至少有一个顶点不是孤立点，则 G 中存在一条回路。证明证明（反证法）设v不是孤立点，从v出发的最长简单路径经过的顶点是v0(=v)v1vn-1vn，则必存在0in使得vn=vi，否则,因为vn的度是偶数，存在与vn邻接另一个顶点u,从而得到一条更长的简单路径。矛盾！2.1 2.1 道路与回路的关系道路与回路的关系8可

4、达性可达性 对于有向图G=(V,A)中，若从 vi 到 vj 存在一条路，则称从 vi 到 vj 是可达的，或称 vi 可达 vj。对无向图 G=(V,E)，结点间的可达性是对称的。连通性连通性 对于无向图G=(V,E)，任意两点之间可达时，称G为连通的（连通图）。G中的一个极大连通子图称为G的一个连通分支。一个图总是由一些连通分支构成的。G的连通分支数，记为W(G)。2.2 2.2 连通性连通性9强连通性强连通性对于有向图G=(V,A)，如果任意两点之间相互可达，则称G为强连通的.弱弱 连通性连通性对于有向图G=(V,A),若不考虑弧的方向后得到的无向图是连通的，则称有向图G是弱连通的。2.

5、2 2.2 有向图的连通性有向图的连通性10定理定理2-5 G=(V,E)，n=|V|，若对任意 u,v V 且 uv，都有：Deg(u)+Deg(v)n1，则 G 连通。证明证明(反证法)设G可分为不连通的两部分G1=(V1,E1)和G2=(V2,E2)，选取 uV1,vV2 则 Deg(u)=|V1|-1，Deg(v)|V2|-1，故 Deg(u)+Deg(v)00 其他 可求得G的道路矩阵 P。算法复杂度 O(n4)2.2 2.2 道路矩阵道路矩阵14道路矩阵可以通过二值矩阵的逻辑运算求得。定义定义 二值元素的逻辑运算：0 0=0，0 1=1 0=1，1 1=1 0 0=0，0 1=1

6、0=0，1 1=1定义定义 二值矩阵的逻辑运算。设有矩阵A=(aij)，B=(bij)，矩阵元素值域为 0,1，定义运算：ijijikkjababijnijk=1(AB)=(AB)=()2.2 2.2 道路矩阵的计算道路矩阵的计算15定义定义 A(k)=A(k1)A (k2)，A(1)=A注意 A(k)与Ak 的区别定理定理2-12 设 Ann 是图G的邻接矩阵，若从vi 到vj存在长度为 l 的路，则 A(l)ij=1，否则 A(l)ij=0。证明证明 对 l 作归纳；或直接引用定理2-11。2.2 2.2 道路矩阵的计算道路矩阵的计算16Warshall算法算法 设 A nn是图G的邻接矩

7、阵，求G的道路矩阵P。1.P A2.for i=1 to n do3.for j=1 to n do4.for k=1 to n do5.pjk pjk(pji pik)计算复杂度 O(n3)2.2 2.2 道路矩阵及道路矩阵及WarshallWarshall算法算法初始：pij表示有无长度为1 的直达路径第i次外层循环结束时：pjk表示有中间通过v1,v2,vi的路径。17例例 图G的邻接矩阵A如右，使用Warshall算法求G的道路矩阵P。01000011A=11011000解解 P A01000011P=110110002.2 2.2 道路矩阵及道路矩阵及WarshallWarshall

8、算法算法18(1)i=101000011P=11011000 j=1,2,3,4 增量方向i=1 矩阵元素处理次序：p11，p12，p13，p14，p21，p22，p31，p41，p44，2.2 2.2 道路矩阵及道路矩阵及WarshallWarshall算法算法19 如：p11=p11(p1i pi1)=p11(p11 p11)=0 p12=p12(p1i pi2)=p12(p11 p12)=1 p13=p13(p1i pi3)=p13(p11 p13)=0 01000011P=11011100 结果为2.2 2.2 道路矩阵及道路矩阵及WarshallWarshall算法算法202.3 图

9、上的搜索图上的搜索可以使用搜索的方法判断从一个顶点u到另一个顶点v是否有路径。深度优先DFS从顶点u出发检查其后继u1是否，如果不是，则从u1开始进行深度优先搜索；如果没有后继,则回溯，直至找到或者没有可搜索的顶点。212.3 图上的搜索图上的搜索广度优先BFS从u出发，首先检查其所有的直接后继是否等于；然后依次检查这些后继的直接后继，直到找到或者没有可遍历顶点。练习：编写一个使用深度优先或者广度优先搜索判定两个点之间是否有道路的程序。22Euler回路回路 若连通图 G=(V,E)中存在一条简单回路（无重复边）经过G的所有边，则称该回路为G中的一条Euler回路。存在Euler回路的图称为E

10、uler图。定理定理2-6-1 设有连通图G=(V,E)，则下述命题等价：(1)G是一个Euler图；(2)G的每一个顶点的度是偶数；证明证明（略）2.4 Euler 2.4 Euler 回路回路23注意定理中对图的连通性的假定；Euler回路经过图的所有边一次且仅仅一次。定理对非简单图也成立；定理的证明过程给出了为一个Euler图构造Euler回路的构造算法。定理定理2-7 设连通图G=(V,E)中恰有2个顶点度为奇数，则G存在Euler道路。证明证明 连接两个奇度数结点形成Euler图，再删除该边即可。2.4 Euler 2.4 Euler 回路回路24有向图的有向图的Euler回路回路

11、若有向连通图 G=(V,A)中存在一条简单有向回路经过G的所有弧，则称该回路为G中的一条Euler回路，称该图为Euler有向图。定理定理2-6-2 设连通有向图G=(V,A)，则下述命题等价：(1)G是一个Euler有向图；(2)G的每一个顶点的入度等于出度；证明证明（略）2.4 Euler 2.4 Euler 回路回路25Hamilton路路 若连通图 G=(V,E)中存在一条初级道路（无重复顶点）经过G中每个顶点一次，则称该道路为G中的一条Hamilton路。存在Hamilton回路（圈）的图称 为Hamilton图。Hamilton路经过图的所有顶点一次且仅仅一次。引入记号：G=(V,

12、E)，SV。从G中去除S中的顶点及其关联边得到的G的子图记为GS。2.5 Hamilton 2.5 Hamilton 道路道路262.5 Hamilton 2.5 Hamilton 图图构造Hamilton圈的简单规则：Halmilton圈含n条边；Halmilton圈正好包含每个结点的两条关联边，其他边可以删除；左图如有H圈，则必包含三个二度结点的邻接边，从而中心结点至少有三个邻接边包含在其中，故不可能有圈。27定理定理2-8 若G=(V,E)是一个Hamilton图，SV且S，则 G的子图GS的连通分支数 W(GS)|S|证明证明 记G中H-回路为C，C中包含了G中所有顶点。考察CS：每从

13、C中去除属于S的一个顶点，连通分支数至多增加1（第一次以及当该顶点处于边缘时操作不会增加连通分支数），故 W(CS)|S|而G可视为向C中添加边构成，故W(GS)W(CS)所以 W(GS)|S|2.5 Hamilton 2.5 Hamilton 图图28例例 图 G12345786令S=2,6，则W(GS)=3。而|S|=2，即W(GS)|S|故图G不可能是Hamilton图。134578图图 G-S2.5 Hamilton 2.5 Hamilton 图图29例例 Petersen图。|V|=10，对任何SV，都有W(GS)S，但Petersen图不是Hamilton图（留作习题）。Peter

14、son 图存在Hamilton道路。2.5 Hamilton 2.5 Hamilton 图图删除一个或者两个顶点仍然连通，删除三个顶点最多得到两个连通分支，30例例 下图不存在Hamilton圈。给图的相邻顶点标以A，B，则Hamilton圈包含相同个数的A,B.2.5 Hamilton 2.5 Hamilton 图图31定理定理2-9 简单图 G=(V,E)，n=|V|，若对任一对不相邻顶点 u,vV,uv，有deg(u)+deg(v)n1，则G中存在一条Hamilton路。证明证明(梗概)(1)G是连通的；(2)如果v1,v2,vp是一条基本道路，pn,则可以扩展这条道路：(a)v1,vp

15、存在v1,vp之外的邻接点，可以立即扩展；(b)v1,vp仅与v1,vp邻接，则存在包含这些点的圈。由连通性，存在圈外的结点与圈上某结点邻接，所以，这样的圈可以扩展成更长的基本道路，直至p=n.2.5 Hamilton 2.5 Hamilton 道路道路32推论推论 上述有 deg(u)+deg(v)n 时，G为Hamilton图。证明证明 假设 v1,v2,vn 是Hamilton路，如果v1与 vn 不邻接，设v1的邻接点集是vi1,vi2,vik,则vn必与 vi1-1,vi2-1,vik-1之一邻接，否则deg(vn)=n-1-k,deg(v1)=k,deg(v1)+deg(vn)=n

16、-1。矛盾！2.5 Hamilton 2.5 Hamilton 道路道路33 定理及其推论 给出了Hamilton图成立的充分条件，可用于对Hamilton图的肯定性判定。Hamilton图成立的充要条件尚未得到解决，是图论求解的课题之一。2.5 Hamilton 2.5 Hamilton 图图34旅行商问题旅行商问题 已知n个城市，任两个城市之间都有无向路相通，求一条经过所有城市一次且仅仅一次，并且总路程最短的回路。在一个边带正权的n阶无向完全图中，存在不同的Hamilton回路。旅行商问题在其中寻找一条最短的Hamilton回路。精确算法：分支与界法近似算法：最近邻法；最近插入法；2.6 2.6 旅行商问题旅行商问题35最近邻法最近邻法 设城市之间道路长度符合三角不等式。算法算法 从v1出发,找到其最近邻城市vi2,再从vi2出发vin,将vin与v1连接得到H-回路。2.6 2.6 旅行商问题旅行商问题123456123456508691978350966558798696886754916588787097586778668379547066vvvvvvvvvvvv例例结果是：