您的位置： 无忧文档所有分类高等教育理学 算法课程论文

算法课程论文

上研究生算法课时写的课程论文

二部图的边染色算法

学号：专业：

姓名：

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

第1页

你可能喜欢

  • 算法设计论文
  • 贪心算法论文
  • spss课程论文
  • 数据挖掘课程论文
  • 传播学课程论文
  • 文献检索课程论文
  • 测试技术课程论文
  • 英语课程论文

算法课程论文的相关文档搜索

算法课程论文相关文档

最新文档

返回顶部