二部图的边染色算法
:专业::
1
排课表
问题 有m位教师x1,x2,x3,...,xm,n个班级y1,y2,y3,...,yn.教师xi每周需要给班级yj上pij次课.要求
制订一张周课时尽可能少的
课程表.
2
图论模型
我们先构造二部图G=(X,Y),其中X={x1,x2,x3,...,xm},Lkm′,Y={y1,y2,y3,...,yn},表示
有n个班级,教师xi每周需要给班级yj上pij次课,则在顶点xi与yj之间连pij条边.根据匹配的定义,一个课时的安排
方案正好对应于二部图G的一个匹配.排课表问题就等价于:将E(G)划分成一些边不交的匹配,使得匹配的数目尽可能的少.按图G的边染色数χ(G)的定义,这个最少的数目便是χ(G).由定理:设G为二部图,则χ(G)=?(G).因此,排课表问题就等价与:求二部图G的边正常?(G)染色.
3
求二部图G=(X,Y)的边正常?(G)染色的算法
先我们来给出算法思想:给G添加必要的顶点使得|X|=|Y|,再添加必要的边使得G成为?(G)
的正则二部图,经过以上
工作后所得到的图记作G?,然后反复利用匈牙利算法求G?的完美匹配.由定理:设G是k正则二部图,则G有k个边不交的完美匹配.则G?存在?(G)个彼此边不交的完美匹配.当我们用匈牙利算法每求出G?的一个完美匹配,便可用一种颜色给这个完美匹配的边染色,故可得到G?的边正常?(G)染色,从而得到G的边正常?(G)染色.二部图边染色算法:求二部图的边正常?(G)染色(求二部图的?(G)个彼此无公共边的匹配).输入:二部图G=(X,Y)输出:G的边正常?(G)染色(?(G)个彼此无公共边的匹配)1
第0步:添加顶点使得|X|=|Y|,所得图记为G?.第1步:若?(G?)=δ(G?),令k=1,转第3步;否则,转第2步.第2步:取x0∈X,y0∈Y,使得dG?(x0)=mindG?(xi),dG?(y0)=mindG?(yi),令G?:=G?+x0y0,转第1步.第3步:任取G?的一个匹配M.第4步:若X已经饱和M,则输出当前的完美匹配,转第7步;否则取X中一个M不饱和点u,置S:={u},T:=φ.第5步:在N(S)\T中取一点y.第6步:若y是M饱和的,则存在yz∈M,置S:=S∪{Z},T:=T∪{y},转第5步;否则,存在一条M可扩路P(u,y),置M:=M⊕E(P),转第4步.第7步:若k=?,则停止;否则,令k:=k+1,G?:=G?\M,转第3步.设|X|≥|Y|,第1步和第2步的加边循环不超过|X|×?次.算法的核心是循环执行第3步到第6步使用匈牙利算法反复求完美匹配(?个).我们如果知道用匈牙利算法求二部图G的一个饱和X的一个匹配的复杂度,就能知道次算法第3步到第6步的复杂度了,现在我们先研究匈牙利算法求二部图G的一个饱和X的一个匹配的复杂度.用匈牙利算法求二部图G的一个饱和X的一个匹配:算法思想:从二部图G=(X,Y)的任何一个匹配M开始.若M饱和X,则算法结束.若M不饱和X,在X中选择一个M不饱和点x.若G中不存在以x为起点的M增广路,则可找到与x由M交错路相连的顶点集合A,而S=A∩X满足|N(S)|<|S|(见Hall定理的证明),此时由Hall定理,G不存在饱和X的匹配.若存在以x为起点的M增广路P,则由Berge定理知M不是最大匹配,且M=M⊕E(P)是比M更大的匹配,用M代替M.反复进行上述过程,使匹配的边数逐步增加,直至到|X|条匹配边为止.算法步骤:输入:二部图G=(X,Y).输出:G的一个饱和X的匹配.第0步:任取G的一个匹配M.第1步:若M饱和X,则停止,输出M;否则,取X中一个M非饱和点x,令S:={x},T:=φ.第2步:若N(S)?T,则停止,G中不存在饱和X的匹配;否则,取y∈N(S)?T.第3步:若y是M饱和的,设yz∈M,令S:=S∪{z},T:=T∪y,转第2步;否则,获得一条M可扩路P(u,y),令M:=M⊕E(P),转第1步.
2
注:按照算法过程,进入T中的点必与S中某点相邻,故总有N(S)?T,因此,第2步中判断N(S)?T可改成判断N(S)=T.匈牙利算法的正确性由Berge定理和Hall定理可知.匈牙利算法是多项式时间算法.现在我们来计算它的复杂度.算法每找到一条增广路更新一次匹配,匹配边增加一条,故最多执行n次增广路的循环.算法每找