Theory And Algorithm For The Problem Of Curriculum Schedule Arranging

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.