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

 2020-02-10 10:02
1.目的及意义(含国内外的研究现状分析)

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

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

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

Euler还给出了连通图能一笔画的充要条件:奇点的数目是0或2个。所谓奇点,即与该点相连的边的条数为奇数。在Euler解答该问题的同时,一个全新的数学分支诞生了——图论与几何拓扑。19世纪中叶,图论进入第二个发展阶段。这一时期图论问题大量出现,其中最著名的便是被誉为世界近代三大数学难题之一的“四色猜想”。时至今日,仍有无数数学家在为证明它而不懈努力着。1936年,匈牙利著名图论学家柯尼希(Kouml;nig)发表了《有限图与无限图理论》,这是图论领域的第一部专著,总结了两百年来图论学科的主要成果,是图论发展史上重要的里程碑之一。此后五十年,图论经历了飞速发展,发展出了许多分支和交叉学科,如:图论、超图理论、极值图论、算法图论、网络图伦和随机图论等,并成为了数学领域的一门独立学科。

时至今日,图论仍活跃在科学前沿,并与众多基础学科都有交集。无论是在数学、物理、化学、生物、天文、地理等基础学科中,还是在信息、交通、经济以及众多社会科学中,我们都能看到图论活跃的身影。图论还是计算机科学中数据结构与算法中最重要的框架,随着计算机技术的高速发展,我们可以运用图论的理论,计算机工具解决交通运输,通信工程,生产管理等众多应用问题,图论的重要性以及广泛应用性不言而喻。作为一名本科生,自然无法深入彻底研究图论的方方面面,因此,我选择了图论中的一个热门问题——强边染色问题来进行研究。

什么是强边染色?先从图的边染色介绍起。所谓图的边染色,即用若干种颜色将图的每一条边着色,使任意相邻的边着不同的颜色,或者说任意距离为1的两条边着不同颜色,或者说任意长为2的路的两条边着不同的颜色。而图的强边染色,即用若干种颜色将图的每一条边着色,使任意距离小于等于2的两条边着不同颜色,或者说任意长为3的路的任意两条边着不同的颜色,或者说如果两条边相邻或存在一条边连接了这两条边,那么这两条边着不同的颜色。对图G进行强边染色所需的最少颜色数,称为图G的强边色数。

边染色以及强边染色在现实生活中诸多领域有所应用。

您需要先支付 5元 才能查看全部内容!立即支付

该课题毕业论文、开题报告、外文翻译、程序设计、图纸设计等资料可联系客服协助查找,微信号:bysjorg 、QQ号:3236353895;