论文总字数：20954字

摘 要

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

本文在遗传算法的基础上引入了浑沌的概念，并对二者冲突数的手链速度进行了分析对比，讨论了图论的发展背景、图形着色的出现及相关概念和一些具体应用，并用可视化方法展示了图形着色。继而在标准遗传算法的基础上，结合图问题具体实际，抽象出图的着色问题，实现用遗传算法解决图形的着色问题。

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

Research on Graph-coloring Problem based on Genetic Algorithm with Chaos

Abstract

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

Formally speaking, graph-coloring problem originates from the famous Four Color Theorem at first. The graph-coloring problem not only is of importance theoretic value, but also has close relation to many practical problems, such as course scheduling, competition scheduling, radio frequency allocation, the number of registers, tec.

Currently, the research of graph-color problem is focused on the proof of Four-color conjecture, the estimate of color number about graph and the application of coloring problem of graph etc. The graph-coloring problem is a NP-complete problem. For a large-scale problems, the time of complexity of application of depth-first search algorithm is very high. Thus people propose many improved algorithms, which can improve retrospective efficiency to a great extent, but the time complexity remains rising exponentially. With various intelligent algorithm advanced, artificial neural network, genetic algorithm, simulated annealing algorithm are applied to the graph-coloring problem, which exerts many benefits.

This article puts forward the concept of chaos based on genetic algorithm and analyses convergence of conflicts of both algorithms. Then on basis of standard genetic algorithm and specific problem, abstract the graph-coloring problem and solve it.

Key Words: graph theory graph-coloring genetic algorithm chaos

目 录

摘 要 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 遗传算法的基本流程 6

3.3.3 遗传编码 8

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

3.3.4 遗传算子 10

3.3.5 控制参数和选择 12

3.3.6 标准GA的流程 13

3.3.7 GA的性能评估 13

3.3.8 引入混沌变量 13

第四章 系统分析 15

4.1需求分析概述 15

4.2 开发及运行环境分析 15

4.3 界面需求分析 15

4.4功能需求分析 16

4.5数据流图分析 16

4.6类图的分析 17

第五章　系统设计 19

5.1 概要设计 19

5.1.1 总体设计 19

5.2 详细设计 20

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

5.2.2图形着色界面设计 26

5.3 图形着色测试数据 29

5.4 收敛速度之比较 29

结束语 31

致 谢 32

参考文献 33

第一章 绪论

1.1 图论的发展背景

计算机科学和网络在快速发展的过程中，同时也很大程度上促进了其他各学科领域的进步。而图论在这个过程中也得到的很大的发展。图论作为一门新兴的学科，它的发展已经带动了很多学科的发展，无论在基础学科、运筹学、计算机科学、电子学、信息论、网络理论、管理科学或者社会科学等等方面，都可以找到图论的身影。到目前为止，图论的产生和发展已有两百多年的历史，大体上可以分成三个阶段。

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