图的染色问题及其应用开题报告

全文总字数：2630字

1. 研究目的与意义

图论是近年来发展迅速而又应用广泛的一门新兴学科，已广泛应用于运筹学、网络理论、信息论、控制论、博奕论以及计算机科学等各个领域。

图的着色问题最早起源于著名的四色问题，染色问题不但有着重要的理论价值，而且它和很多实际问题有着密切联系，例如解决时间表问题、排序问题、排课表问题、交通状态、运输安排、电路设计和贮藏问题等涉及任务分配的实际问题。

2. 国内外研究现状分析

1、国内外研究历史图论的着色理论起源于150年前的四色猜想，即在一个平面或球面上的任何地图都能够只用四种颜色着色，使得每个国家用一种颜色，且没有两个相邻的国家有相同的颜色。

1976年k.apple和w.haken在j.koch的协助下用计算机检验了四色猜想是正确的，从而四色猜想被四色定理所代替，在1997年，n.robertson等又给出了一个简化的计算机证明。

尽管迄今为止仍没有得到非计算机的理论性证明，但人们在冲击四色猜想的过程中所创造的新的思想、方法和技巧为图论宝库增添了一个又一个精彩结果。

3. 研究的基本内容与计划

1、研究内容、方法：（1）详细图的染色的基本概念以及应用范畴。

（2）详细给出图的染色的理论知识和方法。

（3）举出图的染色在实际生活中的应用实例。

4. 研究创新点

1、详细阐述图的染色的理论基础以及实际应用。

2、原理、方法、算法等和实例分析相结合。