7-2 路与回路.ppt

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

1、路与回路路与回路路与回路路与回路中国海洋大学中国海洋大学计算机系计算机系主要内容主要内容主要内容主要内容n路与回路的基本概念路与回路的基本概念n无向图的连通度无向图的连通度n有向图的连通性有向图的连通性n极大通路法极大通路法n二部图二部图n学习要点与基本要求学习要点与基本要求n实例分析实例分析路与回路路与回路路与回路路与回路定义定义7-2.1 给定图给定图G=，设，设v0,v1,vnV，e1,e2,enE，其中，其中ei是关联于结点是关联于结点vi-1,vi的边，的边，交替序列交替序列v0 e1v1e2 envn称为联结称为联结v0到到vn的的路路。v0是路的是路的起点起点，vn是路的是路的终

2、点终点.边的数目边的数目n称为路的称为路的长度长度.当当v0=vn时，这条路称作时，这条路称作回路回路.若路中所有的边若路中所有的边e1,e2,en均不相同，称作均不相同，称作迹迹.若路中所有的结点若路中所有的结点v0,v1,vn均不相同，则称作均不相同，则称作通通路路.若路中除若路中除v0=vn外，其余结点均不相同的，则称作外，其余结点均不相同的，则称作圈圈.路和回路的简单表示法路和回路的简单表示法路和回路的简单表示法路和回路的简单表示法n只用边的序列表示路只用边的序列表示路(回路回路)，可以表示成，可以表示成e1,e2,en。n在简单图中也可以只用顶点序列表示路在简单图中也可以只用顶点序列

3、表示路(回路回路)。可。可以表示成以表示成v0,v2,vn。n为了写出非标定图中的路为了写出非标定图中的路(回路回路)，可以先将非标定，可以先将非标定图标成标定图，再写出路与回路。图标成标定图，再写出路与回路。n在非简单标定图中，当只用顶点序列表示不出某些在非简单标定图中，当只用顶点序列表示不出某些通路通路(回路回路)时，可在顶点序列中加入一些边时，可在顶点序列中加入一些边(这些这些边是平行边或环边是平行边或环)，可称这种表示法为，可称这种表示法为混合表示法混合表示法.实例实例实例实例1 1例例1 在下图所示的图中分别找出一条路、迹、通路、在下图所示的图中分别找出一条路、迹、通路、回路和圈。回

4、路和圈。路：路：v1e2v3e3 v2e4 v3e3 v2e6 v5e7 v3说明：说明：通路一定是迹，迹一定是路，反之不成立。通路一定是迹，迹一定是路，反之不成立。圈一定是回路，反之不然。圈一定是回路，反之不然。迹：迹：v5e8v4e5v2e6v5e7v3e4v2通路：通路：v4e8v5e6v2e1v1e2v3回路：回路：v2e3v3e4v2e1v1e2v3e4v2圈：圈：v2e1v1e2v3e7v5e6v2路的存在性路的存在性路的存在性路的存在性定理定理7-2.1 在一个具有在一个具有n个结点的图中，如果从结点个结点的图中，如果从结点vj到到结点结点vk存在一条路，则从结点存在一条路，则从

5、结点vj到结点到结点vk必存在一条必存在一条不多于不多于n-1条边的路。条边的路。证明证明 如果从结点如果从结点vj到结点到结点vk存在一条路，设该路上的结存在一条路，设该路上的结点序列是点序列是vj,vi,vk，如果这条路中有，如果这条路中有l 条边，则条边，则序列中必有序列中必有l+1个结点。假设个结点。假设ln-1，则必有结点，则必有结点vs，它在序列中不止出现一次，即必有结点序列它在序列中不止出现一次，即必有结点序列vj,vsvsvk，在路中删掉从，在路中删掉从vs到到vs的这些边，仍是的这些边，仍是vj到到vk的一条路，但这条路比原来的路边数少。如此重复的一条路，但这条路比原来的路边

