道路与回路课件.ppt
《道路与回路课件.ppt》由会员分享,可在线阅读,更多相关《道路与回路课件.ppt(62页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、道路与回路第1页,此课件共62页哦2.1 2.1 道路与回路道路与回路第2页,此课件共62页哦有向道路有向道路 有向图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 道路与回路道路与回路第3页,此课件共62页哦简单道路简单道路 若对任意的ij有ai aj,称之为简单有向道路简单有向道路(simple path
2、,没有重复边的路径)回路回路 若 v0=vn,称之为封闭的封闭的。简单封闭有向道路(闭迹)称为有向简单回路有向简单回路。初级道路初级道路若对任意的ij有 vi vj,称之为初级道路初级道路/基本道基本道路路/路径路径(elementry or primary)。圈圈若对任意的ij有vi vj 而例外地v0=vn,称之为初级回路初级回路/圈圈(cycles)。无向图具有完全类似的定义。2.1 2.1 简单道路与圈简单道路与圈第4页,此课件共62页哦2.1 2.1 道路与回路道路与回路练习:找出上图结点1至结点9的简单道路和初级道路,1到1的有向回路和圈。第5页,此课件共62页哦容易证明:定理定理
3、2-1(1)基本道路是简单道路;(2)如果存在u到v的道路,则存在u到v 的基本道路;(3)n阶图的基本道路长度不超过n-1;(4)n阶图的圈的长度不超过n.2.1 基本道路基本道路第6页,此课件共62页哦定理定理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的度
4、是偶数,存在与vn邻接另一个顶点u,从而得到一条更长的简单路径。矛盾!2.1 2.1 道路与回路的关系道路与回路的关系第7页,此课件共62页哦可达性可达性 对于有向图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 连通性连通性第8页,此课件共62页哦强连通性强连通性对于有向图G=(
5、V,A),如果任意两点之间相互可达,则称G为强连通的.弱弱 连通性连通性对于有向图G=(V,A),若不考虑弧的方向后得到的无向图是连通的,则称有向图G是弱连通的。2.2 2.2 有向图的连通性有向图的连通性第9页,此课件共62页哦定理定理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。算法复杂度
6、 O(n4)2.2 2.2 道路矩阵道路矩阵第13页,此课件共62页哦道路矩阵可以通过二值矩阵的逻辑运算求得。定义定义 二值元素的逻辑运算:0 0=0,0 1=1 0=1,1 1=1 0 0=0,0 1=1 0=0,1 1=1定义定义 二值矩阵的逻辑运算。设有矩阵A=(aij),B=(bij),矩阵元素值域为 0,1,定义运算:2.2 2.2 道路矩阵的计算道路矩阵的计算第14页,此课件共62页哦定义定义 A(k)=A(k1)A (k2),A(1)=A注意 A(k)与Ak 的区别定理定理2-12 设 Ann 是图G的邻接矩阵,若从vi 到vj存在长度为 l 的路,则 A(l)ij=1,否则 A
7、(l)ij=0。证明证明 对 l 作归纳;或直接引用定理2-11。2.2 2.2 道路矩阵的计算道路矩阵的计算第15页,此课件共62页哦Warshall算法算法 设 A nn是图G的邻接矩阵,求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的路径。第16页,此课件共62页哦例例 图G的
8、邻接矩阵A如右,使用Warshall算法求G的道路矩阵P。解解 P A2.2 2.2 道路矩阵及道路矩阵及WarshallWarshall算法算法第17页,此课件共62页哦(1)i=1 j=1,2,3,4 增量方向i=1 矩阵元素处理次序:p11,p12,p13,p14,p21,p22,p31,p41,p44,2.2 2.2 道路矩阵及道路矩阵及WarshallWarshall算法算法第18页,此课件共62页哦 如:p11=p11(p1i pi1)=p11(p11 p11)=0 p12=p12(p1i pi2)=p12(p11 p12)=1 p13=p13(p1i pi3)=p13(p11 p
9、13)=0 结果为2.2 2.2 道路矩阵及道路矩阵及WarshallWarshall算法算法第19页,此课件共62页哦2.3 图上的搜索图上的搜索可以使用搜索的方法判断从一个顶点u到另一个顶点v是否有路径。深度优先DFS从顶点u出发检查其后继u1是否,如果不是,则从u1开始进行深度优先搜索;如果没有后继,则回溯,直至找到或者没有可搜索的顶点。第20页,此课件共62页哦2.3 图上的搜索图上的搜索广度优先BFS从u出发,首先检查其所有的直接后继是否等于;然后依次检查这些后继的直接后继,直到找到或者没有可遍历顶点。练习:编写一个使用深度优先或者广度优先搜索判定两个点之间是否有道路的程序。第21页
10、,此课件共62页哦Euler回路回路 若连通图 G=(V,E)中存在一条简单回路(无重复边)经过G的所有边,则称该回路为G中的一条Euler回路。存在Euler回路的图称为Euler图。定理定理2-6-1 设有连通图G=(V,E),则下述命题等价:(1)G是一个Euler图;(2)G的每一个顶点的度是偶数;证明证明1:见课本。见课本。证明证明2:只证充分性。对边数只证充分性。对边数|E|进行归纳。只有一个边的连通图是进行归纳。只有一个边的连通图是Euler图。假定对于图。假定对于|E|2(否则,所有结点为(否则,所有结点为2度的图是度的图是Euler图,),图,),v,w是是u的两个邻接点,则
11、的两个邻接点,则G=G-,+是具有是具有k条边,所有结点度数是偶数。如果条边,所有结点度数是偶数。如果G是连通图,由归纳假设,此图存在是连通图,由归纳假设,此图存在Euler回路,那么将此回路的边回路,那么将此回路的边用用 和和替换后得到图替换后得到图G 的的Euler回路。如果回路。如果G不连通,至多有两个连通分支构成,由归纳假设,两个连通分支不连通,至多有两个连通分支构成,由归纳假设,两个连通分支有有Euler回路,不难由这两个回路,不难由这两个Euler回路构造原图的回路构造原图的Euler回路。回路。2.4 Euler 2.4 Euler 回路回路第22页,此课件共62页哦注意定理中对
12、图的连通性的假定;Euler回路经过图的所有边一次且仅仅一次。定理对非简单图也成立;定理的证明过程给出了为一个Euler图构造Euler回路的构造算法。定理定理2-7 设连通图G=(V,E)中恰有2个顶点度为奇数,则G存在Euler道路。证明证明 连接两个奇度数结点形成Euler图,再删除该边即可。2.4 Euler 2.4 Euler 回路回路第23页,此课件共62页哦有向图的有向图的Euler回路回路 若有向连通图 G=(V,A)中存在一条简单有向回路经过G的所有弧,则称该回路为G中的一条Euler回路,称该图为Euler有向图。定理定理2-6-2 设连通有向图G=(V,A),则下述命题等
13、价:(1)G是一个Euler有向图;(2)G的每一个顶点的入度等于出度;证明证明(略)2.4 Euler 2.4 Euler 回路回路第24页,此课件共62页哦ExercisesProve that if every vertex in a connected graph G has even degree,then the graph G is an Euler graph.(Prove it by induction on the number of edges.)Prove that if every vertex of a graph has even degree,and degre
14、e(v)=2 for some vertex v,then there exists a simple closed path passing over v.第25页,此课件共62页哦Hamilton路路 若连通图 G=(V,E)中存在一条初级道路(无重复顶点)经过G中每个顶点一次,则称该道路为G中的一条Hamilton路。存在Hamilton回路(圈)的图称 为Hamilton图。Hamilton路经过图的所有顶点一次且仅仅一次。存在Hamilton回路的例子:Cn,Kn,正十二面体存在Hamilton道路的例子不存在Hamilton道路的例子Hamilton path in Wikiped
15、ia2.5 Hamilton 2.5 Hamilton 道路道路第26页,此课件共62页哦2.5 Hamilton 2.5 Hamilton 道路道路第27页,此课件共62页哦2.5 Hamilton 2.5 Hamilton 图图构造Hamilton圈的简单规则:Halmilton圈含n条边;Halmilton圈正好包含每个结点的两条关联边,其他边可以删除;左图如有H圈,则必包含三个二度结点的邻接边,从而中心结点至少有三个邻接边包含在其中,故不可能有圈。第28页,此课件共62页哦定理定理2-8 若G=(V,E)是一个Hamilton图,SV且S,则 G的子图GS的连通分支数 W(GS)|S|
16、证明证明 记G中H-回路为C,C中包含了G中所有顶点。考察CS:每从C中去除属于S的一个顶点,连通分支数至多增加1(第一次以及当该顶点处于边缘时操作不会增加连通分支数),故 W(CS)|S|而G可视为向C中添加边构成,故W(GS)W(CS)所以 W(GS)|S|2.5 Hamilton 2.5 Hamilton 图图引入记号:G=(V,E),SV。从G中去除S中的顶点及其关联边得到的G的子图记为GS。第29页,此课件共62页哦例例 图 G12345786令S=2,6,则W(GS)=3。而|S|=2,即W(GS)|S|故图G不可能是Hamilton图。134578图图 G-S2.5 Hamilt
17、on 2.5 Hamilton 图图第30页,此课件共62页哦例例 Petersen图。|V|=10,对任何SV,都有W(GS)S,但Petersen图不是Hamilton图(留作习题)。Peterson 图存在Hamilton道路。2.5 Hamilton 2.5 Hamilton 图图删除一个或者两个顶点仍然连通,删除三个顶点最多得到两个连通分支,第31页,此课件共62页哦例例 下图不存在Hamilton圈。给图的相邻顶点标以A,B,则Hamilton圈包含相同个数的A,B.2.5 Hamilton 2.5 Hamilton 图图第32页,此课件共62页哦定理定理2-9 简单图 G=(V,
18、E),n=|V|,若对任一对不相邻顶点 u,vV,uv,有deg(u)+deg(v)n1,则G中存在一条Hamilton路。证明证明(梗概)(1)G是连通的;(2)如果v1,v2,vp是一条基本道路,pn,则可以扩展这条道路:(a)v1,vp存在v1,vp之外的邻接点,可以立即扩展;(b)v1,vp仅与v1,vp邻接,则存在包含这些点的圈。由连通性,存在圈外的结点与圈上某结点邻接,所以,这样的圈可以扩展成更长的基本道路,直至p=n.2.5 Hamilton 2.5 Hamilton 道路道路第33页,此课件共62页哦推论推论 上述有 deg(u)+deg(v)n 时,G为Hamilton图。证
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 道路 回路 课件
限制150内