oring of another Cartesianproduct graph己oC.is studied in this paper,and proved that the equitable total chromaticnumberof乞口q is 5 forall m≥3 and n≥3 too.Key Words:Cartesian Product Graph;Total Coloring;Equitable Total Coloring — —II 大连理工大学学位论文独创性声明 作者郑重声明:所呈交的学位论文,是本人在导师的指导下进行研究工作所取得的成果。
尽我所知,除文中已经注明引用内容和致谢的地方外,本论文不包含其他个人或集体已经发表的研究成果,也不包含其他已申请学位或其他用途使用过的成果。
与我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。
若有不实之处,本人愿意承担相关法律责任。
学位论文题目: 丝丝狸垫鱼盟塑鱼全羞鱼作者签名: 毖筮 日期: 迎盘年j釜月2生日 大连理工大学顾士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定,在校攻读学位期间论文工作的知识产权属于大连理工大学,允许论文被查阅和借阅。
学校有权保留论文并向国家有关部门或机构送交论文的复印件和电子版,可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印、或扫描等复制手段保存和汇编本学位论文。
学位论文题目: g堡旦g垒狸£坐旦g垒鲍塑鱼全羞鱼作者签名:壅丝蕴 日期: 绝篁年』L月兰生日导师签名:杰毒尘蓬支≥ . 大连理工大学硕十学位论文 引 言 图论的产生和发展经历了二百多年的历史,是离散数学的骨干分支。
以图论的第一篇论文瑞士数学家欧拉的哥尼斯堡七桥问题(1736)为代表,多数问题是围绕着游戏产生的。
图论所涉及的问题比较广泛,而解决问题的方法予变万化,非常灵活。
现实世界中的许多事物(或对象)能用图表示其拓扑结构,为分析处理多种问题提供一种较为理想的数学模型。
因此,图论在自然科学和社会科学的许多领域有着广泛的应用。
特别是进入20世纪七十年代以后,计算机技术迅速发展。
由于图论的算法易于借助计算机实现,二者的结合使得图论的理论及其在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域中各方面应用的研究都得到“爆炸性发展”ill。
图的着色理论起源于1852年的“四色猜想”〔21,即:在一个平面或球面上的任何地图能够只用四种颜色来着色,使得没有两个相邻的国家着相同的颜色。
后来,人们把国家(和外部区域)都看成点,当两个国家相邻时,代表这两个国家的两个点之间就用一条线来连接。
这样,“四色猜想”就转化为图论中的着色问题,即每一个可平面图是4-可着色的。
同时这也是图论着色问题中著名的“四色定理”。
从此,图着色理论的研究就一直在图理论中占有举足轻重的位置。
图的全着色是对图的顶点和边同时进行着色,使得相邻或相关联的元素得到不同的颜色。
是图的着色理论中的一个重要分支。
1973年,Meyer提出了图的均匀点着色的概念,从此揭开了图的均匀染色的序幕。
所谓均匀着色,是在原着色条件的基础之上,还要求每种颜色所染元素数相差不超过l,其所用最少着色数称为均匀色数。
1994年以来,人们又先后提出了图的均匀边着色和图的均匀全着色的概念。
图的均匀全着色研究正在发展之中,目前所知重大结果并不多。
本文在这些已有结果的基础上研究了图Qoc.和己QC.均匀全着色。
给出了一套对于任意整数所≥3,,,≥3都成立的着色方案并确定了这两类图的均匀着色数均为5。
CmDC.和厶口G的均匀全着色1 基本概念和研究动态1.1 基本概念1.1.1 图的基本概念 为了在本文的相关讨论中避免歧义,首先给出与本文研究内容相关的图论的一些基本概念和定义。
以下定义参考了文献【H】。
一个图G定义为一个二元组(坎回,以G)),简记作G毫(KD。
其中坎G)表示一个非空的顶点集合;以回表示连接顶点的边集,其中每一条边与两个顶点相关联。
若以G)中的边与顶点的无序对(B,v,)相关联,则称该边为无向边;著以回中的边与顶点的有序对<%,’,,>相关联,则称该边为有向边;每一条边都是无向边的图称为无向图;每一条边都是有向边的图称为有向图;既有无向边,又有有向边的图称为混合图。
图G中顶点的数目,称为图G的阶;图G中边的数目,称为图G的大小。
图G中的任意一条边(甜,’,)简记为“1,,一般称”和’,是相邻的顶点。
称一条边的顶点和这条边相关联。
关联于同一个顶点的边称为自环,关联于同一对顶点的两条或两条以上的边称为多重边。
无自环,无多重边的图称为简单图。
仅有一个顶点的简单图称为平凡图。
本文涉及到的图若无特别指出,均为无向简单图。
与顶点“v∈V)相关联的边数,称为该顶点的度,记作吠v):其中顶点度中的最大值称为图G的最大度,记作△(G);顶点度中的最小值称为图G的最小度,记作万(G)。
若吠吩=o,称1,为孤立点。
若政v)=1,称1,为悬挂点,与悬挂点关联的边叫悬挂边。
若Vv∈坎回,d(v净r,则称图G为r-正则图。
图萨(乃D中萨邶lVI…Vk-lekVk表示顶点和边的一个交替排列,若l≤f≤k时vi.1,聊为与e,邻接的顶点,则称W为一条通路。
若通路W中的所有边都不同,则称W为一条迹。
若迹W中的所有顶点也均互不相同,则称W为一条路径,含刀个顶点的路径记作一。
又若迹W的起点和终点相同(岵均,其他顶点都互不相同且k>3,则称它为一个圈(或回路)。
一个圈中边的个数称为这个圈的长度,长度为刀的圈记作G。
图G的围长是指在图G中最短的圈(假如G中有圈)的长度。
若一个图的每一对顶点都有一条路径连接,这个图称为是连通的。
G的一个极大连通子图称为G的一个连通分量。
一个连通图只有一个连通分量,那就是它自身。
一个图的一个割点是这样一个顶点:移去它后使剩下的图的连通分量的数目比原来的图有所增加。
一条割边也是具有类似性质的一条边。
无割点的连通图称为(点)--连通 大连理工大学硕士学位论文图。
G的极大二连通子图称为G的二连通分量。
连通的、非平凡的而且没有割点的图称为不可分图。
图G的一个极大的不可分子图称为图G的一个块。
下面介绍几类常见的图:一个连通的且无回路的图称为树。
每’’对不同顶点均有一条边相连的简单图叫做完全图,含刀个顶点的完全图记作K。
。
一个图的顶点集V若能分成两个非空子集X和L使Xu净儿Xn弘≯,且G的每条边的两个端点分别在X和】,中,则称此图为二部图,记为‘.。
。
其中特殊的墨.。
称为星图。
对图G和凰如果坎肋∈坎G),E(H)cE(G),则称日为G的子图,记为埏G;如果坎奶≠坎G)或E(H净E(OD,称H为G的真子图,记为HcG。
如果坎奶=坎G),E(H)cE(OD,则称日为G的生成子图;如果V(1-1)c坎回,当且仅当群’,∈戤回且U,vE坎14)时,材y∈以伪则称日为G的导出子图。
定义I.I.交图和联图 两个图GI和G2的笛卡尔积得到的图称为两个图的交图,记为GlnG(在某些文献中,也用“×”表示图的笛卡尔积)。
交图G_Gl口G’是满足以下条件所构成的图类: ’’ (1)G的顶点集坎G)={(甜,功I对于任意g∈Gl,v∈G2); (2)对于任意萨(“。
,“:)∈V(G),一H,屹)∈g(G),当%=■
上一篇:
信息系统对企业战略和竞争优势的作用毕业论文
下一篇:
恋沫