6、数少。如此重复进行下去，必可得到从进行下去，必可得到从vs到到vs的边数不多于的边数不多于n-1的路。的路。定理定理定理定理7-2.17-2.1的推论的推论的推论的推论推论推论 在在n阶图阶图G中，若从顶点中，若从顶点vi到到vj（vi vj）存在路，）存在路，则从则从vi到到vj存在长度小于等于存在长度小于等于n 1的通路的通路.推论推论 在一个在一个n阶图阶图G中，若存在中，若存在vi到自身的回路，则到自身的回路，则一定存在一定存在vi到自身长度小于等于到自身长度小于等于n的回路的回路.推论推论 在一个在一个n阶图阶图G中，若存在中，若存在vi到自身的回路，则到自身的回路，则一定存在长度小

7、于等于一定存在长度小于等于n的圈的圈.实例实例实例实例2 2例例2 无向完全图无向完全图Kn(n3)中有几种非同构的圈？中有几种非同构的圈？解答解答 长度相同的圈都是同构的，长度相同的圈都是同构的，因而只有长度不同的圈才是非同构的，因而只有长度不同的圈才是非同构的，易知易知Kn(n3)中含长度为中含长度为3，4，n的圈，的圈，所以所以Kn(n3)中有中有n-2种非同构的圈。种非同构的圈。无向图的连通性无向图的连通性无向图的连通性无向图的连通性定义定义7-2.2 在无向图在无向图G中，结点中，结点u和和v之间若存在一条路，之间若存在一条路，则称结点则称结点u和和v是连通的，记为是连通的，记为u

8、v。几点说明：几点说明：1.连通关系连通关系 R=|u,v V且且u v是是V上的上的等价关系等价关系。2.连通分支连通分支:V关于关于R的等价类的导出子图。的等价类的导出子图。称称V/R=V1,V2,Vk,GV1,GV2,GVk为为G的的连通分支，连通分支，连通分支数连通分支数记作记作W(G)=m。定义定义7-2.3 若图若图G只有一个连通分支，则称只有一个连通分支，则称G是连通的是连通的.即连通图即连通图G的连通分支数的连通分支数W(G)=1。实例实例实例实例3 3例例3 下列图哪些是连通图？连通分支数是多少？下列图哪些是连通图？连通分支数是多少？连通图，连通图，W=1非连通图，非连通图，

9、W=3如何定义连通度如何定义连通度如何定义连通度如何定义连通度n问题问题：如何定量地比较无向图的连通性的强与弱？：如何定量地比较无向图的连通性的强与弱？n点连通度点连通度：为了破坏连通性，至少需要删除多少个：为了破坏连通性，至少需要删除多少个顶点？顶点？n边连通度边连通度：为了破坏连通性，至少需要删除多少条：为了破坏连通性，至少需要删除多少条边？边？n“破坏连通性破坏连通性”是指是指“变得更加不连通变得更加不连通”。点割集的定义点割集的定义点割集的定义点割集的定义定定义义7-2.4 设设无无向向图图G=为为连连通通图图,若若有有点点集集V1 V,使使图图G删删除除了了V1的的所所有有结结点点后

10、后，所所得得的的子子图图是是不不连连通通图图，而而删删除除了了V1的的任任意意真真子子集集后后，所所得得到到的的子子图图仍仍是是连连通通图图，则则称称V1是是G的的一一个个点点割割集集。若若某某一一个个结点构成一个点割集，则称该结点为结点构成一个点割集，则称该结点为割点割点。形式化为：形式化为：若若W(G V1)W(G)且且 V V1,W(G V)=W(G),则则称称V1为为G的的点割集点割集.若若v为点割集为点割集,则称则称v为为割点割点.实例实例实例实例4 4例例4 求下图的割点求下图的割点删除结点删除结点s连通图，连通图，W=1非连通图，非连通图，W=2因此因此s是割点。是割点。实例实例

11、实例实例5 5例例5 在下图所示的图中，找出点割集和割点。在下图所示的图中，找出点割集和割点。点割集：点割集：v1,v4,v6，v5，割点：割点：v6，v5v2、v3与与v7不在任何点割集中。不在任何点割集中。无向图的点连通度无向图的点连通度无向图的点连通度无向图的点连通度定义定义 设设G是无向图，是无向图，k(G)=min|V1|V1是是G的点割集的点割集是是G的的点连通度点连通度，也称作连通度。，也称作连通度。几点说明：几点说明：1.连通度连通度k(G)表示为了产生一个不连通图所需要删除表示为了产生一个不连通图所需要删除的点的最少数目。的点的最少数目。2.非连通图的连通度等于非连通图的连通

