离散数学-耿素云ppt(第5)6.1-3离散数学-耿素云ppt(第5版)6.1-3.ppt

格雷码(续) 格雷码: 相邻的两个以及最后一个和第一个之间只有一位不 同的把n位0-1串序列 例如, 000, 001, 011, 010, 110, 111, 101, 100是一个格雷码 构造n维立方体图: 2n个顶点, 每个顶点表示一个n位串, 两个 顶点之间有一条边当且仅当它们的n位串仅相差一位. 当n?2时, 图中一定存在哈密顿回路. * 001 101 111 011 000 100 010 110 01 00 11 10 * * * * 第6章 特殊的图 6.1 二部图 6.2 欧拉图 6.3 哈密顿图 6.4 平面图 * 6.1 二部图 二部图 完全二部图 匹配 极大匹配,最大匹配,完美匹配,完备匹配 Hall定理 * 二部图 定义 设无向图 G=V,E, 若能将V 划分成V1 和 V2 (V1?V2=V, V1?V2=?), 使得G中的每条边的两个端 点都一个属于V1, 另一个属于V2, 则称G为二部图, 记为V1,V2,E, 称V1和V2为互补顶点子集. 又若G 是简单图, 且V1中每个顶点都与V2中每个顶点相邻, 则称G为完全二部图, 记为Kr,s, 其中r=|V1|, s=|V2|. 注意: n 阶零图为二部图. * 二部图(续) 例 下述各图是否是二部图? 定理 无向图G=V,E是二部图当且仅当G中无奇圈 不是 * 匹配 设G=V,E, 匹配(边独立集): 任2条边均不相邻的边子集 极大匹配: 添加任一条边后都不再是匹配的匹配 最大匹配: 边数最多的匹配 匹配数: 最大匹配中的边数, 记为?1 例 极大匹配 最大匹配 ?1=3 * 匹配 (续) 设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=V1,V2,E为二部图, |V1|?|V2|, M是G中最 大匹配, 若V1中顶点全是M饱和点, 则称M为G中V1 到V2的完备匹配. 当|V1|=|V2|时, 完备匹配变成完美 匹配. 例 完备,不完美 不完备 完美 * Hall定理 定理(Hall定理) 设二部图G=V1,V2,E中，|V1|?|V2|. G中存 在从V1到V2的完备匹配当且仅当V1中任意k 个顶点至少与V2 中的k个顶点相邻(k=1,2,…,|V1|). ?相异性条件 由Hall定理, 上一页第2个图没有完备匹配. 定理 设二部图G=V1,V2,E中, 如果存在t?1, 使得V1中每个 顶点至少关联 t 条边, 而V2中每个顶点至多关联t条边，则G 中存在V1到V2的完备匹配. ?t 条件 证 V1中任意k个顶点至少关联kt条边, 这kt条边至少关联V2 中的k个顶点, 即V1中任意k个顶点至少邻接V2中的k个顶点. 由Hall定理, G中存在V1到V2的完备匹配. * 一个应用实例 例 某课题组要从a, b, c, d, e 5人中派3人分别到上海、广州、香港去开会. 已知a只想去上海，b只想去广州，c, d, e都 表示想去广州或香港. 问该课题组在满足个人要求的条件下，共有几种派遣方案？ 解 令G=V1,V2,E, 其中V1={s, g, x}, V2={a, b, c, d, e}, E={(u,v) | u?V1, v?V2, v想去u}, 其中s, g, x分别表示上海、广州和香港. G 满足相异性条件，红边是一个完备匹配, 对应的派遣方案: a?上海, b?广州, d?香港 * 6.2 欧拉图 欧拉通路与欧拉回路 存在欧拉通路和欧拉回路的充分必要条件 * 哥尼斯堡七桥问题 要求边不重复地一笔画出整个图 * 欧拉图 欧拉通路: 图中行遍所有顶点且恰好经过每条边一次的通路. 欧拉回路: 图中行遍所有顶点且恰好经过每条边一次的回路. 欧拉图: 有欧拉回路的图. 半欧拉图: 有欧拉通路回路,但无欧拉回路的图. 几点说明：上述定义对无向图和有向图都适用. 规定平凡图为欧拉图. 欧拉通路是简单通路, 欧拉回路是简单回路. 环不影响图的欧拉性. * 欧拉图实例 例 是否是欧拉图或半欧拉图? 欧拉图 欧拉图 半欧拉图 半欧拉图 不是 不是 * 欧拉图的判别法 定理 无向图G为欧拉图当且仅当