1. 研究目的与意义（文献综述）

图论是近代数学的一个重要分支，无论是在数学领域中，还是在物理、化学、生物、天文、地理、计算机、信息、经济、交通等领域中，图论都有着重要的应用。而染色问题是图论领域的一个经久不衰的话题。染色问题按研究对象分，可以分为：点染色、边染色、面染色以及全染色等，其中结果相对最为成熟的便是边染色问题，强边染色又是边染色问题的一个新兴话题。强边染色的相关结果在通讯中频率分配等现代实际应用问题中起着理论依据的作用，尽管已经获得了不少令人满意的结果，但仍有许多改进优化的空间。

先从图论的诞生说起：在18世纪，东普鲁士哥尼斯堡有一条大河，河中有两个小岛，整个城市被这条大河分成了四块陆地，河上有七座桥把四块陆地连接起来，那里风景优美，游客众多。有一天，一名学者突发奇想：我能否既不重复也不遗漏地走遍这七座桥，然后回到出发点呢？于是这名学者便试着无重复无遗漏地走过这七座桥，可惜无论如何也回不到出发点，而要想回到出发点则必然要重复走过某座桥或者遗漏某座桥。这名学者感觉十分困惑，认为一定是自己选择的方法不对，于是把自己的想法诉说给其他学者听，其他学者也十分感兴趣，也纷纷尝试，可惜没有一个人能够成功。学者们十分困惑：使我们的方法都不对？还是这个问题本身就是无解的呢？一部分学者继续尝试，另一部分则认为这个问题本身是不可能完成的，但却无法给出证明。

直到1736年，29岁的euler向圣彼得堡科学院提交了一篇名为《哥尼斯堡的七座桥》的论文，运用一笔画的方法完美的解决了这个问题：答案是否定的。euler将四块陆地抽象成四个点，而将连接两块陆地的桥抽象成连接两点的边，这样问题就转化为能否从某一点开始，不重复不遗漏地经过这七条边，最终回到该点。再进一步抽象为能否用一笔画完成该图形，使得该图形的每条边都不重复。euler的证明方法是这样的：除了起点外，人们每进入一块陆地，也必然会从该陆地离开，所以与每一个不是起点的点相连的边必为偶数条；而从起点离开最终也要回到起点，所以与起点相连的边也必为偶数条。这样，只有与四个点相连的边都为偶数条时，该问题才能有肯定答案；而事实上，与四个点相连的边的条数分别为：3、3、3、5，因此，该问题的答案是否定的，也即不可能完成的。

2. 研究的基本内容与方案

（1）概念与记号介绍：

本论文讨论的图都是有限的、无向的、无重边的连通平面图 ，后面我们简称为图。一个图g由一些结点和一些边组成。其中这些结点分别为:v₁，v₂，…，v_n，这些边分别为：e₁，e₂，…，e_n。我们记v(g)={v₁，v₂，…，v_n}，e(g)={e₁，e₂，…，e_n}，f(g)={f₁，，f₂…，f_n}，f(g)为面集，面即为由若干条边e₁e₂…e_m围成的封闭图形，其中v(g)不可为空集，而e(g)、f(g)可以为空集，在不引起混淆的情况下，我们简记为v、g、f，v(g)、e(g)、f(g)中元素的个数，我们分别记为：|v(g)|、|e(g)|、|f(g)|。图g可以表示为：g=lt;v，egt;。在图g中，若两个结点v_i、v_j之间存在一条边e_m，则该边可以表示为：e_m=(v_i，v_j)，v_i、v_j称为边e_m的端点，并称结点v_i、v_j相互关联，以及v_i、v_j为邻接点，以及v_i、v_j的距离为1。以一个结点v_i为端点的边的条数称为该结点的度，记为d(v_i)。如果结点v_i满足d(v_i)=k，我们说v_i为k度结点。图g中所有结点度的最大值记为#8710;(g)，在不引起混淆的情况下，我们简记为#8710;。边e_m的度定义为它的两个端点的度之和，记为d(e_m)，即若边e_m以v_i、v_j为端点，则d(e_m)=d(v_i) d(v_j)。若边e_m或结点v_i的度达到给定条件下所能达到的最大值，我们称边e_m或结点v_i达到饱和。如果边e_m满足d(e_m)=k，我们说e_m为k度边。两条边e_m、e_n有公共端点v_i，我们称两条边e_m、e_n关联于v_i，并称e_m、e_n的距离为1。如果两条边e_m、e_n相互不关联，但存在一条边e_k同时关联与e_m、e_n，我们称e_m、e_n的距离为2。由结点v_i经过k条边到达v_j，我们称v_i到v_j的路长为k。由n条边围成的面f我们称为n-面或者n-圈，并称该圈的长度为n，以及该面的度为n，记为d(f)=n。我们称面与围成它的边的结点相关联。两个面f₁、f₂有一条公共边e_m，我们说f₁、f₂相邻于e_m，两个面f₁、f₂没有公共边但有一个公共结点v_i，我们说f₁、f₂相交于v_i。图g中所有圈长度的最小值我们称为图g的围长。显然，图g要么不含圈，否则围长至少为3（因为无重边）。

图g的强边染色，即用若干种颜色将图g的每一条边着色，使任意距离小于等于2的两条边着不同颜色，或者说任意长为3的路的任意两条边着不同的颜色，或者说如果两条边相邻或存在一条边连接了这两条边，那么这两条边着不同的颜色。对任意边e_m，到其距离小于等于2的边的全体，我们记为n（e_m），n（e_m）中元素数量我们记为|n（e_m）|。对图g进行强边染色所需的最少颜色数，称为图g的强边色数，记为χ_sacute;(g)。图g能被n种颜色染色，我们说图g能被n-染色。应用最小反例法时，边e_m在满足不与距离小于等于2的已着色的边同色的情况下，剩余可使用的颜色数，我们记为s(e_m)。显然，s(e_m)≤|n（e_m）|。

3. 研究计划与安排

1-3周：查阅文献，完成开题报告
4-6周：总体设计，完成论文综述
7-10周：改进与推广
11-13周：论证和检查
14-15周：撰写论文，提交初稿，老师检查，修改定稿，参加答辩。

4. 参考文献（12篇以上）

[1] r.j. faudree, a.gyárfas,r.h.schelp,zs.tuza. the strong chromatic index of graphs[j]. ars combin,1983,16a:141-150.