6.2图的连通性

第二节图的连通性图的连通路和回路连通分支有向路强连通图的割集割集的基本概念割集的性质路和回路路：一个点和边的交替序列(ni,eij,…,ekl,nl)，记为{ni,nl}路简单路：边不重的路初级路：点不重的路回路：至少包含一个边并且ni=nl的{ni,nl}路简单回路：边不重的回路初级回路：点不重的回路例(1,2,3,4,2,3,5,6)是一条{1,6}路(1,2,4,5,3,4,6)是一条{1,6}简单路(1,2,3,5,6)一条{1,6}初级路(1,2,4,3,2,4,5,3,1)是一条回路(1,2,3,4,5,3,1)是一条简单回路(1,2,4,5,3,1)是一条初级回路1.图的连通连通分支点i和j点是连通的：G中存在一条{i,j}路G是连通的：G中任意两点都是连通的连通分支：G的极大连通子图下图中(a)是连通图，(b)是一个具有三个连通分支的非连通图。(a)(b)连通分支续定理6.2.1设G有p个连通分支，则G的邻接矩阵可以表示成如下形式：pAAAA0021有向路有向图G中的一条有向路：一个点和弧的交错序列(ni,aij,nj,…,nk,akl,nl)，记为(ni,nl)有向路简单有向路：弧不重的有向路初级有向路：点不重的有向路有向回路：至少包含一条弧且ni=nj的(ni,nj)有向路简单有向回路：弧不重的有向回路初级有向回路：点不重的有向回路例(1,2,4,3,2,4,6)是一条(1,6)有向路(1,2,4,5,3,4,6)是一条(1,6)简单有向路(1,2,3,4,6)是一条(1,6)初级有向路(1,2,4,3,2,4,5,3,1)是一条有向回路(1,2,3,4,5,3,1)是一条简单有向回路(1,2,4,5,3,1)是一条初级有向回路165432强连通点i和点j是强连通的：G中存在一条(i,j)有向路,也存在一条(j,i)有向路.G是强连通的：G中任意两点都是强连通的.G.的强连通分支：G的极大强连通子图.下图中，(a)是一个强连通分支，(b)是一个具有三个强连通分支的非强连通图。(a)(b)强连通续定理6.2.2设G有p个强连通分支，则的邻接矩阵可以表示成如下形式：pAAAA021割集的基本概念2.图的割集图G的割边：如果从G中删去它就使图的连通分支数严格增加的边.显然一条边是割边当且仅当它不在任何简单回路中.{S,T}割:一个端点在S中,另一个端点在T中的边集合,其中S和T是N的两个不相交子集.图G的边割(S,S):从G中删去它就使图的连通分支数严格增加的边集合.割集：G的极小边割.割集的基本概念续例图6.2.5图6.2.6图6.2.5中{2,4}和{6,7}都是割边图6.2.6中，边集{{2,1}，{2,4}，{2,3}}和边集{{2,3}，{2,4}，{1,4}，{1,5}}均为割集176542315432有向图G的割边:如果从G中删去它就使图的连通分支数严格增加的边.(S,T)割:有向图G=(N,A)中尾在S中,头在T中的弧集合.有向图G的弧割(S,S):从G中删去它就使图的强连通分支数严格增加的弧集合.有向割集:G的极小弧割.割集的性质定理6.2.3任何边割都是不相交割集的并.定理6.2.4任给图G,设C是G的一条简单回路,Ω={S,T}是G的一个割集,并用E(C),E(Ω)分别表示C,Ω所包含的边集合.若E(C)∩E(Ω)≠Φ,则|E(C)∩E(Ω)|≥2。