对于有向图,有三种不同的连通概念。 现给出下面的定义 定义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 )中
上图不是二分图。 那么怎样的图才是二分图?二分图有怎 样的特征? 利用回路概念,可以给出二分图的特征。 定理57:G是二分图当且仅当G中没有 奇回路
上图不是二分图。 那么怎样的图才是二分图？二分图有怎 样的特征？ 利用回路概念, 可以给出二分图的特征。 定理5.7：G是二分图当且仅当G中没有 奇回路
证明:(1)若G是二分图则G中没有奇回 路 (V1V)的二分图,若G 没有回路当然就不会 G中有一条回路 不失一般性设v∈V1 v
证明：(1)若G是二分图则G中没有奇回 路 设G是具有二划分(V1 ,V2 )的二分图,若G 没有回路则已成立(没有回路当然就不会 有奇回路。 若 G 有回路 ， 设 G 中 有 一 条 回 路 C:(v0 ,v1 ,…,vm,v0 )。不失一般性,设v0V1
(2)若G中没有奇回路则G是二分图 设G是连通图否则对G的每个分支进行证明。 又设G是一个不包含奇回路的图。 下面关键是构造G的二划分V和V2 然后证明(1,V2)是G的一个二划分
(2)若G中没有奇回路则G是二分图 设G是连通图,否则对G的每个分支进行证明。 又设G是一个不包含奇回路的图。 下面关键是构造G的二划分V1和V2。 然后证明(V1 ,V2 )是G的一个二划分
53欧拉图 一、欧拉图与半欧拉图 定义522:若图G中具有一条包含G中所 有边的闭链,则称它为欧拉闭链简称为欧 拉链称G为欧拉图。若图G中具有一条 包含G中所有边的开链,则称它为欧拉开 链,称G为半欧拉图。 显然,欧拉图除孤立点以外是连通的而孤 立点的有无并不影响对欧拉图的讨论,因 此以后总假设欧拉图是连通的
5.3欧拉图 一、欧拉图与半欧拉图 定义5.22：若图G中具有一条包含G中所 有边的闭链,则称它为欧拉闭链,简称为欧 拉链,称G为欧拉图。若图G中具有一条 包含G中所有边的开链,则称它为欧拉开 链,称G为半欧拉图。 显然,欧拉图除孤立点以外是连通的,而孤 立点的有无并不影响对欧拉图的讨论,因 此以后总假设欧拉图是连通的
定理5.8:设G是连通图,则G是欧拉图当且 仅当G的所有顶点都是偶顶点。 证明:(1)G是欧拉图,证明G的所有顶点 都是偶顶点 设 G 有欧拉链 01V1629ivii+1, ek,Vk),v0=V,其中顶 点可以重复出现边不可重复出现。 在序列中,对任一点v,每当出现一个v,它关 联两条边,故度数增加2, 而v可以重复出现,因此经过v次数的2倍就 是与v;相邻边的总数,即为v的度数,所以 d(v为偶数。 由v的任意性知G中所有顶点为偶顶点
定理5.8：设G是连通图, 则G是欧拉图当且 仅当G的所有顶点都是偶顶点。 证明：(1) G是欧拉图，证明G的所有顶点 都是偶顶点 设 G 有 欧 拉 链 (v0 ,e1 ,v1 ,e2 ,…,ei ,vi ,ei+1 , …,ek ,vk ),v0=vk ,其中顶 点可以重复出现,边不可重复出现。 在序列中,对任一点vi ,每当出现一个vi ,它关 联两条边,故度数增加2， 而vi可以重复出现,因此经过vi次数的2倍就 是与vi相邻边的总数，即为vi的度数，所以 d(vi )为偶数。 由vi的任意性知G中所有顶点为偶顶点