2 路与回路(精品).ppt

《2 路与回路(精品).ppt》由会员分享，可在线阅读，更多相关《2 路与回路(精品).ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.路与回路 在实际应用中在实际应用中,比如在市内乘出租车去参观一个博览会比如在市内乘出租车去参观一个博览会,一定要司机选一条最短的路一定要司机选一条最短的路.到博览会后到博览会后,最好选一条这最好选一条这样到路径样到路径,使得每个展台都参观一次后使得每个展台都参观一次后,再回到原来存包再回到原来存包处处.这就是路与回路的问题这就是路与回路的问题.一一.路的概念路的概念 1.路的定义路的定义:给定图给定图G=设设v0,v1,v2,vnV,e1,e2,enE 其中其中ei是关联是关联vi-1,vi的边的边,则称结点和边的交叉序列则称结点和边的交叉序列v0 e1v1 e2v2envn是连接是连接v

2、0到到vn的路的路.v0是此路的起点是此路的起点,vn是是此路的终点此路的终点.路中含有的边数路中含有的边数 n称之为路的长度称之为路的长度.例如上图中例如上图中:v0 e2v3 e6v2是一条长度为是一条长度为2的路的路.v3 v2v1 v0e1e2e3e4e5e6如果图是个如果图是个简单图简单图,则路可以只用结点序列表示则路可以只用结点序列表示.如右图中如右图中,路路:abcad如果如果图是个图是个有向图有向图,则路可以则路可以只用边序列表示只用边序列表示.如有向图中如有向图中 e1 e5e2e3 e6 是一条路是一条路.2.回路回路:如果一条路的起点和终点是一个结点如果一条路的起点和终点

3、是一个结点,则称此路则称此路是是一个回路一个回路.如右图中的如右图中的 L1=v0 e1v1 e5v3 e6v2e4v0 L2=v0 e1v1 e5v3e2v03.迹与闭迹迹与闭迹 如果一条路中如果一条路中,所有所有边都不同边都不同,则称此路为则称此路为迹迹.如果一条如果一条回路回路中中,所有所有边都不同边都不同,则称此回路为则称此回路为闭迹闭迹.v3 v2v1 v0e1e2e3e4e5e6 cb a d v3 v2v1 v0e1e2e3e4e5e64.通路与圈通路与圈 如果一条路中如果一条路中,所有所有结点都不同结点都不同,则称此路为则称此路为通路通路.如果一条如果一条回路回路中中,除起点和

4、终点外除起点和终点外,其余其余结点都不同结点都不同,则则称称此回路为此回路为圈圈.例如右图中例如右图中:L1=v0 e1v1 e5v3 e6v2e4v0 L2=v0 e1v1 e5v3e2v0L3=v0 e1v1 e5v3 e2v0 e3v3 e6v2e4v0 L1和和L2是闭迹是闭迹,也是圈也是圈.L3是闭迹是闭迹,而不是圈而不是圈.v3 v2v1 v0e1e2e3e4e5e6定理定理8-2.1 在一个有在一个有n个结点的图中个结点的图中,如果从结点如果从结点vi到到vj存在存在一条路一条路,则从则从vi到到vj必存在一条长度不多于必存在一条长度不多于n-1的路的路.*证明证明:设设vi到到

5、vj存在一条路存在一条路:vivi+1vi+2,vj,设此路的长度为设此路的长度为k.假设假设kn-1,则此路中有则此路中有 k+1个结点个结点,k+1n,而而G中只有中只有n个结点个结点,所以此路中必有两个结点相同所以此路中必有两个结点相同,假设假设vs=vt,(ts)于是此路为于是此路为:从图看出从图看出,此路中有一个从此路中有一个从vs到到vt的回路的回路,此回路中此回路中,有有t-s条条边边(t-s1),如果删去这个回路如果删去这个回路,就得到一条就得到一条vi到到vj更短的路更短的路.如果新的路长度还大于如果新的路长度还大于n-1,说明此路中还有回路说明此路中还有回路,再删去再删去回

