【作者】 方剑英；

【导师】 王迪吉； 杜智华；

【作者基本信息】 新疆师范大学 ， 基础数学， 2004， 硕士

【摘要】 排课表问题是众多安排问题中较为复杂的，它本质上是一个时间表问题。国内外的许多学者对它进行了研究和讨论，在某些限制条件下，可以表述为二部图的边着色(匹配)问题，但通常比着色问题复杂。排课表问题涉及到的因素很多：教室可分单班、多媒体、合堂教室；课程可分为单班、多媒体、合堂课；教师上课也可分为单班上课或多班的集体课。针对这种复杂情况，本文使用图论方法对高校排课问题抽象出一个统一的课表超图模型，并对其进行了理论研究和阐述，使之成为图论中一个确定的问题。说明要排出一个合理课表就要对课表超图进行无关可行分解。并把课表超图的无关分解转化为一个图的点独立集问题，即图的色数问题。同时，判断课表超图的无关子集是否是独立可行子集转化为求偶图G=(X，Y)的饱和X的匹配问题。在一些合理的条件下，我们给出了排课问题可解的充要条件以及确定超图的算法和课表超图无关可行分解的图论算法。结合某系的实际情况，利用这两个算法和数据结构的有关知识依步骤排出一张合理的课表。在文章的最后我们对课表超图的图论算法进行设计与分析，并得出该问题是一个NP难问题。更多还原

【Abstract】 The arranging of curriculum schedule is one of relatively complicated problem in multitudinous arrangement problems; in essential it is a timetable problem. A lot of experts and investigators who are domestic and overseas give researches and discusses about it, it can be expressed as a bipartite graph edges coloring (matching) problem under a certain constraints condition. But it is usually much more complicated than coloring problem, because a number of factor must be considered about curriculum schedule arrangement problem, the classroom may be divided into single class and multi-medium and collective class; the curriculum may be divided into single course and multi-medium course and collective course; A teacher may go to class singly or collectively. Aiming at this complicated situation, the paper gives abstractly a curriculum schedule hypergraph model to the timetable problem of a university by making use of the relevant knowledge of Graph Theory, at the same, it also gives a theoretical research and elaborates to the problem of the curriculum schedule arranging, making it become certain problem. It explains that arranging a reasonable curriculum schedule is the edge division that is non-relevant and viable about the curriculum schedule hypergraph; it turns the edge non-relevant division of the curriculum schedule hypergraph into a graph vertex independent set problem, which is called graph chromatic number problem. Moreover, whether the edge non-relevant division of the curriculum schedule hypergraph is a independent and viable subset turns into a matching problem of a saturated X in a bipartite graph G= (X, Y) .Under some reasonable condition, we give necessary and sufficient condition of resolving the problem of curriculum schedule arranging and a hypergraph constructing algorithm and the Graph Theory algorithm of the edge non-relevant and viable division of a curriculum schedule hypergraph. By the terms of the actual circumstance, it arranges a curriculum schedule of some department in our school by applying the two algorithms and relevant information of data structures. In the last, the paper designs and analyses the Graph Theory algorithm and drives a conclusion that the problem of the arranging of curriculum schedule is NP- hard problem.更多还原