1 § 6.3 染色应用举例 一、排课表问题 —— 求二部图的正常 )(Gχ′ 边染色 1. 问题 ： 有 m 位教师 m xxx ,,, 21 L ， n 个班级 n yyy ,,, 21 L 。教师 x i 每周需要给班级 y j 上 p ij 次（节）课。要求制订一张周课时尽可能少的课程表。 2. 图论模型 ：构造二部图 ),( YXG = ，其中 X＝ { m xxx ,,, 21 L }， Y＝ { n yyy ,,, 21 L }， 顶点 i x 与 j y 之间连 ij p 条边。一个课时的安排方案对应与二部图 G 的一个匹配。 排课表问题等价于：将 E(G)划分成一些匹配，使得匹配的数目尽可能地少。 按 )(Gχ′ 的定义，这个最小的数目便是 )(Gχ′ 。由定理 6.2.1， )() GG ?=′（χ 。因此， 排课表问题等价于：求二部图 G 的边正常 )(G? 染色。 3. 求二部图 ),( YXG = 的边正常 )(G? 染色的算法 null 预处理： （ 1）给 G 添加必要的顶点使得 |||| YX = ； （ 2）给 G 添加必要的边使得 G 成为 )(G? 正则二部图，记为 * G 。 null 算法思想：反复运用匈牙利算法求 * G 的完美匹配。 由第 3 章 K?nig 定理（ 推论 3.3.3） ， * G 存在完美匹配。每求出 * G 的一个完美匹配， 给这个完美匹配的边赋以一种颜色。因共可求得 )(G? 个边不重的完美匹配（推论 3.3.3） ， 故可得 * G （从而 G）的边正常 )(G? 染色。 null 算法 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)( ** 0 i G Xx G xdxd i ∈ = ， )(min)( ** 0 i G Yy G ydyd i ∈ = ，令 00 ** : yxGG += ，转第 1 步。 第 3 步：任取 * G 的一个匹配 M。 2 第 4 步：若 X 已 M 饱和，转第 7 步；否则取 X 中一个 M 不饱和点 u，置 }{: uS = ， φ=:T 。 第 5 步：在 TSN \)( 中取一点 y. 第 6 步：若 y 是 M 饱和的，则存在 Myz∈ ，置 }{: zSS U= ， }{: yTT U= ，转第 5 步； 否则，存在一条 M 可扩路 P ),( yu ，置 )(: PEMM ⊕= ，转第 4 步。 第 7 步：若 ?=k ，则停止；否则，令 1: += kk ， MGG \: ** = ，转第 3 步。 因匈牙利算法的时间复杂性为 |)||(| EXO ? ，而预处理的加边循环不超过 ??|| X 次， 故该算法是多项式时间算法。 4. 带有约束的排课表问题 设学校每周有 l 阶课，安排在一张有 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 ，且 NMNM UU =′′ 。 定理 6.3.1 若图 G 是一个二部图，且 pG ≤? )( ，则 G 中存在 p 个无公共边的匹配 p MMM L,, 21 ，使得 p MMME ULUU 21 = ，且对每个 ),,2,1( pii L= 均有 ? ? ? ? ? ? ≤≤ ? ? ? ? ? ? p G M p G i )( || )( εε 。 证明： 因图 G是二部图， 故由本章定理 6.2.1， 边集 )(GE 可划分为 ? 个匹配 ? ′′′ MMM ,,, 21 L ， 因而对任何 )(Gp ?≥ ， G 中存在 p 个无公共边的匹配 ,,,, 21 ? ′′′ MMM L p MM ′′ +? ,, 1 L （其 中 φ=′==′ +? p MM L 1 ） ，使得 U p i i MGE 1 )( = ′= 。对这些匹配反复运用引理，即可得到满足 定理要求的匹配。证毕。 这个定理对前述带约束排课表问题给出了肯定回答。 同时也给出了求所需教室数最少的 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 ，故课表至少需 4 课时。 执行算法 A 得 G 的 4 个边不交的匹配（如图 2） 。相应的一个 4 课时课表如下： 教师 课时 1 2 3 4 x 1 y 1 y 1 y 3 y 4 x 2 y 2 y 4 x 3 y 3 y 4 y 2 x 4 y 4 y 5 按这张课表安排，需 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 的操作。一张只需 3 个教室的 4 课时课表如下： 教师 课时 1 2 3 4 x 1 y 1 y 1 y 3 y 4 x 2 y 4 y 2 x 3 y 3 y 4 y 2 x 4 y 5 y 4 x 4 x 3 x 2 x 1 y 1 y 2 y 3 y 4 y 5 x 4 x 3 x 2 x 1 y1 y 2 y 3 y 4 y 5 4 二、点染色的应用及正常 )(Gχ 点染色的求法 1．考试安排问题 某校有 n 门选修课 n LLL ,,, 21 L 需进行期末考试， 同一个学生不能在同一天里参加两门 或两门以上课程的考试。试问：该校的期末考试至少需要几天？如何安排？ 图论模型：构造图 G＝ (V, E)如下： =)(GV { n LLL ,,, 21 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 ∈ 当且仅当发 射台 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 不能放在同一仓库中。 若干制品可放在同一仓库当且仅当它们在 G 中对应的顶点课染同一种色。可见给这些 产品分配仓库相当于对 G 进行正常点染色。所需的最少仓库数即为 G 的点色数 )(Gχ 。问 题化为：求图 G 的正常 )(Gχ 点染色。 求任意图的正常 )(Gχ 点染色是一个 NPC 问题，目前没有多项式时间精确算法。仅有 一些适用于小规模问题的非多项式时间算法和近似比无界的多项式时间近似算法。 4. 求图 G 的色数 )(Gχ 及正常 )(Gχ 点染色的算法 null 添边粘合法 5 添边粘合操作：给定图 G＝ (V, E)，设 )(, GVvu ∈ ，且 u,v 在 G 中互不相邻，则 （ 1） 给 G 添加边 uv，得图 G′；－添边操作 （ 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 不是完全图，则可取两个不相邻顶点 u,v，对 G 进行添边操作 和粘合操作，反复进行这个过程，直至获得完全图为止。设最终得到的阶数最小的完全图为 m K ，则 mG =)(χ 。对该完全图进行正常点 m 染色，并进行反向操作便可得图 G 的正常点 m 染色。 例： 3)( =Gχ u v u v u v G G’ G” G 6 null 规范染色法（极大独立集法） 设 },,,{ 21 k VVV L=? 是 G 点 k 染色。若 1 V 是 G 的极大独立集， 2 V 是 1 \ VG 的极大独 立集， 3 V 是 )(21 VVG U 的极大独立集，一般地， i V 是 U 1 1 ? = i j j VG 的极大独立集 （ ki L,3,2= ） ，则称 ? 是图 G 的 规范 k 染色 （ canonical k-colouring） . 定理 6.3.3 图 G 是顶点可 k 正常染色的当且仅当 G 存在规范 k 染色。 证明：充分性是显然的。 必要性： 设 },,,{ 21 k VVV L 是图 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 VVV L 。然后考虑 )1( 2 V 。若它不是 )1( 1 \ VG 的极大独立 集，则可从 )()1( 2 )1( 1 VVV U 中调一些顶点进入 )1( 2 V ，将其扩充成极大独立集 )2( 2 V ， )1()1( 3 )1( 2 ,,, k VVV L 变成 )2()2( 3 )2( 2 ,,, k VVV L 。如此类推，最后可得图 G 的规范 k 染色 )()2( 2 )1( 1 ,,, k k VVV L 。 证毕。 规范染色法基本思想： 求 G 的极大点独立集 1 V ，其顶点染上色 1；再求 1 \ VG 的极大点独立 集 2 V ，将其顶点染上色 2；如此类推，直至染完所有顶点。 注： （ 1）这是一种贪婪算法。 （ 2）规范 k 染色一般不唯一。 （ 3）用这个算法只能得到一种正常顶点染色。规范染色所用的颜色数未必就是 )(Gχ 。 （ 4）由定理， G 可用 )(Gχ 种颜色正常顶点染色，则必存在 )(Gχ 规范染色。因此只 需从一切规范染色中选出颜色数最少者，即可求得 )(Gχ 。 （ 5）由于需要求出所有规范染色才能确定出 )(Gχ ，因此该算法不是多项式时间算法， 它只适用于阶数较小的图。 例： G 的一个极大独立集 },,{ 1 cgaV = ， 1 \ VG 的一个极大独立集 },,{ 2 fdbV = ， )(21 VVG U 的一个极大独立集为 }{ 3 eV = 。故 G 可正常 3 顶点染色， 3)( ≤Gχ 。另一方 面， G 含有 3 K ，因此正常顶点染色至少需要 3 种颜色。从而 3)( =Gχ 。 a c d bf e g 7 null 顺序染色法 思想：将图 G 的顶点排一个顺序 n vvv ,,, 21 L 。先给顶点 1 v 染上色 1 c 。对顶点 2 v ，从 颜色集合 },,,{ 321 Lccc 中选取未被 2 v 的邻点使用的编号最小的色来染它。一般地，对顶点 i v ，从颜色集合 },,,{ 321 Lccc 中选取未被 i v 的邻点使用的编号最小的色给其染色， ni ,,2,1 L= 。 算法： 第 1 步：令 1:=i 。 第 2 步：令 1:=c 。 第 3 步：若对所有 )( i vNy∈ ，颜色 c 未染 y，则令 c 染 i v ，转第 5 步。 第 4 步： 1: += cc ，转第 3 步。 第 5 步：若 ni < ，则 1: += ii ，转第 2 步；否则，停止。 例： 注： （ 1）顺序染色法是多项式时间算法，时间复杂性为 )( 2 nO 。 （ 2）顺序染色法是一种近似算法，其算法结果（所用颜色数）与顶点的标号顺序有密切关 系。比如，对完全二部图 ),( , YXK nn = ，若顶点标号顺序为 nn yyyxxx ,,,,,,, 2121 LL ， 则算法结果只用两种颜色，是最优解。但若顶点顺序为 nn yxyxyx ,,,,,, 2211 L ，则算法结 果需 n 种颜色。算法近似比 2 ~ * n c c = ，无界！ null Powell 算法 第 1 步：将图 G 的顶点按度数递减的顺序排列，设为 n vvv ,,, 21 L 。 第 2 步：用第 1 种颜色给 1 v 染色，令 }{: 1 vV c = ， 1:=i 。 第 3 步：若存在与 c V 中所有点都不相邻的顶点，则找出第一个与 c V 中所有点都不相邻 的顶点 v，转下步；否则 1: += ii ，转第 5 步。 第 4 步：给 v 染上第 i 种色，令 }{: vVV cc U= ，转第 3 步。 第 5 步：用第 i 种色给尚未染色的编号最小的顶点 v 染色，令 }{: vV c = ，转第 3 步。 第 6 步：所有顶点都得到染色时，停止。 v 1 v 3 v 4 v 2 v 6 v 5 v 7 8 例： 课外阅读文献 1. E.C.Sewell. An Improved algorithm for exact graph coloring. “Cliques, Coloring and Satisfiability”. (Series in Discrete Mathematics and Theoretical Computer Science), vol. 26 (1996). 2. C. Nomikos, A. Pagourtzis and S. Zachos. Routing and path multicoloring. Information Processing Letters, 80(2001) 249-256. 3. D. de Werra, Lausanne, Heuristics for graph coloring. Computing Supplementum, 7(1990) 191-208. 4. I. Holyer. The NP-Completeness of edge-coloring. SIAM J. Computing, 10: 4(1981) 718-720. 5. O.V. Borodin and A.V. Kostochka. List edge and list total colorings of multigraphs. Journal of Combinatorial Theory, (Ser. B), 71(1997), 184-204. 6. Xiao Zhou, H. Suzuki and T. Nishizeki. An NC parallel algorithm for edge-coloring series-parallel multigraphs. Journal of Algorithms, 23(1997) 359-374. v 7 v 6 v 5 v 2 v 3 v 4 v 1