6、路回路,如此进行下去如此进行下去.最后必可找到长度小于最后必可找到长度小于n-1的路的路.vs-1 vi+1 vt+1 vs=vt vs+1vi vt-1 vj vj-1.应用应用:摆渡人摆渡人Ferryman,狼狼Wolf,羊羊Sheep,干草干草Hay过河问过河问题题.如何摆渡使得它们不能互相伤害如何摆渡使得它们不能互相伤害.实际上实际上,这是个在图上这是个在图上找一条路的问题找一条路的问题.FWSH_ WHFSFS WHFSF WSFH HSFWFHFWFS WFS H HFS WFS FS HW SHFWFWFHF -HWFSFS二二.无向图的连通性无向图的连通性1.两个结点是连通的两

7、个结点是连通的:在无向图中在无向图中,结点结点u和和v之间如果存之间如果存在在一条路一条路,则称则称u与与v是连通的是连通的.我们规定我们规定:对任何结点对任何结点u,u与与u是连通的是连通的.2.结点之间的连通关系是个等价关系结点之间的连通关系是个等价关系.令令G=是无向图是无向图,R是是V上连通关系上连通关系,即即 R=|u和和v是连通的是连通的 显然显然R具有自反、对称和传递性具有自反、对称和传递性.于是可以求商集于是可以求商集V/R.例例1.给定图给定图G1如右上图所示如右上图所示:V/R=a,b,g,c,d,e,f,h例例2.给定图给定图G2如右下图所示如右下图所示:V/R=1,3,

8、5,2,4,6 gh a b ef c d 26 4 51 33.连通分支连通分支:令令G=是无向图是无向图,R是是V上连通关系上连通关系,设设R对对V的商集中有等价类的商集中有等价类V1,V2,V3,Vn,这这n个等价类构个等价类构成成的的n个子图分别记作个子图分别记作G(V1),G(V2),G(V3),G(Vn),并称并称它它们为们为G的连通分支的连通分支.并用并用W(G)表示表示G中连通分支数中连通分支数.下边例中下边例中 W(G1)=3 W(G2)=2 W(G3)=1 4.连通图连通图:如果一个图如果一个图G只有一个连通分支只有一个连通分支(W(G)=1),则称则称G是连通图是连通图.

9、W(G3)=1,G3是连通图是连通图 gh a b ef c d 26 4 51 3G1G2 G3定理定理8-2.2:图图G=是连通的是连通的,当且仅当当且仅当 对对V的任何分的任何分成成V1、V2的划分的划分,恒存在一条边恒存在一条边,使得它的两个端点分别使得它的两个端点分别属于属于V1和和V2.*证明证明:必要性必要性.已知已知G是连通的是连通的.令令V1,V2是是V的一个划的一个划分分.任取任取v1V1,v2V2,由于由于G是连通的是连通的,必存在一条路必存在一条路 v1.v2,在此路上必存在结点在此路上必存在结点u和和v,使得使得uV1,vV2,且且(u,v)是此路中是此路中的一条边的

10、一条边.充分性充分性:已知对已知对V的任何分成的任何分成V1、V2的划分的划分,恒存在一条边恒存在一条边,(反证法反证法)假设假设G不是连通的不是连通的.则则G至少有两个连通分支至少有两个连通分支G1、G2,令令V1=V(G1)V2=V-V(G1),根据连通分支定义知根据连通分支定义知,不不存存在端点分别属于在端点分别属于V1和和V2的边的边,与已知矛盾与已知矛盾.所以所以G是连通是连通的的.V1V2u vv1 v2.三三.割集割集(Cut Set)割集在图论中是个重要概念割集在图论中是个重要概念,在图论的理论和应用中在图论的理论和应用中,都具有重要地位都具有重要地位.比如有交通图比如有交通图

11、:结点结点u,边边e就是就是至关重要的至关重要的.割集就是使得原来连通的图割集就是使得原来连通的图,变成不连通变成不连通,需要删去的需要删去的结点集合或边的集合结点集合或边的集合.1.点割集与割点点割集与割点:令令G=是连通无向图是连通无向图,结点集合结点集合V1,V1 V,如果删去如果删去V1中所有结点后中所有结点后,G就变得不连通了就变得不连通了,而删而删去去V1的任何真子集中的所有结点的任何真子集中的所有结点,得到的子图仍然连通得到的子图仍然连通.则则称称V1是是G的一个点割集的一个点割集.如果点割集如果点割集V1中只有一个结点中只有一个结点,则称此结点为割点则称此结点为割点.u e上图

