边的度和至多为7的平面图的强色数开题报告

 2020-02-10 10:02

1. 研究目的与意义(文献综述)

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

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

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

剩余内容已隐藏,您需要先支付后才能查看该篇文章全部内容!

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

(1)概念与记号介绍:

本论文讨论的图都是有限的、无向的、无重边的连通平面图 ,后面我们简称为图。一个图g由一些结点和一些边组成。其中这些结点分别为:v1,v2,…,vn,这些边分别为:e1,e2,…,en。我们记v(g)={v1,v2,…,vn},e(g)={e1,e2,…,en},f(g)={f1,,f2…,fn},f(g)为面集,面即为由若干条边e1e2…em围成的封闭图形,其中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中,若两个结点vi、vj之间存在一条边em,则该边可以表示为:em=(vi,vj),vi、vj称为边em的端点,并称结点vi、vj相互关联,以及vi、vj为邻接点,以及vi、vj的距离为1。以一个结点vi为端点的边的条数称为该结点的度,记为d(vi)。如果结点vi满足d(vi)=k,我们说vi为k度结点。图g中所有结点度的最大值记为#8710;(g),在不引起混淆的情况下,我们简记为#8710;。边em的度定义为它的两个端点的度之和,记为d(em),即若边em以vi、vj为端点,则d(em)=d(vi) d(vj)。若边em或结点vi的度达到给定条件下所能达到的最大值,我们称边em或结点vi达到饱和。如果边em满足d(em)=k,我们说em为k度边。两条边em、en有公共端点vi,我们称两条边em、en关联于vi,并称em、en的距离为1。如果两条边em、en相互不关联,但存在一条边ek同时关联与em、en,我们称em、en的距离为2。由结点vi经过k条边到达vj,我们称vi到vj的路长为k。由n条边围成的面f我们称为n-面或者n-圈,并称该圈的长度为n,以及该面的度为n,记为d(f)=n。我们称面与围成它的边的结点相关联。两个面f1、f2有一条公共边em,我们说f1、f2相邻于em,两个面f1、f2没有公共边但有一个公共结点vi,我们说f1、f2相交于vi。图g中所有圈长度的最小值我们称为图g的围长。显然,图g要么不含圈,否则围长至少为3(因为无重边)。

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

剩余内容已隐藏,您需要先支付后才能查看该篇文章全部内容!

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.

剩余内容已隐藏,您需要先支付 5元 才能查看该篇文章全部内容!立即支付

该课题毕业论文、开题报告、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。