关于边染色临界图有关性质的研究

发布时间：2017-11-07 14:05

  本文关键词：关于边染色临界图有关性质的研究

  更多相关文章： 临界图 边染色 独立数 差值转移法

【摘要】：图论相对于其他数学分支学科来说,迄今为止只有200多年的历史。本文研究的边染色临界图的问题是图的染色问题的一个分支,也是图论的主要研究对象之一。最大度为D的图G,其边色数'c(G)要么是D,要么是D+1。如果'c(G)=D,则称图G是第一类的;如果'c(G)=D+1,则称图G是第二类的。如果图G是连通的、第二类的,且对每条边''c(G-e)c(G),则称G是临界图。用'(G)ac表示。Vizing(1964)和Gupta(1966)各自独立的得出一个关于图的边色数重要定理(Vizing Theorem):对任意最大度为D的简单图,'c(G)=D或'c(G)=D+1。1960年,Vizing提出了临界图独立数猜想(Vizing’s Independence Number Conjecture):若G是n阶D临界图,则有()2VaG￡,目前为止仍没有被完全证明出来。本文在前人研究的基础上,通过修改某些限制条件研究了边染色临界图的边数和独立数的问题,共分4章.第1章主要对本课题的研究背景、研究现状和基础概念等做了简单介绍.第2章讨论了对于不含2度点边染色临界图的独立数的范围。利用差值转移方法证明了证明当最大度D?{9,10}时,3 3()5 3aG VD-￡D-和当D?{11,L,46},独立数15 42()23 42aG VD-￡D-。第3章讨论了边染色临界图的边数的新下界,通过运用差值转移的方法证明不含3-圈的5-临界图和6-临界图边数的新下界分别为12156m3n和13352m3n,比目前最好的结果157m3n和3313m3n分别提高了128n和126n。第4章提出了一些值得进一步研究的问题.
【学位授予单位】：中国矿业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【共引文献】

中国期刊全文数据库 前10条

1 张彬;袁丛鑫;司璇;金飞;;基于图论的数字图像边缘检测算法[J];中国传媒大学学报(自然科学版);2011年03期

2 张忠海;李端玲;廖启征;;柔性变胞机构的拓扑结构表示及构态变换分析[J];北京邮电大学学报;2010年03期

3 涂冰英;;实时动态最佳路径的实现方法[J];测绘信息与工程;2006年03期

4 郭纪云;;每棵非平凡树至少有两片叶子的证法研究[J];长沙大学学报;2011年05期

5 叶玉民,周立新,胡小倩;关于最佳粮库地址的选择[J];东北电力学院学报;2001年01期

6 解大;何恒靖;常喜强;姚秀萍;;电力系统低频减载的同调分区定义与割集算法[J];电力系统及其自动化学报;2011年03期

7 陈彬;于继来;;电力网络拓扑分析与源流路径链生成算法[J];电力系统及其自动化学报;2012年01期

8 陶华;杨震;张民;杨俊新;贺仁睦;石岩;;基于深度优先搜索算法的电力系统生成树的实现方法[J];电网技术;2010年02期

9 解大;何恒靖;常喜强;姚秀萍;;计及同调分区和全局优化的电力系统低频减载方案[J];电网技术;2010年06期

10 张民;贺仁睦;许津津;陶华;石岩;;图论在BPA模型向PSCAD模型自动转换中的应用[J];电网技术;2012年06期

中国重要会议论文全文数据库 前1条

1 方崇惠;王伟;方波青;;南水北调东荆河节制工程复杂分汊河网水力分析[A];水文泥沙研究新进展——中国水力发电工程学会水文泥沙专业委员会第八届学术讨论会论文集[C];2010年

中国博士学位论文全文数据库 前10条

1 邱宇;基于双边滤波的图像去噪及锐化技术研究[D];重庆大学;2011年

2 白跃伟;结构造型技术及其在机械三维CAD中的应用[D];华中科技大学;2004年

3 张多利;基于功能信息的验证工程学及若干验证技术研究[D];合肥工业大学;2005年

4 乔海泉;并行仿真引擎及其相关技术研究[D];国防科学技术大学;2006年

5 秦宁宁;无线传感器网络栅栏覆盖的研究[D];江南大学;2008年

6 贾玉福;基于资源受限的无线传感器网络关键问题研究[D];华中科技大学;2007年

7 林德明;适应性Agent图及其在复杂系统脆性分析中的应用[D];哈尔滨工程大学;2008年

8 王静;网络编码理论及其应用的研究[D];西安电子科技大学;2009年

9 崔琳;石油化工过程HAZOP专家系统与集成研究[D];北京化工大学;2009年

10 何双华;供水管网系统抗震可靠性分析及加固优化研究[D];大连理工大学;2009年

中国硕士学位论文全文数据库 前10条

1 王冰山;网络两端可靠性问题的研究[D];西安电子科技大学;2011年

2 武艳南;基于管理机制设计理论的应急协调系统设计及其应用[D];山东大学;2011年

3 郑孝俊;基于感兴趣区域的颅脑图像处理与应用[D];安徽大学;2011年

4 赵琪;认知无线电网络频谱分配及共享算法研究[D];杭州电子科技大学;2010年

5 谭显强;基于FPGA的3D图形处理器IP核的设计与实现[D];南京航空航天大学;2010年

6 雷杨;基于凸形障碍物的注水管网优化研究[D];中国石油大学;2011年

7 陶慧;赤峰市烟草公司物流配送路线优化研究[D];吉林大学;2011年

8 颜宁;基于层次分析和搜索算法的博弈模型研究[D];东北大学;2009年

9 季开青;基于轴辐式网络的应急物资调度问题研究[D];辽宁科技大学;2010年

10 秦波;发电厂电气主接线可靠性研究与实践[D];广西大学;2002年

，

本文编号：1152714