对于有向图,有三种不同的连通概念。 现给出下面的定义 定义5.15:设u和v是有向图G的两个顶点, 若从u到v存在一条有向路,则称v是从u可 达的,或称从u可达v 定义516:设有向图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为弱连通图 或简称连通图
中定策 聊中市回 使个原十 12 例如图(a)是强连通的b是单向连通的而(c)是弱连 通的。 对V作划分将V划分为非空子集Ⅴ1,V2,Vo,使得两 个顶点u和v属于同一子集V当且仅当u和v是互相可 达的。 每个顶点子集Ⅴ导出的子图G(V)是强连通的记为G1, 称为G的一个强连通分支。G中有0个强连通分 支:G 15(29…o°
例如图(a)是强连通的,(b)是单向连通的,而(c)是弱连 通的。 对V作划分,将V划分为非空子集V1 , V2 ,…,Vω,使得两 个顶点u和v属于同一子集V当且仅当u和v是互相可 达的。 每个顶点子集Vi导出的子图G(Vi )是强连通的,记为Gi , 称为 G的一个强连通分支。G中有ω个强连通分 支:G1 ,G2 ,…,Gω
G(V1) G(V2) G(V3) U8 o U4 U U U6 U5 的同路径 图(a)不是强连通图,在顶点集V ={v1,V2,V3,V456y,V}上将Ⅴ划分为3个 子集 19798j9 293955V6J9 V3={4},对应得到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)所示
注意有向图的强连通分支与图的连通分支有 个很大的区别: 有向图的每一条弧不一定属于一个强连通分支 而每个顶点恰属于一个强连通分支。但图的每 条边恰属于一个连通分支
注意有向图的强连通分支与图的连通分支有一 个很大的区别: 有向图的每一条弧不一定属于一个强连通分支, 而每个顶点恰属于一个强连通分支。但图的每 一条边恰属于一个连通分支
X X 4 5 K 2.3 3,3 2.称为G的一个二 图(a) 图()直图G具有二划分 上图也是二分图,它可以作这样的二划分: V1={x1,x2x3.X4,V2={y1y 2,y34,y5∫9 也可以作这样的二划分: {x1,x2,x3y4y53,V2={ 3,44J 都符合二分图的要求:每条边的一个端点在V1(V1中 ,另一端点在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 )中