几类图的双约束边染色问题_毕业论文范文网-论文范文

搜索高级搜索

原创毕业论文

几类图的双约束边染色问题

作者: 浏览:5次

免费专业论文
政治工作论文
计算机论文
营销专业论文
工程管理论文范文
医药医学论文范文
法律论文范文
生物专业论文
物理教学论文范文
人力资源论文范文
化学教学论文范文
电子专业论文范文
历史专业论文
电气工程论文
社会学专业论文
英语专业论文
行政管理论文范文
语文专业论文
电子商务论文范文
焊工钳工技师论文
社科文学论文
教育论文范文
数学论文范文
物流论文范文
建筑专业论文
食品专业论文
财务管理论文范文
工商管理论文范文
会计专业论文范文
专业论文格式
化工材料专业论文
英语教学专业论文
电子通信论文范文
旅游管理论文范文
环境科学专业论文
经济论文
人力资源论文范文
营销专业论文范文
财务管理论文范文
物流论文范文
财务会计论文范文
数学教育论文范文
数学与应用数学论文
电子商务论文范文
法律专业论文范文
工商管理论文范文
汉语言文学论文
计算机专业论文
教育管理论文范文
现代教育技术论文
小学教育论文范文
机械模具专业论文
报告,总结,申请书
心理学论文范文
学前教育论文范文

收费计算机专业论文范文

收费计算机专业论文
Delphi
ASP
VB
JSP
ASP.NET
VB.NET
java
VC
pb
VS
dreamweaver
c#.net
vf
VC++
计算机论文

毕业论文范文题目：几类图的双约束边染色问题，论文范文关键词：几类图的双约束边染色问题
几类图的双约束边染色问题毕业论文范文介绍开始：
【论文摘要】：本文考虑的图均为简单无向有限连通图．一个图G，若能被画在平面上，使得其每两条边仅在端点处才能相交，则称它为可嵌入平面的，简称可平面的．平面图的这种在平面上的画法称为一个平面嵌入，也称之为是一个平面图．一个平面图G把平面划分成若干个连通区域，这些区域的闭包称为G的面，其中唯一的一个无界面称为G的外部面，其它的面均为内部面．对于一个平面图G，我们用V(G)、E(G)和F(G)分别表示图的顶点集合、边集合和面集合，两个面f_1，f_2∈F(G)，当且仅当f_1和f_2有公共边时称它们为相邻；面的边界上的点和边称为与该面相关联，与面f相关联的边的数目称为面f在G中的度(割边计算两次)，记为d_G(f)．G中的面度最大者称为G的最大面度，记为F_M(G)；外部面的面度记为F_(ext)(G)，同时，用△(G)、δ(G)分别表示G的顶点的最大度和最小度．平面图G的有点面约束的边染色，也称双约束边（本文此处忽略..）染色，是指对G的边进行染色使得关联同一点的边有不同的颜色且在同一面上的边也有不同的颜色；使图G可进行双约束边染色所需的最小颜色数称为G的双约束边色数，记为χ_(e／vf)(G)．O．V．Borodin和D．R．Woodall首先提出了双约束边染色的概念，并针对外平面图的双约束边色数进行了研究，得出了比较好的结果．本文针对平面图的双约束边染色问题进行了进一步的广泛研究，其中重点就若干特殊类型的平面图，如近似Halin图、近似外平面图、双外平面图、高度平面图等，展开了较深入的讨论．平面图G，如果δ(G)≥3且G去掉外部面的边界之后是一棵树，就称为是一个Hailin图；而一个非Hailin图如果近去掉或者是收缩一条边以后就成为一个Hailin图，我们称为是一个近似Hailin图．平面图G，如果其所有的顶点都在同一个无界面的边界上，则称它为一个外平面图；（此处忽略..）一个非外平面图如果近去掉或者是收缩一条边以后就成为一个外平面图，我们也称为是一个近似外平面图．所有顶点都出现在两个面上的平面图称为双外平面图．平面图G，若满足△(G)=|V(G)|-k，k=1，2，…，则称G为一个h_k-图，k=1，2的h_k-图称为高度平面图，无割点的h_k-图又称为p_k-图．全文共分五章，第一章介绍了图论中的若干基本概念，简单综述了图的染色理论的发展过程以及与本文相关的一些已有的结果．第二章首先介绍了Halin图的双约束边染色已经的较好的结果．然后分别研究了两类近似Hailin图(几乎Halin图，Halin图的弱剖分图)的双约束边染色问题．第三章介绍了关于外平面图的双约束边染色的已有结果．重点就两类近似外平面图(几乎外平面图，外平面图的弱剖分图)的双约束边染色问题展开了研究．第四章介绍了双外平面图的特点，研究了特殊的双外平面图的双（本文此处忽略..）约束边染色问题．第五章初步研究了特殊的高度平面图的双约束边染色问题．得出的主要结论有：定理1设G是几乎Halin图，且余边e位于G-e的内部面上，则有χ_(e/vf)(G)=F_(ext)(G)．定理2设G是几乎Halin图，且余边e位于G-e的外部面上，如果G-e非轮图，且存在有内部面达到了最大面度，则有χ_(e/vf)(G)=F_M(G)．定理3设G是Halin图的弱剖分图，则有χ_(e/vf)(G)=F_M(G)．定理4如果G是带有余边e的几乎外平面图，而G-e恰是由一个圈加上一条对角线构成的外平面图，那么F_M(G)≤χ_(e/vf)(G)≤F_M(G)+1．定理5如果G是带有余边e的几乎外平面图，而G-e是△=4的2-连通极大外平面图，那么χ_(e/vf)(G)≤max{F_M(G)+1，△(G)+1}．定理6若G恰好是C_n加上一条k-对角路构成(n≥3,k≥1)，则χ_(e/vf)(G)=n+k≤3/2F_M(G)，且当且仅当n=2k且（本文此处忽略..）对角路为正对角路时，达到最大值3/2F_M(G)．定理7假设G’为2-连通的外平面图，G为G’的弱剖分图，只要G不是由一个圈加上一条对角路，就有χ_(e/vf)(G)=F_(ext)(G)．定理82-连通图G如果是正则双外平面图，那么χ_(e/vf)(G)≤F_M(G)+1．定理9设G是|V(G)|≥6的p_1类图，则必有χ_(e/vf)(G)≤△(G)+1，且χ_(e/vf)(G)=△(G)+1当且仅当图G同构于图5．1．1所示的图P_△。在本文的最后，提出了一些问题以及有关平面图的双约束边色数的猜想，以待进一步研究．