12、中上图中:b,f,b,g,f,k,k,g以及以及a,d,i,l是点是点割集割集.不存在割点不存在割点.2.点连通度点连通度:若若G不是完全图不是完全图,定义定义:k(G)=min|V1|V1是是G的点割集的点割集 为为G的点连通度的点连通度.点连通度点连通度k(G)是表示使是表示使G不连通不连通,至少要删去的结点数至少要删去的结点数.上例中上例中 k(G)=2 具有割点图的点连通度具有割点图的点连通度 k(G)=1 g c b e g ca i ej d h l k g ca b i ej f d h l kj f h k u 定理定理8-2.3:一个连通图中结点一个连通图中结点v是割点的充分

13、且必要条件是割点的充分且必要条件是存在两个结点是存在两个结点u和和w,使得从使得从u到到w的任何路都通过的任何路都通过 v.证明证明:略略上边是通过删去结点的办法使连通图变得不连通的上边是通过删去结点的办法使连通图变得不连通的.也可以通过删去边的办法使连通图变得不连通也可以通过删去边的办法使连通图变得不连通.3.边割集与割边边割集与割边(桥桥)令令G=是连通无向图是连通无向图,边的集合边的集合E1,E1 E,如果删去如果删去E1中所有边后中所有边后,G就变得不连通了就变得不连通了,而删去而删去E1的任何真子集的任何真子集中的所有边中的所有边,得到的子图仍然连通得到的子图仍然连通.则称则称E1是

14、是G的一个边割的一个边割集集.如果边割集如果边割集E1中只有一条边中只有一条边,则称此边为割边则称此边为割边,也称也称之之 为桥为桥.右图中右图中,e就是桥就是桥.e4.边连通度边连通度:若若G不是平凡图不是平凡图,定义定义:(G)=min|E1|E1是是G的边割集的边割集为图为图G的边连通度的边连通度.边连通度边连通度(G)是表示使是表示使G不连通不连通,至少要删去的边数至少要删去的边数.显然显然,如果如果G不是连通图不是连通图,则则 k(G)=(G)=0定理定理8-2.4 G是无向图是无向图,则则 k(G)(G)(G)证明证明:当当G是不连通时是不连通时,显然有显然有k(G)=(G)=0(

15、G)成立成立.当当G是连通时是连通时:1)先证先证(G)(G)2)再证再证k(G)(G)具体证明过程留作作业。具体证明过程留作作业。四四.有向图的连通性有向图的连通性 1.结点间的可达性结点间的可达性:G=是有向图是有向图,u,vV,如果从如果从 u到到v有一条路有一条路,则称从则称从u到到v可达可达.右图中右图中:a可达可达b和和d,但是但是a不可达不可达c.显然结点间的可达关系显然结点间的可达关系,具有自反性和传递性具有自反性和传递性.2.结点结点u到到v的距离的距离:如果如果u可达可达v,可能从可能从u到到v有多条路有多条路,其中最短的路的长度其中最短的路的长度,称之为从称之为从u到到v

16、的距离的距离.记作记作d.上例中上例中 d=1 d=2 d=0 d=3.可达性的性质可达性的性质:1).d0 2)d=0 3)d+dd (如上图的如上图的c,a,b)4)如果从如果从u到到v不可达不可达,则则d=(如如b,c)(如如a,d)5)如从如从u可达可达v,从从v也可达也可达u,但但d不一定等于不一定等于d dc a b4.图的直径图的直径:G是个有向图是个有向图,定义定义 为图为图G的直径的直径.上图中上图中,图的直径图的直径D=(因为因为d=)5.强连通强连通、单侧连通和弱连通单侧连通和弱连通 在简单有向图在简单有向图G中中,如果任何两个结点间相互可达如果任何两个结点间相互可达,则

