一个离散数学着色问题问题

来源：蜘蛛抓取(WebSpider) 时间：2018-02-27 09:14 标签： 奥数一笔画问题

图的着色问题一直是图论中的重要问题,并且在离散数学和组合分析中有着重要的应用。很多领域所涉及的问题都与图的着色理论相关,例如:排课表问题、排序问题、存储问题等等,正是基于着色理论重要的理论意义和实用意义,着色理论才被引起广泛的重视。本文主要研究了伪Halin图的强边着色、关联着色。具体研究内容如下:首先,综述了一般图的着色的概念和研究现状,例如:边着色、强边着色、顶点着色、星着色、关联着色。其次,引入强边着色、关联着色的定义。最后根据伪Halin图的结构,用构造的方法重新调整一些边的颜色,证明了一类伪Halin图的强边色数满足强边着色猜想,同时研究了伪Halin图的关联着色。 

对2-连通平面图G,f_0为G的一个边界(一个圈)上无弦的面，且V(f_0)上的顶点的度至少为3。若去掉f_0边界上的所有边后的到的图为除V(f_0)中的点外，所有的点不小于3的树T，称G为一伪-Halin图，称G为Halin图当且仅当所有V(f_0)中的点的度为3。本文研究了这类图的三种着色：关联着色、全着色、完备着色。通过研究3-正则Halin图的结构性质，确定了3-正则Halin图的关联色数。证明了伪-Halin图关联色数不超过Δ+2，确定了Δ=4或5的伪-Halin图的全色数为Δ+1，证明了3-正则Halin图的全色数不超过5，Δ=4或5的伪-Halin图的完备色数不超过7。 

设G是一个图,用Δ(G)表示图G的最大度,V(G)和E(G)分别表示图G的顶点集和边集,用dG(v)表示顶点v的度,NG(v)表示图G中与顶点v相邻的顶点的集合.图G的无循环边着色是一个映射ψ:E(G)→C={1,2,…,k},使图G的任何相邻的边都从C中分配到不同的颜色且任意的圈都可以从C中至少分配到3种不同的颜色.易见图G的无循环边着色也是图G的正常的边着色,由Vizing定理a′(G)Δ(G).无循环边着色是在无循环着色的基础上研究的,Alon等[1]提出了如下猜想:对任意的图G有,a′(G)Δ(G)+2.并且在文献[1]中Alon等证明了a′(G)64Δ(G).文献[2]中给出了a′(G)16Δ(G).Borodin[3]证明了一类图的无循环边色数a′(G)4.52Δ(G).Basavaaraju在文献[4]中证明了当Δ(G)=3时,a′(G)=4或5.定义1[5]对2-连通平面图G,f0为G的一个其边界(一个圈)上无弦... 

立体图的着色问题猜想乔彦友，武红敢（中国科学院遥感应用研究所，１００１０１）（中国林科院资源信息研究所，１０００９１）著名的四色问题源于平面地图的绘制与应用。在过去一个半世纪中，围绕该问题的证明吸引了众多的科学家，极大地推动了图论理论的发展，目前已经得到了基于计算机的证明。随着三维地理信息系统及计算机三维图形技术的发展与应用，立体图的着色问题已经成为一个有重要应用背景且有意义的问题。本文给出了立体围着色的一个典型例子，提出了相应于四色问题的猜想，以引起对该问题的讨论和关注。考虑一个立体图Ｑ，由Ｇ中相连的边围成的二维曲面区域称为Ｇ中的面，且在确定Ｇ中的面的集合时满足两两不相交的条件，即Ｇ中的任意两个面至多在它们的边界上相交。由Ｇ中的若干面围成的三维封... 