12、度等于0，存在割点的连通图的连，存在割点的连通图的连通度为通度为1，n阶完全图的连通度为阶完全图的连通度为n-1。3.连通度连通度k(G)表示图表示图G的连通程度，的连通程度，k(G)大表示连通大表示连通性强，即需要删除更多的点才能使图从连通变为非性强，即需要删除更多的点才能使图从连通变为非连通。连通。边割集边割集边割集边割集定义定义7-2.5 设无向图设无向图G=为连通图为连通图,若有边集若有边集E1 E,使图使图G删除了删除了E1的所有结点后，所得的子图的所有结点后，所得的子图是不连通图，而删除了是不连通图，而删除了E1的任意真子集后，所得到的任意真子集后，所得到的子图仍是连通图，则称的子

13、图仍是连通图，则称E1是是G的一个的一个边割集边割集。若。若某一个结点构成一个点割集，则称该结点为某一个结点构成一个点割集，则称该结点为割边割边（或桥）（或桥）。更一般定义为：更一般定义为：若若W(G E1)W(G)且且 E E1,W(G E)=W(G),则则称称E1为为G的的边割集边割集.若若e为点割集为点割集,则称则称e为为割边割边.实例实例实例实例例例 在下图所示的图中，举出边割集和桥的例子。在下图所示的图中，举出边割集和桥的例子。边割集：边割集：e1,e2,e3,e4,e5,e1,e3,e5,e6,e7，e8等等割边：割边：e7，e8边连通度边连通度边连通度边连通度定义定义 设设G是无

14、向图，是无向图，(G)=min|E1|E1是是G的边割集的边割集是是G的边连通度。的边连通度。几点说明：几点说明：1.边连通度边连通度(G)是为了产生一个不连通图所需要删除是为了产生一个不连通图所需要删除的边的最少数目。的边的最少数目。2.非连通图的边连通度等于非连通图的边连通度等于0，存在桥的连通图的边，存在桥的连通图的边连通度为连通度为1，平凡图的边连通度为，平凡图的边连通度为0。3.边边连通度连通度(G)表示图表示图G的边连通程度，的边连通程度，(G)大表示大表示边连通性强，即需要删除更多的边才能使图从连通边连通性强，即需要删除更多的边才能使图从连通变为非连通。变为非连通。点连通度与边连

15、通度的比较点连通度与边连通度的比较点连通度与边连通度的比较点连通度与边连通度的比较定理定理7-2.2 对于任何一个图对于任何一个图G，有，有 k(G)(G)(G)证明证明 若若G不连通，则不连通，则k(G)=(G)=0，故上式成立。，故上式成立。若若G连通，连通，证明证明(G)(G)如果如果G是平凡图，则是平凡图，则(G)=0 (G)若若G是非平凡图，因为每个结点的所有关联边必含一是非平凡图，因为每个结点的所有关联边必含一个边割集，所以个边割集，所以(G)(G)。定理定理定理定理7-2.27-2.2的证明的证明的证明的证明再证再证k(G)(G)(1)设设(G)=1，即，即G有一个割边，那么与割

16、边关联的有一个割边，那么与割边关联的两个结点中至少有一个是割点，所以两个结点中至少有一个是割点，所以k(G)=1。(2)设设(G)1，则必可删去某，则必可删去某(G)条边，使条边，使G不连通，不连通，而删去其中而删去其中(G)-1条边后得到的图条边后得到的图G仍是连通的，仍是连通的，且有一条桥且有一条桥e=(u,v)。对于。对于(G)-1条边中的每一条都条边中的每一条都选取一个不同于选取一个不同于u,v的端点，把这些端点删去则至少的端点，把这些端点删去则至少删去删去(G)-1条边。若这样产生的图是不连通的，则条边。若这样产生的图是不连通的，则k(G)(G)-1 (G).定理定理定理定理7-2.