以上为本篇毕业论文范文几类图的双约束边染色问题的介绍部分。

本论文在计算机论文栏目，由论文网(www.zjwd.net)整理,更多论文,请点论文范文查找

相关论文

收费专业论文
汉语言文学论文
物理学论文
自动化专业论文
测控技术专业论文
历史学专业论文
机械模具专业论文
金融专业论文
电子通信专业论文
材料科学专业论文
英语专业论文
会计专业论文
行政管理专业论文
财务管理专业论文
电子商务国贸专业
法律专业论文
教育技术学专业论文
物流专业论文
人力资源专业论文
生物工程专业论文
市场营销专业论文
土木工程专业论文
化学工程专业论文
文化产业管理论文
工商管理专业论文
护理专业论文
数学教育专业论文
数学与应用数学专业
心理学专业论文
信息管理专业论文
工程管理专业论文
工业工程专业论文
制药工程专业论文
电子机电信息论文
现代教育技术专业
新闻专业论文
艺术设计专业论文
采矿专业论文
环境工程专业论文
西班牙语专业论文
热能与动力设计论文
工程力学专业论文
酒店管理专业论文
安全管理专业论文
交通工程专业论文
体育教育专业论文
教育管理专业论文
日语专业论文
德语专业论文
理工科专业论文
轻化工程专业论文
社会工作专业论文
乡镇企业管理
给水排水专业
服装设计专业论文
电视制片管理专业
旅游管理专业论文
物业管理专业论文
信息管理专业论文
包装工程专业论文
印刷工程专业论文
动画专业论文
环境艺术专业论文
信息计算科学专业
物流专业论文范文
人力资源论文范文
营销专业论文范文
工商管理论文范文
汉语言文学论文范文
法律专业论文范文
教育管理论文范文
小学教育论文范文
学前教育论文范文
财务会计论文范文

电子商务论文范文

上一篇：基于价值函数修正的GARCH模型及其..

下一篇：铝电解电容器高压阳极铝箔的直流..