对于有向图，有三种不同的连通概念。现给出下面的定义：定义5.15：设u和v是有向图G的两个顶点若从u到v存在一条有向路则称v是从u可达的，或称从u可达V。定义5.16：设有向图G.若G中任何两顶点是互相可达的，则称G为强连通图。若G中任何两顶点至少有一个顶点从另一个顶点可达，则称G为单向连通图或称连通有向图。若G中弧的方向不考虑时，任何两顶点之间有一条路，则称G为弱连通图或简称连通图
对于有向图, 有三种不同的连通概念。 现给出下面的定义: 定义5.15：设u和v是有向图G的两个顶点, 若从u到v存在一条有向路,则称v是从u可 达的,或称从u可达v。 定义5.16：设有向图G,若G中任何两顶点 是互相可达的,则称G为强连通图。若G 中任何两顶点至少有一个顶点从另一个 顶点可达, 则称G为单向连通图,或称连通 有向图。若G中弧的方向不考虑时,任何 两顶点之间有一条路,则称G为弱连通图 或简称连通图
U14001604首装04核邮国银中国单调来美庭道上定义十个二元关系民就谢师两市销百，店安茶用专尚连支快全客康虹车育关更吧等价2家便费庭vg显，把+3U3（）由毒支（b）星羊古前价（）收例如图a）是强连通的.(b）是单向连通的，而（c)是弱连通的。对V作划分，将V划分为非空子集Vi，V2...V使得两个顶点u和v属于同一子集V当且仅当u和v是互相可达的。每个顶点子集V导出的子图GV是强连通的，记为G称为G的一个强连通分支。G中有0个强连通分支:Gi,G2....,Go
例如图(a)是强连通的,(b)是单向连通的,而(c)是弱连 通的。 对V作划分,将V划分为非空子集V1 , V2 ,.,Vω,使得两 个顶点u和v属于同一子集V当且仅当u和v是互相可 达的。 每个顶点子集Vi导出的子图G(Vi )是强连通的,记为Gi , 称为 G的一个强连通分支。G中有ω个强连通分 支:G1 ,G2 ,.,Gω
0102U3U2U3U1G(Va)G(V2)G(V)是连通图当以证期：时于老从乐有一0A茶V4U8V8S国的路V6UTUU7V605#的闲路径(a)(b)图（a不是强连通图在顶点集V={Vi,V2,V34,V,V6V,V8上将V划分为3个子集,V-{Vi,V,V8i,V2-(V2,V3,Vs,V]V3-lv4i,对应得到3个强连通分支：G(V1),G(V2),G(V3),如图(b)所示
图 ( a) 不 是 强 连 通 图 , 在 顶 点 集 V ={v1 ,v2 ,v3 ,v4 ,v5 ,v6 ,v7 , v8 }上将V划分为3个 子 集 , V1={v1 ,v7 ,v8 }, V2={v2 ,v3 ,v5 ,v6 }, V3={v4 }, 对 应 得 到 3 个 强 连 通 分 支:G(V1 ),G(V2 ),G(V3 ),如图 (b)所示
注意有向图的强连通分支与图的连通分支有一个很大的区别：有向图的每一条弧不一定属于一个强连通分支而每个顶点恰属于一个强连通分支。但图的每条边恰属于一个连通分支
注意有向图的强连通分支与图的连通分支有一 个很大的区别: 有向图的每一条弧不一定属于一个强连通分支, 而每个顶点恰属于一个强连通分支。但图的每 一条边恰属于一个连通分支
X3X4X2Y4Y3Y2K2.3K3,3称为G的一个一图 (b)图 (a)鱼图G具有一划分上图也是二分图，它可以作这样的二划分：V,=(X1,X2,X3,X4),V2=(yi,y2.y3.y4.ys),也可以作这样的二划分：V'i={x1,X2,X3.y4.ysi, V'2={yi,y2,Y3,X4),都符合二分图的要求：每条边的一个端点在V(V）中，另一端点在V2(V2）中
四、二分图 现在给出二分图的概念。 定义5.21：若图G的顶点集V能划分为两个 子集V1和V2 , 并且每条边的一个端点在V1中, 另 一端点 在 V2中 ,则称 G为二 分图 ,记 为 G(V1 ,V2 )。V划分为V1和V2 ,称为G的一个二 划分, 记为(V1 ,V2 )。若简单图G具有二划分 (V1 ,V2 ),并且V1中每个顶点与V2中每个顶点 恰 有 一 边 相 连 , 称 G 为 完 全 二 分 图 。 若 |V1 |=m,|V2 |=n,则这样的完全二分图记为Km,n。 例如图(a)和图(b)都是完全二分图：K3,3和 K2,3。 上图也是二分图，它可以作这样的二划分： V1={x1 ,x2 ,x3, x4 }, V2={y1,y2,y3,y4,y5 }, 也可以作这样的二划分： V'1={x1 ,x2 ,x3,y4,y5 }, V'2={y1,y2,y3, x4 }, 都符合二分图的要求：每条边的一个端点在V1 (V'1 )中 ，另一端点在V2 (V'2 )中