图论讲义6染色应用

《图论讲义6染色应用》由会员分享，可在线阅读，更多相关《图论讲义6染色应用（8页珍藏版）》请在金锄头文库上搜索。

1、 1 6.3 染色应用举例染色应用举例 一、排课表问题 求二部图的正常一、排课表问题 求二部图的正常)(G边染色 边染色 1. 问题问题： 有 m 位教师 m xxx, 21 L，n 个班级 n yyy, 21 L。教师 xi每周需要给班级 yj上 pij次（节）课。要求制订一张周课时尽可能少的课程表。 2. 图论模型图论模型：构造二部图),(YXG=，其中 X m xxx, 21 L，Y n yyy, 21 L， 顶点 i x与 j y之间连 ij p条边。一个课时的安排方案对应与二部图 G 的一个匹配。 排课表问题等价于：将 E(G)划分成一些匹配，使得匹配的数目尽可能地少。 按)(G的定

2、义，这个最小的数目便是)(G。由定理 6.2.1，)()GG= （ 。因此， 排课表问题等价于：求二部图 G 的边正常)(G染色。 3. 求二部图求二部图),(YXG=的边正常的边正常)(G染色的算法染色的算法 ? 预处理： （1）给 G 添加必要的顶点使得|YX=； （2）给 G 添加必要的边使得 G 成为)(G正则二部图，记为 * G。 ? 算法思想：反复运用匈牙利算法求 * G的完美匹配。 由第 3 章 Knig 定理（定理（推论 3.3.3） ， * G存在完美匹配。每求出 * G的一个完美匹配， 给这个完美匹配的边赋以一种颜色。因共可求得)(G个边不重的完美匹配（推论 3.3.3）

3、， 故可得 * G（从而 G）的边正常)(G染色。 ? 算法 A：求二部图的边正常)(G染色（求二部图的)(G个边不交的匹配） 。 输入：二部图 G=(X,Y) 输出：G 的边正常)(G染色（)(G个边不交的匹配） 第 0 步：添加顶点使得|X|=|Y|，所得图记为 * G。 第 1 步：若)()( * GG=，令1=k，转第 3 步；否则，转第 2 步。 第 2 步：取Xx 0 ，Yy 0 ，使得)(min)( * 0i G Xx G xdxd i =，)(min)( * 0i G Yy G ydyd i =，令 00 * :yxGG+=，转第 1 步。 第 3 步：任取 * G的一个匹配

4、M。 2 第 4 步：若 X 已 M 饱和，转第 7 步； 否则取 X 中一个 M 不饱和点 u，置:uS =，=:T。 第 5 步：在TSN)(中取一点 y. 第 6 步：若 y 是 M 饱和的，则存在Myz，置:zSSU=，:yTTU=，转第 5 步； 否则，存在一条 M 可扩路 P),(yu，置)(:PEMM=，转第 4 步。 第 7 步：若=k，则停止；否则，令1:+= kk，MGG: * =，转第 3 步。 因匈牙利算法的时间复杂性为|)|(|EXO，而预处理的加边循环不超过 | X次， 故该算法是多项式时间算法。 4. 带有约束的排课表问题带有约束的排课表问题 设学校每周有 l 阶

5、课，安排在一张有 p 节课时的课表中（前面的方法求得一个节课时 的课表） 。 这样， 平均每一课时要上 p l 节课。 因此需要 p l 间教室。 比如，510=l，20=p， 则需要26 20 510 = = p l 间教室。 问题：问题： 可否在一张有 p 节课时的课表里安排 l 节课， 使得在一节课时内至多用 p l 间教室？ 下面的引理见第 3 章习题。 引理引理 6.3.1 设 M 和 N 是图 G 的两个无公共边的匹配，并且|NM，则存在 G 的无公共 边的匹配 M 和 N ，使得1|=MM，1|+=NN，且NMNMUU=。 定理定理 6.3.1 若图 G 是一个二部图，且pG )

