第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为二部图, 记为<V1,V2,E>,称V和V为互补顶点子集又若G 是简单图,且V中每个顶点均与V2中每个顶点都相 邻,则称G为完全二部图,记为K,其中F=|V1=V2 注意:n阶零图为二部图
3 二部图 定义 设无向图 G=<V,E>, 若能将V 分成V1 和 V2 (V1V2 =V, V1V2 =), 使得G中的每条边的两个端 点都一个属于V1 , 另一个属于V2 , 则称G为二部图, 记为<V1 ,V2 ,E>, 称V1和V2为互补顶点子集.又若G 是简单图, 且V1中每个顶点均与V2中每个顶点都相 邻, 则称G为完全二部图, 记为Kr,s , 其中r=|V1 |, s=|V2 |. 注意: n 阶零图为二部图
二部图的判别法 定理无向图G=<V,E>是二部图当且仅当G中无奇圈 例下述各图都是二部图
4 二部图的判别法 定理 无向图G=<V,E>是二部图当且仅当G中无奇圈 例 下述各图都是二部图
匹配 设G=<V,E>, 匹配边独立集):任2条边均不相邻的边子集 极大匹配:添加任一条边后都不再是匹配的匹配 最大匹配:边数最多的匹配 匹配数:最大匹配中的边数,记为月 例3个图的匹配数依次为3,3,4
5 匹配 设G=<V,E>, 匹配(边独立集): 任2条边均不相邻的边子集 极大匹配: 添加任一条边后都不再是匹配的匹配 最大匹配: 边数最多的匹配 匹配数: 最大匹配中的边数, 记为1 例 3个图的匹配数 依次为3, 3, 4