【教学课件】第五章图论(第二部分).ppt

第 五 章 图 论(第二部分)1.通路通路2.图的图的连通性连通性11.1.通路通路定义定义通路通路 pseudo pathl 设设G(V，E)是图，是图，v0，vn是是G中两点。若中两点。若G中结点序列中结点序列v0v1 vn满足：满足：vi与与vi+1相邻相邻(0 in),则该序列称为从则该序列称为从v0到到vn的的通路通路。l 两个端点相同的通路称为两个端点相同的通路称为回路（环或圈）回路（环或圈）。l 通路中包含的边数称为该通路中包含的边数称为该通路的长度通路的长度。注意注意：(1)(1)通路中通路中允许有重复的结点和边允许有重复的结点和边。2ABCDE通路举例通路举例通路：通路：ADEBDEAADEBDEA回路：回路：ACDBCEAACDBCEA回路：回路：ABCDEAABCDEA3ABCDE简单通路：简单通路：ADEBDADEBD简单回路：简单回路：ACDBCEAACDBCEA 定义定义简单通简单通(回回)路路 各边均不相同的通路称为各边均不相同的通路称为简单通路简单通路。各边均不相同的回路称为各边均不相同的回路称为简单回路简单回路 简单通简单通(回回)路路4基本通基本通(回回)路路l定义定义基本通基本通(回回)路路 结点各不相同结点各不相同的通路称为的通路称为基本通路基本通路。中间结点各不相同中间结点各不相同的回路称为的回路称为基本回路基本回路。ABCDE基本通路：基本通路：ACEBDACEBD基本回路：基本回路：ABCDEAABCDEA5有向通有向通(回回)路路l定义定义有向通有向通(回回)路路 若通路若通路v0v1 vn各边是各边是有向边有向边，且，且vi-1和和vi分别是有向边的分别是有向边的始点始点与与终点终点，则称该通路为，则称该通路为有向通有向通(回回)路路。6通路定理通路定理l定理定理通路定理通路定理 在在n阶图阶图G中，如果有顶点中，如果有顶点u到到v（u v）的）的通路通路，那么，那么u到到v必有一条必有一条长度小长度小于等于于等于n 1的的基本通路。基本通路。7通路定理证明通路定理证明l定理：在有定理：在有n个顶点的图个顶点的图G中，如果有顶点中，如果有顶点u到到v的通路，必有长度的通路，必有长度不大于不大于n-1的基本通路。的基本通路。证明：证明：(1)先证明先证明u和和v之间存在基本通路之间存在基本通路 若若uv之之间间的的通通路路P中中有有相相同同的的顶顶点点，则则从从P中中删删除除相相同同顶顶点点之之间间路路径径，直直到到P中中没没有有相相同同顶顶点点，这这样样得得到到的的路路径径为为u和和v之之间间的的基基本通路。本通路。(2)再证基本通路长度不大于再证基本通路长度不大于n-1 （反证法）设（反证法）设u和和v之间的基本通路的长度之间的基本通路的长度。一条边关联两个顶点，一条边关联两个顶点，长度长度的基本通路上至少有个顶点。的基本通路上至少有个顶点。至至少少有有两两个个相相同同顶顶点点在在u和和v之之间间的的基基本本通通路路上上，这这与与基基本本通通路路的性质的性质“任意两个顶点不同任意两个顶点不同”相矛盾。相矛盾。基本通路的长度基本通路的长度=n-18路径：路径：回路定理回路定理l定理定理回路定理回路定理 在有在有n个顶点的图个顶点的图G中，如果有顶点中，如果有顶点v到自身到自身的的通路通路，那么必定有一条从，那么必定有一条从v到到v的长度不的长度不大于大于n的的基本回路基本回路。9连通性定义连通性定义l定义定义两结点连通两结点连通(可达可达)若若u与与v之间有通路相连之间有通路相连，则称，则称u与与v连通（可达）。连通（可达）。规定：规定：任意顶点与自身连通。任意顶点与自身连通。l定义定义连通无向图连通无向图l任意两个顶点都连通任意两个顶点都连通的无向图的无向图abcdef10有向图的连通性有向图的连通性l强连通的有向图强连通的有向图l任意两个顶点都是任意两个顶点都是互相互相连通连通的。的。l单向连通的有向图单向连通的有向图l任意两个顶点，至少从一个顶点到另一个是任意两个顶点，至少从一个顶点到另一个是连通连通的的l弱连通的有向图弱连通的有向图l底图底图连通连通的的bca11强连通图性质（补充）强连通图性质（补充）定理定理：一个有向图：一个有向图G是强连通的是强连通的当且仅当当且仅当中有一条包含所中有一条包含所有顶点至少一次的有顶点至少一次的回路回路。证明：证明：中有一条包含所有顶点的回路，显然强连通。中有一条包含所有顶点的回路，显然强连通。/*连通连通图的定义图的定义*/：如果如果 G强连通，强连通，G中的顶点为中的顶点为v1，v2，.vn,设设v1到到v2路路径为径为P1，v2到到v3的路径为的路径为P2，vn到到v1 的路为的路为Pn，将，将P1，P2，.Pn连起来，此路是一条包含连起来，此路是一条包含G中所有顶点的中所有顶点的回路。回路。12有向图连通性举例有向图连通性举例l判断下面给出的图是强连通图、单向连通图还是弱连通图。ABCDEFABCDEFABCDEFABDCE强连通图强连通图弱连通图弱连通图强连通图强连通图单向连通图单向连通图13无向图的连通分支无向图的连通分支l定义定义连通分支连通分支（connected component）l设图设图G 是无向图是无向图G的子图的，如果：的子图的，如果：(1)G 是是连通连通的，的，(2)G 不是不是任何其它连通子图的真子图任何其它连通子图的真子图（极大性）（极大性）则称则称G 是是G的的连通分支连通分支。G 定义定义 连通图：连通图：只有只有一个一个连通分连通分支的图。支的图。14无向图连通分支举例例例 请指出下图请指出下图G的连通分支数。的连通分支数。v3v4v5v6v7v1v2G15有向图的连通分支有向图的连通分支l定义定义强（单向、弱）连通分支强（单向、弱）连通分支 设图设图G 是有向图是有向图G的子图的，如果：的子图的，如果：(1)G 是是强连通（单向连通、弱连通）强连通（单向连通、弱连通）的，的，(2)G 不是不是任何其它任何其它强连通（单向连通、弱连通）强连通（单向连通、弱连通）子图的真子图子图的真子图（极大性）（极大性）则称则称G 是是G的的强连通分支强连通分支/强分支（单向连通分支强分支（单向连通分支/单向分支、弱连通分支单向分支、弱连通分支/弱分支）弱分支）。16有向图的连通分支举例有向图的连通分支举例强分支强分支:、单向分支单向分支:、，弱分支弱分支:、v8Gv2v1v6v3v5v4e2e1e7e6e5e3e4v7e8例例 请指出下图请指出下图G的所有强分支、单向分支和弱分支。的所有强分支、单向分支和弱分支。17有向图连通分支举例有向图连通分支举例l请给出下图的所有强分支、单向分支和弱分支l强分支：GA、GE、GF、GB、GC、GD、GP,Q,S,Tl单向分支：GA,E,F、GB,C,D、GA,B,C,D、GA,C,D,E、GP,Q,S,Tl弱分支：GA,B,C,D,E,F，GP,Q,S,TABCDEFPQST18 若若若若n n n n阶图阶图阶图阶图G G G G的邻接矩阵为的邻接矩阵为的邻接矩阵为的邻接矩阵为A=(A=(A=(A=(a a a aijijijij)nnnnnnnn，V(G)=vV(G)=vV(G)=vV(G)=v1 1 1 1,v,v,v,v2 2 2 2,v v v vn n n n,则：则：则：则：（1 1 1 1）若）若）若）若ijijijij 1 1 1 1，表明，表明，表明，表明v v v vi i i i到到到到v v v vj j j j有一条边，即有一条边，即有一条边，即有一条边，即v v v vi i i i到到到到v v v vj j j j连通连通连通连通；（2 2 2 2）若）若）若）若ijijijij，表明，表明，表明，表明v v v vi i i i到到到到v v v vj j j j没有长度为没有长度为没有长度为没有长度为1 1 1 1的通路。的通路。的通路。的通路。ijij的的值值表示表示G G中中i i到到j j长度为的长度为的通路条数。通路条数。图的连通性：图的连通性：连通性质讨论连通性质讨论19 定理定理 若若G G的的邻邻接接矩矩阵阵为为A A，则则矩矩阵阵m m的的元元素素b bijij表表示示v vi i到到v vj j长度为长度为的的通路条数通路条数。连通性质讨论连通性质讨论(续续)20可达矩阵l定义定义可达矩阵可达矩阵 若阶有向图的邻接矩阵为若阶有向图的邻接矩阵为A，令，令B=A+A2+An-1+An 将将B中中不为不为0的元素改为的元素改为1，为为0的元素不变的元素不变，修改后所得到的矩阵修改后所得到的矩阵(bij)n n称为称为G的的可达矩阵可达矩阵。图图G从从vi点到点到vj点有通路当且仅当？点有通路当且仅当？bij=121图的连通性与可达矩阵l有向图的连通性（有向图的连通性（n n 1 1）：）：设有向图设有向图G G的可达矩阵为的可达矩阵为B B(1)(1)强连通强连通(2)(2)是单向连通的是单向连通的l无向图的连通性（无向图的连通性（n n 1 1）：）：设无向图设无向图G G的可达矩阵为的可达矩阵为B B 连通连通B B中元素全为中元素全为B B中中所有关于主对角线对称所有关于主对角线对称的两个元素中至少一个值为的两个元素中至少一个值为B B中元素全为中元素全为22连通性证明题举例连通性证明题举例1 试证试证：若个顶点的无向图若个顶点的无向图G=(V,E)G=(V,E)连通，则连通，则|E|E|（）（）。证明：证明：(归纳法归纳法)(1)(1)，由，由G G连通可知连通可知:|E|:|E|1=1=,定理成立。定理成立。(2)(2)假设时假设时,结论成立结论成立,即即|E|E|1.1.(3)(3)证法一证法一:当时，由递归假设可知当时，由递归假设可知:|E|:|E|1.1.任选任选G G中一个结点中一个结点v v 若若G-vG-v连通连通,则则|V(G-v)|=k,|V(G-v)|=k,故由递归假设故由递归假设|E(G-v)|E(G-v)|1;1;而由而由v v与与G-vG-v至少有一条边相连可知至少有一条边相连可知:|E|:|E|E(G-v)|+1|E(G-v)|+1;若若G-vG-v不连通不连通,不妨设不妨设G-vG-v中有中有m m个连通分支个连通分支G G1 1,G,G2 2,G,Gm m,设设|V(G|V(Gi i)|=x)|=xi i;显然显然,对所有对所有i=1,2,3,m,i=1,2,3,m,都有都有:x:xi ik.|V(G)|/2-1，则G是连通图。证明证明：（反证法）假设G不是连通图。则G中至少存在两个连通分支，不妨设G中的两个连通分支分别为G1和G2，且|V(G1)|V(G2)|。则有：|V(G1)|V(G)|/2。而由G是简单图可知：G1中任意顶点v的度数满足：d(v)|V(G1)|-1|V(G)|/2-1 进而，d(v)|V(G)|/2-1，这与前提条件|V(G)|/2-1矛盾。因此，G是连通图。25连通性证明举例连通性证明举例3l设设G是是n阶无向简单图，若阶无向简单图，若G中任意不同的两个顶点的度数中任意不同的两个顶点的度数 之和大于等于之和大于等于n 1，请证明，请证明G是连通图。是连通图。证明：证明：反证法。反证法。假设假设G不连通。不连通。不妨设不妨设G有有k个连通分支个连通分支G1，G2，Gk，n1，n2，nk是各分支的顶点数。则有：是各分支的顶点数。则有：n1+n2+nk=n 任取任取u G1,v G2。由由G是简单图可知：是简单图可知：deg(u)=n1 1 且且 deg(v)=n2 1。因此，因此，deg(u)+deg(v)=n1 1+n2 1 =n 2 这与题设这与题设“任意不同的两个顶点的度数之和大于等于任意不同的两个顶点的度数之和大于等于n 1”矛盾。矛盾。G是连通图是连通图26l 设图设图G是无向简单图。是无向简单图。请证明图请证明图G和补图和补图G中至少有一个连通图中至少有一个连通图。证明：证明：(1)如果如果G是连通图，问题得证。是连通图，问题得证。(2)如果如果G不不是连通图。是连通图。任取任取u,v G，设，设G的连通分支有的连通分支有G1，G2，Gk 如果如果u和和v是属于是属于G中不同的连通分支中不同的连通分支Gi和和Gj，则，则(u,v)G 如果如果u和和v是属于是属于G中相同的连通分支中相同的连通分支Gi，则可在，则可在G的另一个连通分的另一个连通分支中取一个结点支中取一个结点x，则，则(u,x)G,(v,x)G。u和和v之间在之间在G中有通路中有通路uxv相连。相连。由由u和和v的任意性，可知的任意性，可知G是连通的。是连通的。综上所述，综上所述，G和补图和补图G中至少有一个是连通图。中至少有一个是连通图。连通性证明举例连通性证明举例427课堂练习课堂练习l证明：若G是简单图，设为G的顶点的最小度，若k，则G中有长为k的基本通路。28课堂练习解答课堂练习解答l2.证明：证明：（反证法）假设G中不存在长度为k的基本通路。设P=v1v2vm为G中最长基本通路。则mk。假设vm与V(G)-V(P)中的一个结点相连，不妨设为w，则v1v2vmw为比P更长的一条基本通路。这与P是G中最长的基本通路相矛盾。因此，vm结点只能与P上的结点v1,v2,vm-1相连，故d(vm)m-1k-1，进而 d(vm)k-1，这与k矛盾。29