道路与回路路与圈的相关定理

《道路与回路路与圈的相关定理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录1概念与性质2图的连通性道路与回路3路与圈的相关定理PathandCircuit4道路与回路的判定高晓沨高晓沨(高晓沨(((XiaofengGao)))DepartmentofComputerScienceShanghaiJiaoTongUniv.2016/12/6IntroductionToCS--XiaofengGao2有向道路与有向回路
【【【定义【定义定义】定义】】】有向图有向图G中边序列P=(e,e,…,e),i1i2iq其中e=(v,v)满足:v是是是e的终点,v是是是eijklkij−−−1lij+1的始点,就称P是

2、是是G的一条有向道路。如果eiq的终点也是e的始点,则称P是是是G的一条有向i1回路.道路与回路的定义
简单有向道路/回路:P中边不重复出现.DefinitionofPathandCircuit
初级有向道路/回路:P中结点不重复出现.2016/12/6IntroductionToCS--XiaofengGao32016/12/6IntroductionToCS--XiaofengGao4道路与回路其他定义
【【【定义【定义定义】定义】】】无向图无向图G中中中,若点边交替序列
长度为奇数的圈（初级回路）称为奇圈；；；P=(vi1,ei

3、1,vi2,ei2,…,eiq−−−1,viq)长度为偶数的圈（初级回路）成为偶圈。。。满足:vij和和和vij+1是是是eij的两个端点,则称P是是是G中的一条链链链或或或道路(path).如果viq=vi1,则称P是是是G中的一个圈圈圈
在含圈的无向简单图G中，称G中最长圈的或或或回路(circuit).长度为G的的的周长，记做c(G)，，，G中最短圈的
简单道路/回路:P中没有重复出现的边.长度为G的的的围长，记做g(G)。。。
初级道路/回路:P中没有重复出现的结点.
注：道路又称通道；回路又称闭通道（开通道即
无向完全图K(

4、n≥3)的周长为n，围长为3。。。n非回路的道路）；简单道路又称迹迹迹；初级道路又完全二部图K(n≥2)的周长为2n，围长为4。。。n,n称称称路路路、、、路径；初级回路有时也称为圈圈圈。。。2016/12/6IntroductionToCS--XiaofengGao52016/12/6IntroductionToCS--XiaofengGao6简单图中的弦证明
【【【定义【定义定义】定义】】】设设设设C是简单图G中含结点数大于3
在在在G中找到一条极长的初级道路的一个初级回路。如果结点v和和和v在在在C中不P=(e,e,…,e)。不

5、妨设e=(v,v)，，，e=(v,v)。。。ij12l112iii+1相邻，而边(vi,vj)∈∈∈E(G)，则称(vi,vj)是是是C的的的
由于P是极长的初级道路，所以v1和和和vl的邻一条弦弦弦。。。接点都在该道路上。
【【【定理【定理定理】定理】】】若对每一个若对每一个
由已知条件，d(v)≥3，不妨设1v∈∈∈V(G)，都有ΓΓΓ(v)={v,v,v,…}，其中s

6、16/12/6IntroductionToCS--XiaofengGao72016/12/6IntroductionToCS--XiaofengGao8图例二分图的回路
【【【定理【定理定理】定理】】】如果二分图如果二分图G中存在回路，那么它们都是由偶数条边组成的。
【【【证明【证明证明】证明】】】设二分图设二分图G将将将V(G)分为X，，，Y两个点集（二分点集），设C是二分图G的任一回路，不妨设v∈∈∈X是是是C的起点，由于G是是是0二分图，所以沿回路C必须经过偶数条边才能达到某结点v∈∈∈X，因而只有经过偶数条i边才能回到v。。。

7、02016/12/6IntroductionToCS--XiaofengGao92016/12/6IntroductionToCS--XiaofengGao10连通性
若无向图G的任意两个结点之间都存在道路,就称G是是是连通的(connected).
对有向图G,若不考虑边的方向时是连通的,则称G是是是(弱弱弱)连通的的的.
若若若G的连通子图H不是G的任何连通子图的真子图,则称H是是是G的的的极大连通子图,或称连通分支(connectedcomponent).图的连通性显然G的每个连通分支都是它的导出子图.Connectivity

8、oftheGraph任何非连通图都是2个以上连通支的并连通分支又称连通支、连通分量。2016/12/6IntroductionToCS--XiaofengGao112016/12/6IntroductionToCS-