-
摘要图的染色问题是图论中的基本问题，现实生活中我们常用图的染色解决排课表问题、最短路径、最优安排、抽屉原理等问题。图的边染色是图的染色中最基本的染色方法之一，即将图分解为互不相交的边独立集的并的方法。
- 上一篇：整函数的阶型与零点+文献综述
- 下一篇：线性回归中最小二乘估计的改进
随着社会的发展，各个学科对排课表问题的研究加深，单一智能算法的不足使得排课表问题未能完全解决，大学排课表仍是现今社会关注的问题。本文首先介绍边染色和排课表问题，然后使用边染色对排课表问题进行应用，最后运用边染色解决教室无限制和教室有限制的排课问题的算法，使所得算法能解决教师、学生与教室的排课冲突，通过运行程序解决简单的排课表问题，从而使算法得到应用。6661
关键词：边染色；最优安排；排课表问题；算法
Abstract
Coloring is the basic problem of graph theory,we use coloring to solve the practical cases,such as curriculum schedule arrangement,the shortest route,best arrangement,drawer axiom and so on.Edge coloring is one of the basic way of graph coloring,which separates the graph into the combine of disjoint edge independent sets.
With society developed,every subject go deep into the research of curriculum schedule arrangement,but the shortage of single brainpower arithmetic make it cannot go any farther,the arrangement still holds the social attention.This paper introduce edge coloring and curriculum schedule at the beginning,then solve it with edge coloring,and apply the edge coloring to curriculum schedule arrangements with unlimited-class and limited -class,so that we can solve the problems with teachers,students and classrooms.At last,we run the program to solve the simple problem,so that the algorithm can be put to use.
Key words:edge coloring; best arrangement; curriculum schedule arrangement; algorithm
目录 1
摘要 2
Abstract 2
一、绪论 3
1.1课题的目的和意义 3
1.2国内外研究现状与发展趋势 3
1.3基本符号 4
1.4基本概念 4
1.5相关定理 5
二、边染色在排课表中的应用 5
2.1 边染色的介绍 5
2.2 排课表问题的介绍 6
2.2.1 排课表问题的背景介绍 6
2.2.2 排课表问题是一个NP完全问题 8
2.2.3 排课表中的基本原则 8
2.3 边染色在简单排课表中的应用 9
三、排课表问题的算法 12
3.1 教室不受限制的算法 12
3.2 教室有限的算法 13
四、算法的应用 14
4.1 教室无限制的算法的应用 14
4.2教室有限制的算法的应用 17
4.3实例应用 18
4.4算法探讨与其他问题 19
五、总结 20
751、致谢 20
七、主要参考文献 21
八、附录 22
附录1 22
附录2 23
附录3 24
一、绪论
1.1课题的目的和意义
图论是数学的一个分支，它以图为研究对象。图的染色问题是图论中的基本问题，染色方法是一种将题目研究对象分类的形象化方法，通过将问题中的对象适当染色，我们可以更形象地观察分析出其中所蕴含的关系，再经过一定的逻辑推理，便能得出问题的答案。染色问题在实际生活中如最短路径、最优安排、抽屉原理也得到运用。因此对染色问题的深入研究有助于这些实际工程问题的解决，也对其他学科的发展有推动作用。