图论及其应用ch5-ch6.ppt

5 图的匹配与独立集 人员分派问题 某公司准备分派n个工人做n件工作，已知这些工人中每个人都胜任一件或几件工作。试问能不能把所有的工人都分派做一件他所胜任的工作？ 构作一个具有二分类(X,Y)的偶图G,这里 对集：设M是图G=(V,E)中边集E的子集,如果M中任何两边都不相邻，则称M为G的一个匹配。 (非)饱和点：在匹配M中边的端点称为M-饱和点,其他顶点称为M-非饱和点. 完美对集：如果G中每个顶点都是M-饱和点,即匹配M将G中所有顶点配成对,则称M为G的完美匹配. 最大对集：如果G中不存在另一匹配M,使得 |M ||M|,则称M为最大匹配,|M|称为G的匹配数. 性质：完美匹配都是最大匹配,反之不然。 举例： 可以看出,工作分配问题可以归结为求二部图G=(X,Y;E)的对集，即 （1）什么情况下，G存在完美对集？ （2）如果没有完美对集，则怎样求 G的最大对集？ 下面我们依次给出答案。 G的M交错路：设M是G的匹配,G的M交 错路:是指其边在E\M和M中交错出现的 路.（ E\M 和M 没有谁先谁后的原则） M –可扩路）:是指起点和终点都是M非 饱和的M交错路. 举例说明。 定理5.1.1：图G的匹配M为最大匹配的充要条件是：G中不存在M可扩路。 定理5.1.1的证明 那么一个图存在完美对集的充要条件呢？ 举例 5.2 二分图的对集 THE PROOF OF THEORM 5.2.1 推论及其证明 匈牙利算法是用来求最大匹配的算法之一。 定义10：设M是G的匹配,G的M交替路:是指其边在E\M和M中交错出现的路. 定义11：M可扩路（ M –增长路）:是指起点和终点都是M非饱和的M交错路. 举例说明。 定理3：图G的匹配M为最大匹配的充要条件是：G中不存在M可扩路。 5.3 匈牙利算法 定义：设M是二部图G=(X,Y;E)的一个匹配,u是X中的一个M-未饱和点.如果G的一个子图T满足下面两个条件： (1)u (2)对于T的每一个顶点v,有唯一的P(u,v)路,且是M-交替路,则称T为G的一棵以u为根的M-交替树. 匈牙利算法 5.4 独立集和覆盖 二分图的对集和覆盖 独立集和覆盖的关系 边覆盖和对集的关系 5.5 Ramsey数 问题：在9个人中一定有3个人互相认识或有4 个人互不认识。 对应怎样的图论问题呢？ 其中的9能否更小呢? 举例说明。 Ramsey数 已有的简单定理 已知的Ramsey数 Ramsey定义的推广 6 图的染色 面染色，顶点染色，边染色之间能否相互转 化？四色问题是否有其他描述方式? 6.1 顶点染色 色数算法 理论基础： 6.2 平面图和五色定理 几个重要结果 举例 例： 设是平面上n个点，其中任意两点的距离至少是1，证明至多有3n-6对点，每对点的距离恰好是1. 你认为有哪些正多面体？ 练习：存在且只存在5种多面体： 正四面体、正方体、正八面体和正十二面体。 平面图的充要条件 五色定理 定理6.2.5 每个平面图的色数不超过5。 四色猜想的等价命题 补充内容： 厚度和交叉数（指了解概念即可） 厚度：一个非平面图不能嵌入平面,但是可分 成若干子图分别嵌入一些平面上.若G可表示 为若干个平面图的并图称这种平面图的最小 数为G的厚度。[应用：设计印刷电路] 交叉数：把一个平面图画在一个平面上一定 会有一些边，除端点外还有公共点，即由一 些边在非端点处出现交叉，最小交叉的数目 称为G的交叉数。 6.3 边染色 几个重要结论 实际问题中的应用 排课表问题： 6.4 列表染色（了解） 列表染色：给图G的每个顶点x一个列表L(x), 称G是L可染色的是指对每个顶点x,都可以从 其对应的列表L(x)中找到一种染色c(x)，使得c 是G的一格正常染色。如果每个顶点列表长度 都相同，此时列表着色数定义为满足下面条件 的最小的正整数k,对任一顶点x，当|L(x)|=k 时，G都是L可染色的。 6.5 圆染色和圆色数（了解） 圆染色： 那末对于任意图而言，其色数如何？ 事实上，推论2有更好的推广。 边染色与对集之间的关系？ 具体的算法和实现过程自学，通过学习，你能否 给出更理想的算法，能否将算法用到具体的案例 中来？ Lilzhang@hhu.edu.cn Graph Theory/图论 5.1 对集（匹配） 设G是二部图(X,Y;E),如果X中每个顶点都被G的一个匹配M所饱和,即|M|=|X|,则称M为G的从X到Y的完全匹配. 举例说明其应用背景。 另一定义方式： 顶点染色与独立集之间的关系？ Lilzhang@hhu.edu.cn Graph Theory/图论