17、称则称G是是强连通强连通.如果任何一对结点间如果任何一对结点间,至少有一个结点到另至少有一个结点到另一个结点可达一个结点可达,则称则称G是是单侧连通单侧连通.如果将如果将G看成无向图看成无向图后后(即把有向边看成无向边即把有向边看成无向边)是连通的是连通的,则称则称G是是弱连通弱连通.(a)有回路有回路adbca,强连通强连通.(b)a到到d,d到到a,都不可达都不可达 是弱连通是弱连通.(c)单侧连通单侧连通.dc a bD=maxd u,vV dc a b dc a b dc a b(a)(b)(c)定理定理8-2.5:一个有向图一个有向图G是强连通的是强连通的,当且仅当当且仅当G中有一个

18、中有一个回路回路,此回路至少包含每个结点一次此回路至少包含每个结点一次.证明证明:充分性充分性:显然成立显然成立.因为如果因为如果G中有一个回路中有一个回路,它至它至少少包含每个结点一次包含每个结点一次,就使得任何两个结点间相互可达就使得任何两个结点间相互可达,所所以以G是强连通的是强连通的.必要性必要性:如果如果G是强连通的是强连通的,则任何两个结点间相互可达则任何两个结点间相互可达.所以可以构造一个回路经过所有结点所以可以构造一个回路经过所有结点.否则必有一个回路否则必有一个回路不包含某个结点不包含某个结点v,所以所以v与回路上的各与回路上的各结点都不相互可结点都不相互可达达.这与这与G是

19、强分图矛盾是强分图矛盾.所以所以G必有回路至少包含每个结必有回路至少包含每个结点一次点一次.所以所以可以应用此定理判断可以应用此定理判断G是否为强连通是否为强连通,就是看它是否就是看它是否有包含每个结点的回路有包含每个结点的回路.6*.强分图强分图、单侧分图和弱分图单侧分图和弱分图在简单有向图中在简单有向图中,具有强连通的最大子图具有强连通的最大子图,称为称为强分图强分图.具具有单侧连通的最大子图有单侧连通的最大子图,称为称为单侧分图单侧分图.具有弱连通的最具有弱连通的最大子图大子图,称为称为弱分图弱分图.这些这些分图用结点的集合表示分图用结点的集合表示.例如例如,给定有向图给定有向图G,如图

20、所示如图所示:求它的强分图求它的强分图、单侧分图和单侧分图和弱分图弱分图.解解:强分图强分图:由由a,g,hbc def导出的子图导出的子图.单侧分图单侧分图:由由a,g,h,b,f,d,eb,c,f,d,e导出的子图导出的子图.弱分图弱分图:G本身是弱分图本身是弱分图.在有向图中在有向图中,每个结点必位于一个且只位于一个强分图中每个结点必位于一个且只位于一个强分图中 ef c d gh a b定理定理8-2.6 在有向图中在有向图中,每个结点必位于一个且只位于一个每个结点必位于一个且只位于一个强分图中强分图中.证明证明:令令G=是有向图是有向图,任取结点任取结点vV,令令S是所有与是所有与v

21、 相互可达的结点集合相互可达的结点集合,当然当然vS S,而而S是一个强分是一个强分图图,所以所以v必位于一个强分图中必位于一个强分图中.如果如果v位于两个不同的强分图位于两个不同的强分图S1、S2中中,于是于是 v与与S1中每中每个结点相互可达个结点相互可达,v也与也与 S2中每个结点相互可达中每个结点相互可达,所以所以S1中中 每个结点都与每个结点都与S2中每个结点通过中每个结点通过v相互可达相互可达,这说明这说明S1与与S2是一个强分图是一个强分图,与已知与已知S1、S2是两个不同的强分图矛盾是两个不同的强分图矛盾.所以每个结点必位于一个且只位于一个强分图中所以每个结点必位于一个且只位于一个强分图中.在给定的简单有向图中找强分图在给定的简单有向图中找强分图-回路中的结点构成回路中的结点构成一个强分图一个强分图,不在回路中的结点不在回路中的结点,自己构成一个强分图自己构成一个强分图.作业作业 P175(21)