17、27-2.2的证明的证明的证明的证明若这样产生的图是连通的，则若这样产生的图是连通的，则e仍是桥，此时再删去仍是桥，此时再删去u,v中的任一个，就产生一个不连通图，中的任一个，就产生一个不连通图，故故k(G)(G).由由1)和和2)得得k(G)(G)(G)例如例如 下图下图G。k(G)=2 (G)=3 (G)=4实例实例实例实例6 6求所示各图的点连通度，边连通度求所示各图的点连通度，边连通度K4 4K3 3K2 2K1 1K=1 1=2 2K2 2K0 0K0 0割点的判定割点的判定割点的判定割点的判定定理定理7-2.3 一个连通无向图一个连通无向图G中的结点中的结点v是割点的充分必是割点的

18、充分必要条件是存在两个结点要条件是存在两个结点u和和w，使得结点，使得结点u和和w的每一的每一条路都通过条路都通过v。证明证明 必要性。必要性。若结点若结点v是连通图是连通图G=的一个割点，的一个割点，设删去设删去v得到子图得到子图G，则，则G至少包含两个连通分支。至少包含两个连通分支。设为设为G1=,G2=，任取，任取uV1,wV2，因为因为G是连通的，故在是连通的，故在G中必有一条连结中必有一条连结u和和w的路的路C,但但u和和w在在G中属于两个不同的连通分支，故中属于两个不同的连通分支，故u和和v在在G中必不连通，因此中必不连通，因此C必通过必通过v，故，故u和和v之间的任一条路之间的任

19、一条路都通过都通过v。定理定理定理定理7-2.37-2.3的证明的证明的证明的证明充分性。充分性。若连接图若连接图G中某两个结点的每一条路都通过中某两个结点的每一条路都通过v，删去，删去v得到子图得到子图G，在，在G中这两个结点必然不连通，故中这两个结点必然不连通，故v是图是图G的割点。的割点。有向图的连通性有向图的连通性有向图的连通性有向图的连通性设有向图设有向图D=u可达可达v:u到到v有一条路有一条路.规定规定u到自身总是可达的到自身总是可达的.可达具有自反性和传递性，但不一定具有对称性。可达具有自反性和传递性，但不一定具有对称性。u到到v的的距距离离（或或短短程程线线）:u到到v长长度

20、度最最短短的的路路的的长长度度(u可可 达达 v)，记记 作作 d。若若 u不不 可可 达达 v,规规 定定d=.距离的性质：距离的性质：1.d 0,2.d=0 3.d+d d 注意：注意：d d强连通、弱连通、单侧连通强连通、弱连通、单侧连通强连通、弱连通、单侧连通强连通、弱连通、单侧连通图的直径：图的直径：基图：基图：把有向图中边的方向忽略得到的无向图称为该把有向图中边的方向忽略得到的无向图称为该有向图的基图。有向图的基图。定义定义7-2.6 在简单有向图在简单有向图G中，任何一对结点间，至中，任何一对结点间，至少有一个结点到另一个结点是可达的，则称这个图少有一个结点到另一个结点是可达的，

21、则称这个图是是单侧连通的单侧连通的.如果对于图如果对于图G中的任何一对结点两者之间是互相可中的任何一对结点两者之间是互相可达的，则称这个图是达的，则称这个图是强连通的强连通的.如果在图如果在图G的基图是连通的，则称该图为的基图是连通的，则称该图为弱连通的弱连通的.实例实例实例实例例例7 判断下列图的连通性。判断下列图的连通性。强连通的强连通的单侧连通的单侧连通的弱连通的弱连通的强连通判别法强连通判别法强连通判别法强连通判别法定定理理7-2.4 一一个个有有向向图图G是是强强连连通通的的，当当且且仅仅当当G中中存存在至少包含每个结点一次的回路。在至少包含每个结点一次的回路。证明证明 充分性充分性

22、 设设G中有一个回路，它至少包含每个结点一次，中有一个回路，它至少包含每个结点一次，则则G中任两个结点都是相互可达的，中任两个结点都是相互可达的，故故G是强连通图。是强连通图。必要性必要性 设设G含有含有n个结点且是强连通的，个结点且是强连通的，则任意两个结点都是相互可达。则任意两个结点都是相互可达。定理定理定理定理7-2.47-2.4的证明的证明的证明的证明 故故vi可达可达vi+1，i=1,2,n-1，设设Pi是是vi到到vi+1的路的路,Pn是是vn到到v1的路的路,则则P1,P2,Pn-1,Pn所所围围成成的的回回路路经经过过G中中每每个个结结 点至少一次点至少一次.定定理理 图图G单

