论文总字数：18686字

摘 要

近年来，图论的发展速度迅猛，而且又得到了广泛的应用显然成为了一门新的学科。在许多领域诸如：网络理论、控制论、博弈论、信息论、运筹学以及计算机科学等得到了广泛的应用。图的着色问题公认最早是起源于一个非常著名的问题——“四色问题”，不但密切联系了很多实际问题，而且它的理论价值也是非常重要的。而且，在很多问题上都有着很密切的应用，比如说排课问题、安排比赛，无线频率分配、变址寄存器数目等。当前，对图着色问题的研究主要集中在四色猜想的证明、图的色素估计以及图着色的应用等方面。图的着色问题作为一个大的NP-完全问题，面对稍大规模的问题时，我们通常采用深度优先的搜索算法。但弊端也是相当明显的，比如说求解问题时候时间复杂度很高。由于种种弊端的原因，很多改进算法被提出，回溯效率在很大程度上也被提高了。但是问题还是没有得到解决——时间复杂度仍然还是指数级的。人们提出了很多智能算法，图形着色也可以通过很多算法来解决，比如说本文研究的遗传算法、模拟退火算法，人工神经网络等，也都产生了很好的效果。

本文首先讨论了图论的发展背景、图形着色的出现及相关概念和一些具体应用，并用可视化方法展示了图形着色。继而在标准遗传算法的基础上，结合图问题具体实际，抽象出图的着色问题，实现用遗传算法解决图形的着色问题。本文的一大亮点在阐述过程中广泛的提及了其他各种解决相应问题的方式，并对其核心操作步骤进行分析。读者也可通过其和遗传算法进行比较，得出自己心目中的理想解决问题的算法。

关键词：图论 图形着色 遗传算法

Base On Genetic Algorithm For Research On Coloring Problems of Graph

Abstract

Graph theory is a jumped-up subject which develops very rapidly in recent years and is applied extensively. It is widely applied to the field of game theory, network theory,information theory,cybermetics,computer science and so on.

Generally speaking,the coloring problem of graph early originates from the famous “four color problem”.The coloring problem is not only be of important theoretic value,but also having close relation to many practial problems, such as course scheduling, competition scheduling, radio frequency allocation, the number of registers and so on, be of direct application.

Currently, the research of coloring problem of graph is focoued on the proof of Four-color conjecture, the estimate of color number of graph and the application of coloring problem of graph and so on. The coloring problem of graph is a NP-complete.for slightly large-scale problems, use the depth-first search algorithm, the time complexity of solving the problem is high.for this,people propose many improved algorithms, which improve retrospective efficiency to a large extent,but the time complexity is rising exponentially. With various intelligent algorithm advanced, many people use artificial neural network,genetic algorithm, simulated annealing algorithm to coloring problems of graph,which produced very good results.

In this article, I will discuss development background of color theory, the emergence of color graphics and related concepts and some specific applications, display the coloring of graph. Then on the basis of standard genetic algorithm, combining the specific reality of graph problems, abstracting coloring problems of graph, using genetic algorithms to solve the coloring problems of graph.

Key Words: graph theory coloring of graph genetic algorithm

目 录

摘 要 I

Abstract II

目 录 III

第一章 前言 1

1.1 图论的发展历程 1

1.2 遗传算法的起源 2

1.3 本文内容及研究意义 2

第二章 图形着色的相关理念 3

2.1图形着色问题的出现 3

2.2 图形着色的相关基本概念 3

2.3 当前对图形着色的研究方向和方法 4

第三章 遗传算法 5

3.1 遗传算法的产生和发展 5

3.2 遗传算法的基本原理 5

3.3遗传算法的基本描述 5

3.3.1 遗传算法的基本流程 6

3.3.2 遗传编码 8

3.3.3适应函数(评价函数) 10

3.3.4 遗传算子 10

第四章 系统分析 15

4.1需求分析概述 15

4.2 开发及运行环境分析 15

4.3 界面需求分析 15

4.4功能需求分析 16

4.5数据流图分析 16

4.6类图的分析 17

第五章 系统设计 18

5.1 概要设计 18

5.1.1 总体设计 18

5.2 详细设计 19

5.2.1 系统各模块的详细设计 19

5.2.2图形着色界面设计 25

5.3图形着色测试数据 28

结束语 30

致 谢 31

参考文献 32

第一章 前言

1.1 图论的发展历程

在信息技术的快速发展环境下，各个领域的科学也乘势蓬勃发展，图论就是这一大环境中快速发展的产物。一般来说，图论以图为研究对象是一支发展较快的数学分支。至今为止，图论作为一门数学科学走过了200多年的历程，大致经历了3个阶段。

请支付后下载全文，论文总字数：18686字