毕业论文

打赏
当前位置: 毕业论文 > 数学论文 >

图的染色问题在排课表中的应用+文献综述(2)

时间:2017-03-19 15:05来源:毕业论文
课表安排是一项十分繁重而复杂的工作,它涉及几十甚至上百个专业、几百门课程、几百名教师的合理安排。然而教室、实验室等资源又有限,更给排课增


    课表安排是一项十分繁重而复杂的工作,它涉及几十甚至上百个专业、几百门课程、几百名教师的合理安排。然而教室、实验室等资源又有限,更给排课增加了难度。在整个排课过程中,自始至终充满了冲突,其中包括上课班级、所开课程、任课教师、上课时间、上课地点等5个方面在排列组合中所发生的冲突与矛盾。班级多、课程门类多、教师少、教室少是发生冲突和矛盾的重要因素。为了减轻劳动强度,提高工作效率,我们考虑用图论中的染色来解决排课问题。
1.2国内外研究现状与发展趋势
1.3基本符号

 ——表示图 的最大度
 ——表示完全图
 ——表示二部图
 ——表示完全二部图
 ——表示图 中顶点 的度

1.4基本概念

设 是一个图,我们用 , , 和 (或者用简单的 , , 和 )分别表示图 的顶点集合,边集合,最大度和最小度。
顶点的度:在图 中与顶点 相关联的边数(每个环计算二次),称为顶点 的度,记为 。
图 的最大度: ,记为 。
简单图:如果一个图 没有环和多重边,那么称 为简单图。
完全图:每对顶点之间都恰有一条边的简单图。
二部图:若图 的顶点集可划分为两个非空子集 和 ,使得任一条边都有一个端点在 中,另一个端点在 中,则称 为二部图(或偶图),记为 。
边染色:无环图 的一个 边正常染色是指 种颜色1,2,… ,对于 的各边的一个分配,使得相邻的两条边染以不同的颜色。若 有 边正常染色,则称 是 边可染色的。
边色数: 为 边可染色的最小值 ,记为 ,若 ,则称 是 边色的。因此图 的一个 边染色实际等价于图 的边集合 划分为 个边不交的对集。
关联矩阵:设 的顶点集和边集分别为 , 用 表示顶点 与边 关联的次数(0,1或2),称矩阵 为 的关联矩阵。
邻接矩阵:设图 的顶点集为 ,用 表示 中 与 之间的边数。称矩阵 为 的邻接矩阵。

1.5相关定理

定理1[1]:若 是二分图, 。则存在 个互不相交的对集 ,使得  并且对每个
定理2[2]:设 是二部图,则 。
定理3[3~4](Vizing定理):对于简单图 ,有  ,其中 为 的最大度点。
引理4:设与 是图 的两个不相交匹配,且| |>| |,则存在图 #的不相交匹配 与 ,使| |=| |-1,| |=| |+1,   =   
定理5:设 是二部图, ,则存在 的 不相交匹配 ,…,
    
并且对于 有
 
Koning定理:在0-1矩阵中,1的最大独立集合最小覆盖包含的元素个数相同,等价地,二分图中的最大匹配数等于这个图中的最小点覆盖数。

二、边染色在排课表中的应用

用染色解决排课表问题,传统的解法是运用边染色对该问题进行求解。在解决排课表问题前,我们先简单的介绍一下边染色以及其经常求解的简单现实模型,并从中体会边染色的运用,使其运用到排课表问题中去。

2.1 边染色的介绍

无环图G的一个 着色是指 种颜色1,2,…, 对于G的各边的一个分配。若没有相邻的两条边有着相同的颜色,则称着色是正常的[5]。
换句话说,一个 边着色可以看做是 的一个分类( ),这里 (可能是空的)表示染有颜色 的 的子集,一个正常的 边着色就是每个 均为对集的 边着色( )。图1中的图有正常的4边着色
若 有正常的 边着色,则称 是 边可着色的。显然,每个无环图 是 边可着色的;并且若 是 边着色的,则对每个l> , 亦是l边可着色的。无环图 的边色数  ,则称 是 边色的。可以验证,图1没有正常的3边着色,因此该图是4边色的。 图的染色问题在排课表中的应用+文献综述(2):http://www.751com.cn/shuxue/lunwen_4284.html
------分隔线----------------------------
推荐内容