23、单向向连连通通当当且且仅仅当当G中中存存在在经经过过每每个个顶顶点点至少一次的路。至少一次的路。定定理理 若若图图是是G强强连连通通的的，则则必必是是单单侧侧连连通通的的；若若图图G是单侧连通的，则必是弱连通的。是单侧连通的，则必是弱连通的。强分图强分图强分图强分图，弱分图，单侧分图弱分图，单侧分图弱分图，单侧分图弱分图，单侧分图定义定义7-2.7 在简单有向图中，具有强连通性质的最大在简单有向图中，具有强连通性质的最大子图，称为子图，称为强分图强分图；具有单侧连通性质的最大子；具有单侧连通性质的最大子图，称为图，称为单侧分图单侧分图；具有弱连通性质的最大子图，；具有弱连通性质的最大子图，称为

24、称为弱分图弱分图。强连通分图：强连通分图：v1,v2,v3,v4，v5单侧分图：单侧分图：v1,v2,v3,v4,v5弱分图：弱分图：v1,v2,v3,v4,v5定理定理定理定理7-2.57-2.5定理定理7-2.5 在有向图在有向图G=中，它的每一个结点位于中，它的每一个结点位于且仅位于一个强分图中。且仅位于一个强分图中。证明证明 先证每一个结点都位于一个强分图中。先证每一个结点都位于一个强分图中。vV，令，令S是是G中所有与中所有与v相互可达的结点的集合，相互可达的结点的集合，显然显然v S，而且，而且S是是G的一个强分图的一个强分图.故故G的每一结点必位于一个强分图中。的每一结点必位于一

25、个强分图中。再证每一个结点仅位于一个强分图中。再证每一个结点仅位于一个强分图中。假设假设v位于两个不同的强分图位于两个不同的强分图S1与与S2之中，因为之中，因为S1中每中每个结点与个结点与v互相可达，而互相可达，而v与与S2中的每个结点也互相可中的每个结点也互相可达，故达，故S1中任何结点与中任何结点与S2中任何一个结点通过中任何一个结点通过v都互都互相可达，这与相可达，这与S1为强分图矛盾。故得证。为强分图矛盾。故得证。扩大通路法扩大通路法扩大通路法扩大通路法 设设G为为n阶无向图，阶无向图，E，设，设l为为G中一条路中一条路径，径，若此路径的始点或终点与通路外的顶点相邻，就若此路径的始点

26、或终点与通路外的顶点相邻，就将它们扩到通路中来将它们扩到通路中来。继续这一过程，直到最后得到继续这一过程，直到最后得到的通路的两个端点不与通路外的顶点相邻为止。的通路的两个端点不与通路外的顶点相邻为止。设最后得到的路径为设最后得到的路径为l+k(长度为长度为l的路径扩大成了长度的路径扩大成了长度为为l+k的路径的路径)，称，称l+k为为“极大路径极大路径”。称使用此种方法证明问题的方法为称使用此种方法证明问题的方法为“扩大路径法扩大路径法”。有向图中可以类似地讨论，只须注意，在每步扩大中有向图中可以类似地讨论，只须注意，在每步扩大中保持有向边方向的一致性。保持有向边方向的一致性。关于极大通路的

27、说明关于极大通路的说明关于极大通路的说明关于极大通路的说明n由某条路经扩大出的极大路径不唯一。由某条路经扩大出的极大路径不唯一。n极大路径不一定是图中最长的路径。极大路径不一定是图中最长的路径。实例实例实例实例8 8例例8 设设G为为n（n4）阶无向简单图，阶无向简单图，(G)3。证明证明G中存在长度大于或等于中存在长度大于或等于4的圈。的圈。证明证明 不妨设不妨设G是连通图，否则，因为是连通图，否则，因为G的各连通分支的的各连通分支的 最小度也都大于或等于最小度也都大于或等于3，因而可对它的每个连通，因而可对它的每个连通 分支分别进行讨论。分支分别进行讨论。设设u,v为为G中任意两个顶点，中