6、(，则 G 中存在 p 个无公共边的匹配 p MMML, 21 ，使得 p MMMEULUU 21 =，且对每个), 2 , 1(piiL=均有 p G M p G i )( | )( 。 证明： 因图G是二部图， 故由本章定理6.2.1， 边集)(GE可划分为个匹配 MMM, 21 L， 因而对任何)(Gp，G 中存在 p 个无公共边的匹配, 21 MMML p MM+ , 1 L（其 中=+ p MML 1 ） ，使得 U p i i MGE 1 )( = =。对这些匹配反复运用引理，即可得到满足 定理要求的匹配。证毕。 这个定理对前述带约束排课表问题给出了肯定回答。 同时也给出了求所需教

7、室数最少的 3 p 课时课表的方法：先按算法 A 求出相应二部图的一个正常)(G边染色，然后反复运用引 理 6.3.1 对其进行调整，最终使得染不同颜色的两个边集所含边数至多相差 1。 例例 6.3.1 设有 4 个教师和 5 个班级，教学要求用矩阵)( ij tT =表示如下： = 11000 01110 01010 01102 4 3 2 1 54321 x x x x yyyyy T 问： （1）课表至少需要几课时？ （2）按算法 A 给出一个课时数最少的课表。 （3）在课时数最少的前提下，给出需教室数最少的课表方案。 解：构造二部图如下图 1： 图 1 图 2 由于4)(= G，故课表

8、至少需 4 课时。 执行算法 A 得 G 的 4 个边不交的匹配（如图 2） 。相应的一个 4 课时课表如下： 教师 课时 1 2 3 4 x1 y1 y1 y3 y4 x2 y2 y4 x3 y3 y4 y2 x4 y4 y5 按这张课表安排，需 4 个教室。但因11)(=G，3 4 11 = = p ，由定理 6.3.1，可 排出一张只需 3 个教室的 4 课时课表。事实上，将教师 4 x在第 1 课时的课调到第 3 课时而 将教师 2 x在第 3 课时的课与第 1 课时对调即可。从二部图的匹配上来看，是将第 1 课时和 第 3 课时对应的匹配施行了一次引理 6.3.1 的操作。一张只需

9、3 个教室的 4 课时课表如下： 教师 课时 1 2 3 4 x1 y1 y1 y3 y4 x2 y4 y2 x3 y3 y4 y2 x4 y5 y4 x4 x3 x2 x1y1 y2 y3 y4 y5 x4 x3 x2 x1y1 y2 y3 y4 y5 4 二、点染色的应用及正常二、点染色的应用及正常)(G点染色的求法 点染色的求法 1考试安排问题考试安排问题 某校有 n 门选修课 n LLL, 21 L需进行期末考试， 同一个学生不能在同一天里参加两门 或两门以上课程的考试。试问：该校的期末考试至少需要几天？如何安排？ 图论模型：构造图 G(V, E)如下：=)(GV n LLL, 21

10、L，)(GELL ji 当且仅当课 程 i L和 j L被同一学生选修。 将同一天中的考试课程在 G 中对应的顶点染同一种色，则考试安排相当于对 G 进行顶 点正常染色。所求最少天数即为 G 的点色数)(G。问题化为：求图 G 的正常)(G点染 色。 2电视频道分配问题电视频道分配问题 某地区有年家电视发射台 n TTT, 21 L，主管部门给每家电视台分配一个发射频道。为 排除同频干扰，使用相同频道的发射台之间相距必须大于一定的距离 d。试问：该地区至少 需要多少个频道？如何分配？ 图论模型：构造图 G(V, E)如下：=)(GV n TTT, 21 L，)(GETT ji 当且仅当发 射台

11、 i T和 j T的距离不超过 d。 考虑 G 图的正常点染色。易见染同一种色的顶点课分配给同一频道。反之，按要求分 配一个频道，相当于给 G 中相应的顶点染同一种色。因此，频道分配相当于对 G 进行顶点 正常染色。所求最少频道数即为点色数)(G。问题化为：求图 G 的正常)(G点染色。 3. 储藏问题储藏问题 某公司生产 n 种化学品 n CCC, 21 L，其中某些制品不能存放在同一个仓库中。问至 少需要多少个仓库？如何分配存放？ 图论模型：构造图 G(V, E)如下：=)(GV n CCC, 21 L，)(GECC ji 当且仅当 制品 i C和 j C不能放在同一仓库中。 若干制品可放

12、在同一仓库当且仅当它们在 G 中对应的顶点课染同一种色。可见给这些 产品分配仓库相当于对 G 进行正常点染色。所需的最少仓库数即为 G 的点色数)(G。问 题化为：求图 G 的正常)(G点染色。 求任意图的正常)(G点染色是一个 NPC 问题，目前没有多项式时间精确算法。仅有 一些适用于小规模问题的非多项式时间算法和近似比无界的多项式时间近似算法。 4. 求图求图 G 的色数的色数)(G及正常及正常)(G点染色的算法点染色的算法 ? 添边粘合法添边粘合法 5 添边粘合操作：给定图 G(V, E)，设)(,GVvu，且 u,v 在 G 中互不相邻，则 （1） 给 G 添加边 uv，得图 G ；添

13、边操作 （2） 将 u,v 两点粘合为一点，并去掉所得的重边，得图 G 。粘合操作 例如：例如： 定理定理 6.3.2 )(),(min)(GGG =。 证明：考虑图 G 的所有可能的正常点染色。u, v 的染色有两种可能：u 与 v 同色，或 u 与 v 异色。G 的使 u 与 v 染同色的正常点染色与 G 的正常点染色一一对应，而 G 的使 u 与 v 染异色的正常点染色与 G 的正常点染色一一对应。因此)(),(min)(GGG =。 证毕。 由此可知，对于给定的图 G，若 G 是一个阶完全图，则=)(G。此时给 G 的每个 顶点一个不同的色即可。若 G 不是完全图，则可取两个不相邻顶点

14、 u,v，对 G 进行添边操作 和粘合操作，反复进行这个过程，直至获得完全图为止。设最终得到的阶数最小的完全图为 m K，则mG =)(。对该完全图进行正常点 m 染色，并进行反向操作便可得图 G 的正常点 m 染色。 例：例： 3)(=G u v u v u v G G G” G 6 ? 规范染色法（极大独立集法）规范染色法（极大独立集法） 设, 21k VVVL=是 G 点 k 染色。若 1 V是 G 的极大独立集， 2 V是 1 VG的极大独 立集， 3 V是)( 21 VVGU的极大独立集，一般地， i V是 U 1 1 = i j j VG的极大独立集 （kiL, 3 , 2=） ，

15、则称是图 G 的规范 k 染色（canonical k-colouring）. 定理定理 6.3.3 图 G 是顶点可 k 正常染色的当且仅当 G 存在规范 k 染色。 证明：充分性是显然的。 必要性： 设, 21k VVVL是图 G 的一个顶点正常 k 染色， 则 k VVV, 21 L都是 G 的独立集。 若 1 V不是 G 的极大独立集，则可从 1 VV中调一些顶点进入 1 V，使 1 V扩大成极大独立集 )1( 1 V， k VVV, 32 L变成 )1()1( 3 )1( 2 , k VVVL。然后考虑 )1( 2 V。若它不是 )1( 1 VG的极大独立 集，则可从)( )1( 2 )1( 1 VVVU中调一些顶点进入 )1( 2 V，将其扩充成极大独立集 )2( 2 V， )1()1( 3 )1( 2 , k VVVL变成 )2()2( 3 )2( 2 , k VVVL。如此类推，最后可得图 G 的规范 k 染色 )(