## Welch-Powell图的点染色在现实生活中的应用

Abstract
This paper mainly introduces a very important way of coloring -- vertex coloring. Nowadays graph theory has been used very widely. Vertex coloring has become the common method in solving many problems. It involves many fields, such as communication, physics, biology, management science and so on[1]. This paper mainly introduces the basic principle of vertex coloring and some basic algorithms, such as the Welch-Powell algorithm, the greedy algorithm, Backtracking algorithm[2] and so on. Finally I design a traffic lights system by using Welch-Powell algorithms and a simple courses arranging system by using the greedy algorithm.
Key Word: vertex coloring; Welch-Powell algorithm; the greedy algorithm
目   录

Abstract    2

1.1 课题的目的及意义    3
1.2 国内外研究现状与发展    4

1.3 文中符号说明    5
1.4 基本概念    6

2.1 相关定义    6
2.2 相关定理    7

3.1 Welch-Powell染色法(穷举法)    8
3.1.1 算法步骤[10]    8
3.1.2 举例说明    8
3.1.3 算法的优缺点    9
3.2 回溯法    10
3.2.1 算法步骤    10
3.2.2 举例说明    10
3.2.3 算法的优缺点    12
3.3 贪心法(顺序着色算法)    12
3.3.1 算法步骤[11]    12
3.3.2 举例说明    12
3.3.3 算法的优缺点    13
3.4 蚁群算法(简介)[12]    14
3.4.1 算法的基本介绍    14
3.4.2 算法步骤    15

4.1 交通信号灯管理系统    15
4.1.1 提出问题    15
4.1.2 算法设计    16
4.1.3 编写程序并用Matlab实现    18
4.2 高校排课系统    20
4.2.1 提出问题[13]    20
4.2.2 算法设计    21
4.2.3 编写程序并用VC6.0实现    22

1.1 课题的目的及意义

------分隔线----------------------------