所谓求一个图的着色,指两个方面:一是求图的着色数;二是求图的着色法.它有多种应用,如时间表问题〔2,、故障诊断问题汇3,、自动布线的分层问题〔习和编译程序中寄存器的最优分配问题等.总之,可以把图的着色问题看作是一类离散最优化问题的图论模型. 本文从分析图的着色矛盾出发,对〔l]中介绍的求图的着色的算法给出有效的改进.文中所说的图皆指有限的简单无向图,所用的术语同于【5]、汇6].一、图的着色矛盾和无着色矛盾图 定义1.设G~一简单无向图,若G中存在点。(V和边(b,c)〔E,使点召和点b、‘皆不相邻,则称偶对(ab,。c)为图G的一基本着色矛盾. 显然(。b,。‘)一(。‘,。习~(。。,。习.任一图的所有基本着色矛盾组成该图的基本着色矛盾组.对任一已知的图,求其基本着色矛盾组是简便的,可按下述算法进行: 1.图G是否有未考察过的点?若无,则算法终止。 2.任取‘的一未考察点a〔V.计算机学报1985年 a女占 叮3.G中去掉点...  (本文共9页)

关于着色计数,Tutte于1973年发表第一篇文章[l],他所研究的是平面上的三角剖分.十年之后,本文作者研究了一般平面地图〔刀.接着,又研究了乎面上的3一正则地图r3].这里所研究的是外平面地图并且求出了着色计数的显式.而文献【1一31均未得到这样的显式. 由于环的出现使色多项式变为零,重边不影响色多项式的值.这里只研究不可分离的简单外平面地图,只有节点而无边的地图不在考虑之列,只有一条非环边的杆地图则在此列,记.月r为所有这种外平...  (本文共5页)

图论是离散数学的重要分支之一。着色问题是图论中研究较早的领域,也是图论的重要研究内容,最近几年来一直是图论研究中的热点问题,但至今着色问题仍是数学中未解决的难题之一。由于还未找到求图色数的有效算法,甚至还未找到有较好性能比的有效近似算法,着色理论的应用受到了很大的限制,这有待于我们去进一步的研究。 本文首先简单介绍了目前国内外关于图的着色问题的研究现状以及研究意义。其次,通过研究极大平面图的构成原理,给出了构造极大平面图的加点法,并证明了这种方法的可靠性。接着,本文给出了简单连通图的色数不大于2的充要条件。接下来,本文证明了任意一个简单平面图都是某个极大平面图的生成子图,则任意一个简单平面图色数的上界是相应的极大平面图的色数。接着,本文证明了顶点度都为偶数的极大平面图的色数为3。最后,本文在证明极大平面图都可以5-着色的基础上,用数学归纳法证明了部分加点法产生的极大平面图是可以4-着色的,并对其余的极大平面图提出了一个猜想,若这个猜想成立,则可以证明极大平面图都可以4-着色,进而证明四色定理。

【学位授予单位】：南京信息工程大学
【学位授予年份】：2008

支持CAJ、PDF文件格式


王绍文;;[J];北京机械工业学院学报;1997年02期
王绍文;;[J];北京机械工业学院学报;1998年01期
王绍文;[J];北京机械工业学院学报;1998年04期
王绍文;[J];北京机械工业学院学报;1999年01期
王绍文;[J];北京机械工业学院学报;1999年02期
王绍文;[J];北京机械工业学院学报;1999年03期
王绍文;[J];北京机械工业学院学报;1999年04期
徐志才;[J];北京邮电大学学报;2003年02期
颜宪邦,屈姿朴;[J];航空计算技术;2003年02期
李雪峰;;[J];安徽大学学报(自然科学版);2009年04期
吕洪升;;[J];安徽工程科技学院学报(自然科学版);2009年02期
侴万禧;;[J];安徽建筑工业学院学报(自然科学版);2006年04期
黄雅平;杜建庚;陈恩义;;[J];北京交通大学学报;2010年02期
王绍文;[J];北京机械工业学院学报;1998年04期
王绍文;[J];北京机械工业学院学报;1999年01期
王绍文;[J];北京机械工业学院学报;1999年02期
王绍文;[J];北京机械工业学院学报;1999年03期
王绍文;[J];北京机械工业学院学报;1999年04期
中国重要会议论文全文数据库
杨雄平;石东源;段献忠;;[A];2006中国电力系统保护与控制学术研讨会论文集[C];2006年
任崇勋;李毓祁;;[A];数学·力学·物理学·高新技术研究进展——2006（11）卷——中国数学力学物理学高新技术交叉研究会第11届学术研讨会论文集[C];2006年
余平祥;张丽红;刘伟章;余金昌;;[A];农业系统工程理论与实践研究——全国农业系统工程学术研讨会论文集[C];2006年
中国博士学位论文全文数据库
沈郑燕;[D];哈尔滨工程大学;2010年
穆华;[D];国防科学技术大学;2010年
卓莹;[D];国防科学技术大学;2010年
侯叶;[D];西安电子科技大学;2011年
中国硕士学位论文全文数据库
王芳;[D];西安电子科技大学;2010年
邹宇;[D];西安电子科技大学;2010年
张蕾;[D];中国地质大学（北京）;2011年
王绍文;;[J];北京机械工业学院学报;1997年02期
王绍文;;[J];北京机械工业学院学报;1998年01期
王绍文;[J];北京机械工业学院学报;1998年04期
王绍文;[J];北京机械工业学院学报;1999年01期
王绍文;[J];北京机械工业学院学报;1999年03期
徐志才;[J];北京邮电大学学报;1995年01期
徐志才;[J];北京邮电大学学报;1994年01期
徐志才;[J];北京邮电大学学报;1996年01期
徐志才,冯玉倩,石秀芹;[J];电路与系统学报;1998年04期
栗永安;[J];兰州铁道学院学报;1998年01期
徐淮涓;;[J];淮阴师范学院学报(自然科学版);2005年04期
王志雄;[J];漳州师范学院学报(自然科学版);1994年04期
王军秀;;[J];纯粹数学与应用数学;2007年03期
左光纪;;[J];新疆大学学报(自然科学版);1989年01期
瞿晓鸿,杨晓帆,柏森;[J];重庆大学学报(自然科学版);1998年06期
周国斌;[J];数学的实践与认识;1979年01期
中国重要会议论文全文数据库
冯纪先;;[A];武汉(南方九省)电工理论学会第22届学术年会、河南省电工技术学会年会论文集[C];2010年
来新夏;;[A];抗日战争史及史料研究（一）——中国近现代史史料学学会学术会议论文集[C];1995年
雷良;;[A];中国土地学会1987年学术讨论会论文选集[C];1987年
冯纪先;;[A];第十五届电工理论学术年会论文集[C];2003年
;[A];中国化学会第十届胶体与界面化学会议论文摘要集[C];2004年
赵世明;;[A];中国土木工程学会水工业分会第四届理事会第一次会议论文集[C];2002年
王福建;曾学贵;;[A];中国土木工程学会计算机应用分会第七届年会论文集[C];1999年
李秀彦;赵朝辉;李庆珍;;[A];煤矿物探学术论文集（2007）[C];2007年
申世国;薛晓轩;甄天忱;;[A];吉林省测绘学会2008年学术年会论文集（上）[C];2008年
中国重要报纸全文数据库
魏剑生　翁贤光;[N];闽北日报;2010年
本报记者 熊熙玲;[N];中国财经报;2003年
中国博士学位论文全文数据库
中国硕士学位论文全文数据库
刘茜;[D];南京信息工程大学;2008年

【摘要】：图的着色问题是由地图的着色提出的,它是最著名的NP-完全问题之一。图的着色理论不仅在离散数学和组合分析等数学理论中有着广泛的应用,近年来,随着生产管理、交通运输、军事、计算机和通讯网络等方面许多离散型问题的出现与研究,图论的着色问题具体应用在解决安排会议或考试的日程以避免冲突和安排化学品的存储上以避免相互反应等问题上并取得了较好的效果。 图的无圈着色和线性着色是在顶点着色的基础上提出的。本文研究了几类简单图的无圈着色以及与之密切相关的线性着色问题,主要分为三部分: 在第一部分中(见论文第一、二章)对图论着色问题的研究历史、背景、基本概念等进行一个综述。主要包括:正常顶点着色、无圈着色、星着色、3-不足着色和线性着色等,为后文的论证打好基础。 第二部分(论文第三、四章)探讨图的无圈着色和线性着色问题。 无圈着色在研究星着色、2-距离着色等问题中具有重要意义,这类着色问题通常会以无圈色数作为下界来逼近其色数的确界,因此在着色研究中只要无圈着色有进展,其他一系列着色就会有相应的改进。第三章通过分析图的结构,运用归纳等数学理论方法给出了最大度为5的非正则图和高度图的无圈色数界,并通过群论中置换思想给出含有割边或割点的五正则图无圈色数的更加精确的上界。第四章首先运用J. Heuvel的一个引理缩小了最大度大于11的平面图的线性可选择着色色数的上界;然后通过分析最大度为4的图的着色特点得到了这一类图线性色数的较为精确的上界,并给出具体算法说明这个界是可达的;随后证明了d维网格线性着色的确界。 最后是对本文结论、主要创新之处的总结,以及有关无圈着色和线性着色研究的展望。

【学位授予单位】：重庆大学
【学位授予年份】：2011


张忠辅,刘林忠,王建方,袁晋江;[J];西北师范大学学报(自然科学版);2002年01期
张健红;左春柽;钱生君;齐培正;;[J];系统仿真学报;2008年05期
马新民;曾勇;尹旭日;包帅善;;[J];安徽大学学报(自然科学版);2009年05期
余训爽;;[J];安徽大学学报(自然科学版);2011年01期
刘守强,胡章文,陶庭先,唐定兴;[J];安徽工程科技学院学报(自然科学版);2005年03期
侴万禧;;[J];安徽建筑工业学院学报(自然科学版);2006年04期
余训爽;李爱国;黄建平;;[J];安徽师范大学学报(自然科学版);2006年03期
毕守东,胡焱,郭晓冰,凌成,许迎东;[J];安徽农业大学学报;2000年01期
毕守东,胡焱,郭晓冰,康冠林,胡莲;[J];安徽农业大学学报;2000年02期
徐士友;储先萍;汪海燕;;[J];北京工业大学学报;2006年12期
冯长君;杨伟华;沐来龙;;[J];北京工业大学学报;2008年06期

我要回帖

更多关于 奥数一笔画问题 的文章

 

随机推荐