《离散数学》PPT课件：第8章 一些特殊的图（8.1-8.3）

第8章一些特殊的图 81二部图 82欧拉图 83哈密顿图 84平面图

1 第8章 一些特殊的图 8.1 二部图 8.2 欧拉图 8.3 哈密顿图 8.4 平面图

81二部图 二部图 完全二部图 匹配 极大匹配 最大匹配 匹配数 完备匹配

2 8.1 二部图 ▪ 二部图 ▪ 完全二部图 ▪ 匹配 ▪ 极大匹配 ▪ 最大匹配 ▪ 匹配数 ▪ 完备匹配

二部图 定义设无向图G=VE>,若能将分成V和V2 (Ⅳ∪V2=V⌒V2=⑦),使得G中的每条边的两个端 点都一个属于V1,另一个属于V2,则称G为二部图, 记为,称V和V为互补顶点子集又若G 是简单图,且V中每个顶点均与V2中每个顶点都相 邻,则称G为完全二部图,记为K,其中F=|V1=V2 注意:n阶零图为二部图

3 二部图 定义 设无向图 G=, 若能将V 分成V1 和 V2 (V1V2 =V, V1V2 =), 使得G中的每条边的两个端 点都一个属于V1 , 另一个属于V2 , 则称G为二部图, 记为, 称V1和V2为互补顶点子集.又若G 是简单图, 且V1中每个顶点均与V2中每个顶点都相 邻, 则称G为完全二部图, 记为Kr,s , 其中r=|V1 |, s=|V2 |. 注意: n 阶零图为二部图

二部图的判别法 定理无向图G=是二部图当且仅当G中无奇圈 例下述各图都是二部图

4 二部图的判别法 定理 无向图G=是二部图当且仅当G中无奇圈 例 下述各图都是二部图

匹配 设G=, 匹配边独立集):任2条边均不相邻的边子集 极大匹配:添加任一条边后都不再是匹配的匹配 最大匹配:边数最多的匹配 匹配数:最大匹配中的边数,记为月 例3个图的匹配数依次为3,3,4

5 匹配 设G=, 匹配(边独立集): 任2条边均不相邻的边子集 极大匹配: 添加任一条边后都不再是匹配的匹配 最大匹配: 边数最多的匹配 匹配数: 最大匹配中的边数, 记为1 例 3个图的匹配数 依次为3, 3, 4

匹配(续) 设M为G中一个匹配 v与v被M匹配:(2)EM 为M饱和点:M中有边与u关联 为M啡非饱和点:M中没有边与ν关联 M为完美匹配:G的每个顶点都是M饱和点 例关于M1,a,b,d是饱和点a。b c是非饱和点 f M1不是完美匹配 M2是完美匹配 M d M

6 匹配 (续) 设M为G中一个匹配 vi与vj被M匹配: (vi ,vj )M v为M饱和点: M中有边与v关联 v为M非饱和点: M中没有边与v关联 M为完美匹配: G的每个顶点都是M饱和点 例 关于M1 , a,b,e,d是饱和点 f,c是非饱和点 M1不是完美匹配 M2是完美匹配 M1 M2

二部图中的匹配 定义设G=为二部图,VV2,M是G中最 大匹配,若V1中顶点全是M饱和点,则称M为G中V1 到v2的完备匹配当V=H2时,完备匹配变成完美 匹配 例图中红边组成各图的一个匹配,(1)为完备的,但不是完 美的;(2)不是完备的,其实(2)中无完备匹配;(3)是完美的 (2)

7 二部图中的匹配 定义 设G=为二部图, |V1 ||V2 |, M是G中最 大匹配, 若V1中顶点全是M饱和点, 则称M为G中V1 到V2的完备匹配. 当|V1 |=|V2 |时, 完备匹配变成完美 匹配. (1) (2) (3) 例 图中红边组成各图的一个匹配，(1)为完备的, 但不是完 美的; (2)不是完备的, 其实(2)中无完备匹配; (3) 是完美的

Ha定理 定理(Hal定理)设二部图G=中,V1V2G中存 在从V到V的完备匹配当且仅当v中任意k个顶点至少与V 中的k个顶点相邻(k=1,2,…,V1D 由Ha定理不难证明,上一页图(2)没有完备匹配 定理设二部图G=中,如果存在仑1,使得V中每个 顶点至少关联t条边,而V中每个顶点至多关联t条边,则G 中存在V到V2的完备匹配 Hl定理中的条件称为“相异性条件”,第二个定理中的条 件 称为t条件.满足t条件的二部图一定满足相异性条件

8 Hall定理 定理(Hall定理)设二部图G=中，|V1 ||V2 |. G中存 在从V1到V2的完备匹配当且仅当V1中任意k个顶点至少与V2 中的k个顶点相邻(k=1,2,…,|V1 |). 由Hall定理不难证明, 上一页图(2)没有完备匹配. 定理 设二部图G=中, 如果存在t1,使得V1中每个 顶点至少关联t 条边, 而V2中每个顶点至多关联t条边，则G 中存在V1到V2的完备匹配. Hall定理中的条件称为“相异性条件” , 第二个定理中的条 件 称为 t 条件. 满足 t 条件的二部图一定满足相异性条件

一个应用实例 例某课题组要从a,b,C,d,e5人中派3人分别到上海、广州、 香港去开会已知a只想去上海,b只想去广州,c,d,e都表 示想去广州或香港问该课题组在满足个人要求的条件下, 共有几种派遣方案? 解令G=<V1,V2E,其中V={s,g,x,V2={ab,c,e}, E={u,)|u∈V1,v∈V2,想去u}, 其中s,g,x分别表示上海、广州和香港 G如图所示 G满足相异性条件,因而可给 出派遣方案,共有9种派遣方案 (请给出这9种方案 b

9 一个应用实例 例 某课题组要从a, b, c, d, e 5人中派3人分别到上海、广州、 香港去开会. 已知a只想去上海，b只想去广州，c, d, e都表 示想去广州或香港. 问该课题组在满足个人要求的条件下， 共有几种派遣方案？ 解 令G=, 其中V1={s, g, x}, V2={a, b, c, d, e}, E={(u,v) | uV1 , vV2 , v想去u}, 其中s, g, x分别表示上海、广州和香港. G如图所示. G 满足相异性条件，因而可给 出派遣方案，共有9种派遣方案 (请给出这9种方案)

82欧拉图 欧拉通路 欧拉回路 欧拉图 ■半欧拉图 10

10 8.2 欧拉图 ▪欧拉通路 ▪欧拉回路 ▪欧拉图 ▪半欧拉图