资源描述：
《§6.3染色应用举例》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、§6.3染色应用举例一、排课表问题——求二部图的正常χ′(G)边染色1.问题：有m位教师x1,x2,L,xm，n个班级y1,y2,L,yn。教师xi每周需要给班级yj上pij次（节）课。要求制订一张周课时尽可能少的课程表。2.图论模型：构造二部图G=(X,Y)，其中X＝{x,x,L,x}，Y＝{y,y,L,y}，12m12n顶点x与y之间连p条边。一个课时的安排方案对应与二部图G的一个匹配。ijij排课表问题等价于：将E(G)划分成一些匹配，使得匹配的数目尽可能地少。按χ′(G)的定义，这个最小的数目便是χ′(G)。由定理6.2
2、.1，χ′（G)=∆(G)。因此，排课表问题等价于：求二部图G的边正常∆(G)染色。3.求二部图G=(X,Y)的边正常∆(G)染色的算法z预处理：（1）给G添加必要的顶点使得
3、X
4、=
5、Y
6、；*（2）给G添加必要的边使得G成为∆(G)正则二部图，记为G。*z算法思想：反复运用匈牙利算法求G的完美匹配。**由第3章König定理（推论3.3.3），G存在完美匹配。每求出G的一个完美匹配，给这个完美匹配的边赋以一种颜色。因共可求得∆(G)个边不重的完美匹配（推论3.3.3），*故可得G（从而G）的边正常∆(G)染色。z算法A：求二部图
7、的边正常∆(G)染色（求二部图的∆(G)个边不交的匹配）。输入：二部图G=(X,Y)输出：G的边正常∆(G)染色（∆(G)个边不交的匹配）*第0步：添加顶点使得
8、X
9、=
10、Y
11、，所得图记为G。**第1步：若∆(G)=δ(G)，令k=1，转第3步；否则，转第2步。第2步：取x0∈X，y0∈Y，使得dG*(x0)=minx∈XdG*(xi)，dG*(y0)=miny∈YdG*(yi)，令ii**G:=G+xy，转第1步。00*第3步：任取G的一个匹配M。1第4步：若X已M饱和，转第7步；否则取X中一个M不饱和点u，置S:={u}，T:
12、=φ。第5步：在N(S)T中取一点y.第6步：若y是M饱和的，则存在yz∈M，置S:=SU{z}，T:=TU{y}，转第5步；否则，存在一条M可扩路P(u,y)，置M:=M⊕E(P)，转第4步。**第7步：若k=∆，则停止；否则，令k:=k+1，G:=GM，转第3步。因匈牙利算法的时间复杂性为O(
13、X
14、⋅
15、E
16、)，而预处理的加边循环不超过
17、X
18、⋅∆次，故该算法是多项式时间算法。4.带有约束的排课表问题设学校每周有l阶课，安排在一张有p节课时的课表中（前面的方法求得一个∆节课时l⎡l⎤的课表）。这样，平均每一课时要上节课。因此
19、需要⎢⎥间教室。比如，l=510，p=20，p⎢p⎥⎡l⎤⎡510⎤则需要⎢⎥=⎢⎥=26间教室。⎢p⎥⎢20⎥⎡l⎤问题：可否在一张有p节课时的课表里安排l节课，使得在一节课时内至多用⎢⎥间教室？⎢p⎥下面的引理见第3章习题。引理6.3.1设M和N是图G的两个无公共边的匹配，并且
20、M
21、>
22、N
23、，则存在G的无公共边的匹配M′和N′，使得
24、M′
25、=
26、M
27、−1，
28、N′
29、=
30、N
31、+1，且M′UN′=MUN。定理6.3.1若图G是一个二部图，且∆(G)≤p，则G中存在p个无公共边的匹配M,M,LM，使得E=MUMULUM，且对每个i(i
32、=1,2,L,p)均有12p12p⎢ε(G)⎥⎡ε(G)⎤≤
33、M
34、≤。⎢⎥i⎢⎥⎣p⎦⎢p⎥证明：因图G是二部图，故由本章定理6.2.1，边集E(G)可划分为∆个匹配M′,M′,L,M′，12∆因而对任何p≥∆(G)，G中存在p个无公共边的匹配M′,M′,L,M′,M′,L,M′（其12∆∆+1pp中M∆′+1=L=M′p=φ），使得E(G)=UMi′。对这些匹配反复运用引理，即可得到满足i=1定理要求的匹配。证毕。这个定理对前述带约束排课表问题给出了肯定回答。同时也给出了求所需教室数最少的2p课时课表的方法：先按算法A求出相应
35、二部图的一个正常∆(G)边染色，然后反复运用引理6.3.1对其进行调整，最终使得染不同颜色的两个边集所含边数至多相差1。例6.3.1设有4个教师和5个班级，教学要求用矩阵T=(t)表示如下：ijyyyyy12345x1⎛20110⎞⎜⎟T=x2⎜01010⎟x⎜01110⎟3⎜⎟⎜⎟x4⎝00011⎠问：（1）课表至少需要几课时？（2）按算法A给出一个课时数最少的课表。（3）在课时数最少的前提下，给出需教室数最少的课表方案。解：构造二部图如下图1：x1y1x1y1x2y2x2y2x3y3x3y3x4y4x4y4y5y5图1图2由
36、于∆(G)=4，故课表至少需4课时。执行算法A得G的4个边不交的匹配（如图2）。相应的一个4课时课表如下：教师课时1234x1y1y1y3y4x2y2y4x3y3y4y2x4y4y5⎡ε⎤⎡11⎤按这张课表安排，需4个教室。但因ε(G)=11，⎢⎥=⎢⎥=3，由
