摘要图的染色问题是图论中的基本问题,现实生活中我们常用图的染色解决排课表问题、最短路径、最优安排、抽屉原理等问题。图的边染色是图的染色中最基本的染色方法之一,即将图分解为互不相交的边独立集的并的方法。
随着社会的发展,各个学科对排课表问题的研究加深,单一智能算法的不足使得排课表问题未能完全解决,大学排课表仍是现今社会关注的问题。本文首先介绍边染色和排课表问题,然后使用边染色对排课表问题进行应用,最后运用边染色解决教室无限制和教室有限制的排课问题的算法,使所得算法能解决教师、学生与教室的排课冲突,通过运行程序解决简单的排课表问题,从而使算法得到应用。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
吹冰、致谢    20
七、主要参考文献    21
八、附录    22
附录1    22
附录2    23
附录3    24
一、绪论
1.1课题的目的和意义

图论是数学的一个分支,它以图为研究对象。图的染色问题是图论中的基本问题,染色方法是一种将题目研究对象分类的形象化方法,通过将问题中的对象适当染色,我们可以更形象地观察分析出其中所蕴含的关系,再经过一定的逻辑推理,便能得出问题的答案。染色问题在实际生活中如最短路径、最优安排、抽屉原理也得到运用。因此对染色问题的深入研究有助于这些实际工程问题的解决,也对其他学科的发展有推动作用。
上一篇:整函数的阶型与零点+文献综述
下一篇:线性回归中最小二乘估计的改进

微课在中学数学素质教育中的应用

中学数学教学中的模型思想与应用

凯勒流形的复结构与代数结构研究

可展曲面的判定构造及其应用

Dirichlet判别法与Abel判别法的探究

一维Schroedinger算子只有离散谱的条件

螺纹钢期货交易中几个影...

从政策角度谈黑龙江對俄...

STC89C52单片机NRF24L01的无线病房呼叫系统设计

酵母菌发酵生产天然香料...

压疮高危人群的标准化中...

提高教育质量,构建大學生...

AES算法GPU协处理下分组加...

基于Joomla平台的计算机学院网站设计与开发

浅谈高校行政管理人员的...

上海居民的社会参与研究

浅论职工思想政治工作茬...