28、任意两个顶点，由于由于G是连通图，因而是连通图，因而u,v之间存在通路，之间存在通路，用用“扩大通路法扩大通路法”扩大这条通路，设最后得到的扩大这条通路，设最后得到的“极极 大通路大通路”为为lv0v1vl，易知，易知l3.若若v0与与vl相邻，则相邻，则l(v0,vl)为长度大于或等于为长度大于或等于4的圈的圈.否则，由于否则，由于d(v0)(G)3，因而，因而v0除与除与l上的上的v1相相邻外，还存在邻外，还存在l上的顶点上的顶点vk(k1)和和vt(kt l)与与v0相相邻，则邻，则v0v1vkvtv0为一个圈且长度大于或等于为一个圈且长度大于或等于4。单向连通判定的证明单向连通判定的证

29、明单向连通判定的证明单向连通判定的证明定定理理 图图G单单侧侧连连通通当当且且仅仅当当G中中存存在在经经过过每每个个顶顶点点至少一次的路。至少一次的路。证明证明 充分性。充分性。因为因为G中存在经过每个顶点至少一次的路，则对于中存在经过每个顶点至少一次的路，则对于G中的任意两个结点中的任意两个结点u,v,必有必有u可达可达v或或v可达可达u，所以，所以G是是单向连通。单向连通。必要性。必要性。设有向图设有向图G含有含有n个结点且是单侧连通的，个结点且是单侧连通的，任取一个结点任取一个结点u，构造包含，构造包含u的极大有向通路的极大有向通路P，设设P的起点和终点是的起点和终点是w和和v。若若P的

30、长度等于的长度等于n-1，定理得证，定理得证单向连通判定的证明单向连通判定的证明单向连通判定的证明单向连通判定的证明若若P的长度小于的长度小于n-1，则存在结点，则存在结点s不在不在P上，且上，且s不会不会是是w的前驱，也不会是的前驱，也不会是v的后继，因为的后继，因为G是单向连同的，是单向连同的，所以要么所以要么P上的所有结点可达上的所有结点可达s，要么，要么P上存在结点上存在结点t，使，使得得s可达可达t.综上所述，能得到一条包含综上所述，能得到一条包含s的更长的路，一次进行总的更长的路，一次进行总可以找到一条经过每一结点的路。可以找到一条经过每一结点的路。二部图二部图二部图二部图定定义义

31、 设设G为为一一个个无无向向图图，若若能能将将V分分成成V1和和V2(V1V2V,V1V2)，使使得得G中中的的每每条条边边的的两两个个端端点点都都是是一一个个属属于于V1，另另一一个个属属于于V2，则则称称G为为二二部部图图（或或称称二二分分图图，偶偶图图等等），称称V1和和V2为为互互补补顶顶点点子集子集。常将二部图常将二部图G记为记为。若若G是是简简单单二二部部图图，V1中中每每个个顶顶点点均均与与V2中中所所有有顶顶点点相相邻邻，则则称称G为为完完全全二二部部图图，记记为为Kr,s，其其中中r|V1|，s|V2|。说明说明 n阶零图为二部图。阶零图为二部图。二部图举例二部图举例二部图举

32、例二部图举例K6的子图的子图K6的子图的子图K3,3K2,3K3,3K2,3二部图的判定定理二部图的判定定理二部图的判定定理二部图的判定定理定理定理 一个无向图一个无向图G是二部图当且仅当是二部图当且仅当G中无中无奇数长度的回路。奇数长度的回路。证明证明 必要性。必要性。若若G中无回路，结论显然成立。中无回路，结论显然成立。若若G中有回路，只需证明中有回路，只需证明G中无奇圈。中无奇圈。设设C为为G中任意一圈，令中任意一圈，令Cvi1vi2vilvi1，易知，易知 l2。不妨设不妨设vi1V1，则必有则必有vilV-V1=V2，而而l必为偶数，于是必为偶数，于是C为偶圈，为偶圈，由由C的任意性

