离散数学-特殊的图.pdf

第6章 特殊的图 6.1 二部图 6.2 欧拉图 6.3 哈密顿图 6.4 平面图 1 6.1 二部图 二部图 完全二部图 匹配 极大匹配,最大匹配,完美匹配,完备匹配 Hall定理 2 二部图 定义 设无向图 G= V,E, 若能将V 划分成V 和 V 1 2 (V V V, V V ), 使得G中的每条边的两个端 1 2 1 2 点都一个属于V , 另一个属于V , 则称G为二部图, 1 2 记为 V , V ,E, 称V 和V 为互补顶点子集. 又若G 1 2 1 2 是简单图, 且V 中每个顶点都与V 中每个顶点相邻, 1 2 则称G为完全二部图, 记为K , 其中r=| V |, s=| V |. r,s 1 2 注意: n 阶零图为二部图. 3 二部图(续) 例 下述各图是否是二部图? 不是 定理 无向图G= V,E是二部图当且仅当G中无奇圈 4 匹配 设G= V,E, 匹配(边独立集): 任2条边均不相邻的边子集 极大匹配: 添加任一条边后都不再是匹配的匹配 最大匹配: 边数最多的匹配 匹配数: 最大匹配中的边数, 记为1 例 极大匹配 最大匹配  =3 1 5 匹配 (续) 设M为G中一个匹配 v 与v 被M 匹配: (v ,v ) M i j i j v为M饱和点: M 中有边与v关联 v为M非饱和点: M 中没有边与v关联 M为完美匹配: G的每个顶点都是M饱和点 例 关于M , a,b,e,d是饱和点 1 f,c 是非饱和点 M1不是完美匹配 M2是完美匹配 M1 M2 6 二部图中的匹配 定义 设G= V , V ,E为二部图, | V ||V |, M是G中最 1 2 1 2 大匹配, 若V1 中顶点全是M饱和点, 则称M为G中V1 到V 的完备匹配. 当|V |=|V |时, 完备匹配变成完美 2 1