《14.2通路与回路》由会员分享，可在线阅读，更多相关《14.2通路与回路（4页珍藏版）》请在金锄头文库上搜索。
1、1,14.2 通路、回路、图的连通性,本课基本要求： 要弄清楚图中通路与回路的概念及其分类以及它们的关系。 理解有向连通图的分类及它们之间的关系。,2,定义14.11,给定图G=.设G中顶点和边的交替序列为 =v0e1 v1e2 elvl ,满足如下条件: vi 1和vi 是ei的端点(在G是有向图时,要求vi 1是ei的始点,vi是ei的终点),i=1,2, ,l, 则称为顶点 v0到vl的通路.v0和vl 分别称为此通路的起点和终点,中边的数目l 称为 的长度.当 v0 = vl 时,此通路称为回路.,若中的所有边 e1 , e2 , , el互不相同,则称此回路为简单通路或一条闭迹.,3
2、,若中的所有边 e1 , e2 , , el互不相同,则称此回路为简单通路或一条闭迹.,若通路的所有顶点v0 , v1, , vl互不相同(从而所有边互不相同),则称此通路为初级通路 或一条路径.若回路中,除 v0 = vl外,其余顶点各不相同,所有边也各不相同,则称此回路为初级回路 或圈.,有边重复出现的通路称为复杂通路,有边重复出现的回路称为复杂回路.,由定义可知,初级通路(回路)是简单通路(回路),但反之不真 .,4,定理14.3 在一个n 阶图中,若从顶点vi到vj (vi vj )存在通路,则从 vi到vj存在长度小于等于n 1的初级通路.,推论 在一个n阶图中,若从顶点 vi到 vj (vi vj )存在通路,则从 vi到vj存在长度小于等于 n 1的初级通路.,定理14.4 在一个n阶图中,如果存在 vi到自身的回路,则从 vi到自身存在长度小于等于n的回路.,推论 在一个n阶图中,如果 vi到自身存在一条简单回路,则从 vi到自身存在长度小于等于n 的初级回路.,