33、可知结论成立。的任意性可知结论成立。二部图的判定定理二部图的判定定理二部图的判定定理二部图的判定定理充分性。充分性。不妨设不妨设G为连通图，否则可对每个连通分支进行讨论为连通图，否则可对每个连通分支进行讨论.设设v0为为G中任意一个顶点，令中任意一个顶点，令V1v|vV(G)d(v0,v)为偶数为偶数V2v|vV(G)d(v0,v)为奇数为奇数易知，易知，V1,V2,V1V2，V1V2V(G)。下面证明下面证明V1中任意两顶点不相邻中任意两顶点不相邻,V2中任意两点不相邻中任意两点不相邻.若存在若存在vi,vjV1相邻，令相邻，令(vi,vj)e，设设v0到到vi,vj的的短线程短线程分别为分

34、别为i,j，则它们的长度则它们的长度d(v0,vi),d(v0,vj)都是偶数，都是偶数，故故ije构成奇圈，这与已知条件矛盾。构成奇圈，这与已知条件矛盾。类似可证类似可证V2中也不存在相邻的顶点中也不存在相邻的顶点.学习要点与基本要求学习要点与基本要求学习要点与基本要求学习要点与基本要求n深刻理解路与回路的定义及其分类深刻理解路与回路的定义及其分类.n理解无向图的连通性、连通分支等概念理解无向图的连通性、连通分支等概念.n深刻理解无向图的点连通度、边连通度等概念及其深刻理解无向图的点连通度、边连通度等概念及其之间的关系，并能熟练求出给定图的点连通度和边之间的关系，并能熟练求出给定图的点连通度

35、和边连通度连通度.n理解有向图连通性的概念及其分类理解有向图连通性的概念及其分类.n掌握判断有向连通图类型的方法掌握判断有向连通图类型的方法.n了解二分图的概念及其判定了解二分图的概念及其判定.n作业作业7-2：(5),(8)返回返回实例分析实例分析实例分析实例分析例题例题1 设设G是无向图，证明是无向图，证明e是是G的割边当且仅当的割边当且仅当e不包不包含在含在G的闭迹中。的闭迹中。证明证明 充分性。充分性。设设e=(u,v)不包含在不包含在G的闭迹中，那么的闭迹中，那么u与与v之间不存在之间不存在除了除了e外的其它的路，所以在外的其它的路，所以在G-e中中u与与v不连通，不连通，因此因此G

36、-e是非连通图，故是非连通图，故e是是G的割边的割边.必要性。必要性。设设e=(u,v)是是G的割边，假设的割边，假设e在在G的闭迹的闭迹C中，中，那么那么C-e中存在从中存在从u到到v的路，的路，所以所以G-e中中u与与v是连通的，这与是连通的，这与e是割边矛盾。是割边矛盾。实例分析实例分析实例分析实例分析例题例题2 若无向图若无向图G中恰有两个奇数度的结点，则这两中恰有两个奇数度的结点，则这两个结点间必有一条路。个结点间必有一条路。证明证明 设无向图设无向图G中两个奇数度结点为中两个奇数度结点为u和和v.从从u开始构造一条迹，即从开始构造一条迹，即从u出发经关联于出发经关联于u的边的边e1

37、到达结点到达结点u1，若若d(u1)为偶数，则必可由为偶数，则必可由u1经关联于经关联于结点结点u1的边的边e2到达结点到达结点u2，依次进行下去，每边只，依次进行下去，每边只取取1次，直到另一个奇数度结点次，直到另一个奇数度结点.(1)若结束点是若结束点是v，则，则u到到v的一条路就构造好了的一条路就构造好了.(2)若结束点是若结束点是u，那么此路是闭迹。，那么此路是闭迹。实例分析实例分析实例分析实例分析闭迹上每个结点都关联偶数条边，但闭迹上每个结点都关联偶数条边，但d(u)为奇数，为奇数，所以至少有所以至少有1条关联于条关联于u的边不在该闭迹上。的边不在该闭迹上。从从u出发沿该边按照上述方法继续构造路，直到奇数出发沿该边按照上述方法继续构造路，直到奇数度结点度结点v结束，这就是一条从结束，这就是一条从u到到v的路的路.返回返回实例实例实例实例1 1中路的动画演示中路的动画演示中路的动画演示中路的动画演示路：路：v1e2v3e3 v2e4 v3e3 v2e6 v5e7 v3返回返回回路：回路：v2e3v3e4v2e1v1e2v3e4v2