-
摘要本文主要介绍了图论染色当中一个非常重要的染色方法——点染色。在如今图论运用得非常广泛的时代中，点染色已经成为了解决许多问题的常用方法，它涉及到很多领域，如通讯学，物理学，生物学，管理学等等。本文主要介绍点染色的基本原理，部分基本的染色方法，如Welch-Powell法，贪心法，回溯法等，最后运用Welch-Powell法设计一个交通信号灯系统，用贪心法设计一个简易的学院排课系统。19716
- 上一篇：指数分布与几何分布的关系探讨
- 下一篇：基于SVR支持向量回归模型的在线商品评论信息可信度分析研究
关键词：点染色；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
目 录
摘要 2
Abstract 2
一、绪论 3
1.1 课题的目的及意义 3
1.2 国内外的研究现状与发展 4
1.3 文中符号说明 5
1.4 基本概念 6
二、与点染色相关的定义及定理 6
2.1 相关定义 6
2.2 相关定理 7
三、几种求顶点色数的算法 8
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
四、点染色在现实生活中的应用 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
五、总结 25
参考文献 26
致谢 27
附录 28 一、绪论
1.1 课题的目的及意义
图论是一个应用相当广泛，并且内容十分丰富多样的数学分支，在数学的舞台上一直都比较活跃。更详细的说它是组合数学的—个分支，与其他的数学分支，如矩阵论、概率论、数值分析等有着比较密切的联系。1736年是图论的历史元年。这一年，欧拉（L•Euler）研究了哥尼斯堡城（Königsberg）的七桥问题，发表了关于图论的第一篇论文。欧拉也因此成为了图论和拓扑学的创始人。图论在19十九世纪中期进入第二个发展阶段。在这一时期关于图论的问题大量涌现出来：关于地图染色的四色问题、由“周游世界”游戏发展起来的哈密顿问题等。1936年，匈牙利数学家哥尼格(Denes Koenig)发表了第一本有关于图论专著《有限与无限图理论》，这本书总结了图论自出现以来200年的成果，在图论发展史上是具有里程碑意义的，同时也标志着图论正式成为一门独立的数学分支。时间来到20世纪中叶，图论开始了第三个发展阶段，拟阵理论、超图理论、极图理论，以及代数图论、拓扑图论等都有很大的发展。由于生产管理、军事、交通运输、计算机以及通信网络等方面提出大量的实际问题，尤其是许多离散化问题的出现，以及因为大型高速电子计算机的出现使得大规模计算问题的求解成为可能，图论的应用研究得到飞速发展。尤其是网络理论的建立，图论与运筹学等优化理论和方法的互相影响，促使图论内容的研究和应用的发展。在最近的几十年中，图论在通讯网络的设计、电网络分析、信号流图与反馈理论、计算机流程图等众多领域都有骄人的成果，进入发展与突破的快车道。现代图论早已是是数学中的重要学科，并发展出相当多的新分支，如算法图论、极值图论网络图论、代数图论、随机图论、超图论等[3]。图论中的图是客观世界中某些具体事物间联系的一个数学抽象，用顶点代表事物，用边表示各事物间的二元关系，如果所讨论的事物之间有某种二元关系，我们就把相应的顶点连成一条边。我们感兴趣的是两事物之间是否有某种特定关系，所以图形中两顶点间连接与否尤为重要，而图形的位置、大小、形状及连接线的曲直长短则无关紧要。