含有两条平行弦的圈的奇优美标号的研究

分类号：密级：ＵＤＣ：：编号理学硕士学位论文含有两条平行弦的圈的奇优美标号的研究硕士研究生：任红楠指导教师：高振滨教授学科、专业：应用数学论文主审人：卜长江教授哈尔滨工程大学２０１８年３月 分类号：密级：UDC：编号：理学硕士学位论文含有两条平行弦的圈的奇优美标号的研究硕士研究生：任红楠指导教师：高振滨教授学科、专业：应用数学论文主审人：卜长江教授哈尔滨工程大学2018年3月 分类号：密级：UDC：编号：理学硕士学位论文含有两条平行弦的圈的奇优美标号的研究硕士研究生：任红楠指导教师：高振滨教授学位级别：理学硕士学科、专业：应用数学所在单位：理学院论文提交日期：2018年1月论文答辩日期：2018年3月学位授予单位：哈尔滨工程大学 ClassifiedIndex:U.D.C:ADissertationfortheDegreeofM.ScienceAStudyofOddGracefulLabelingofCycleswithTwoParallelChordsCandidate：RenHongnanSupervisor：Prof.GaoZhenbinAcademicDegreeAppliedfor：MasterofScienceSpeciality：AppliedMathematicsDateofSubmission：Jan.2018DateofOralExamination：Mar.2018University：HarbinEngineeringUniversity 哈尔滨工程大学学位论文原创性声明本人郑重声明：本论文的所有工作，是在导师的指导下，由作者本人独立完成的＝。有关观点、方法、数据和文献的引用己在文中指出，并与参考文献相对应除文中已注。明引用的内容外，本论文不包含任何其他个人或集体己经公开发表的作品成果对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。作者（签宇）：ｎ％Ｆ：年１期３月４曰哈尔滨工程大学学位论文授权使用声明本人完全了解学校保护知识产权的有关规定，即研究生在校攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨工程大学有权保留并向国家有关部门或机构送交论文的复印件。本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据库进行检索，可，可采用影印、缩印或扫描等复制手段保存和汇编本学位论文以公布论文的全部内容一。同时本人保证毕业后结合学位论文研究课题再撰写的论文律注明作者第一署名单位为哈尔滨工程大学。。涉密学位论文待解密后适用本卢明本论文＾／在授予学位后即可〇在授予学位１２个月后□解密后）由哈尔滨工程大学送交有关部门进行保存、汇编等。（：作者（签字）：导师签字〕Ｆ１期：年令月允円年３月４朽各 摘要图论是离散数学的一个重要分支，本文主要的研究内容是图的标号问题。自A.Rosa提出了著名的优美树猜想后，人们开始广泛关注并研究图的标号问题。随后，标号图的一些结论就在物理，化学，地理，天文等领域得到了应用，尤其在计算机领域应用广泛。近几十年，图的标号经历了从无到有的快速发展，人们逐渐完善了图的标号理论并开始转向研究一些新的标号图与标号方法。关于标号图的文章数量与日俱增，其中热门的研究当属优美标号、和谐标号、友好标号。Gnanajoth定义了奇优美标号，并证明了许多奇优美图。之前学者已经研究过了圈图和龙图的奇优美性，本文结合了之前圈图的标号特点，通过构造合理标号的方法证明圈图的奇优美性，在此基础上研究含有两条平行弦的圈图的奇优美性，具体研究以下奇优美图的标号：1.弦相邻圈对称的圈图的奇优美标号；2.弦相邻圈不对称的圈图的奇优美标号；3.弦不相邻圈对称的圈图的奇优美标号；4.弦不相邻圈不对称的圈图的奇优美标号。通过研究其特点与标号规律，能够解决含有两条平行弦的奇优美标号的一般理论问题，能通过简单图的奇优美标号找出更普遍的规律，构造出相应的奇优美标号，并给出了相应的证明及例子来说明标号的准确性。关键词：标号图；优美图；奇优美标号；圈；平行弦 AbstractGraphtheoryisanimportantbranchofdiscretemathematics.Themaincontentofthispaperisaboutthelabelingproblemofgraphs.A.Rosahasproposedthefamousgracefultreeconjecture,andthenpeoplebegantofocusonandresearchthelabelingproblemofgraphs.Subsequently,someconclusionsonlabelinggraphshavebeenappliedinphysics,chemistry,geography,astronomyandsoon,especiallycomputer.Inrecentyears,graphlabelinghasrapidlydevelopedfromnothing,anditstheoryhasgraduallyimproved,sothatpeoplebegantostudysomenewlabelinggraphsandmethods.Thearticlesaboutlabeledgraphsareincreasingeveryday,includinggracefullabeling,harmoniouslabelingandfriendlylabelingwhicharethemostpopularintheresearch.Gnanajothdefinedtheoddgracefullabelingandprovedmanyrelatedgraphs.Previously,researchershaveresearchedtheoddgracefullabelingaboutthecirclegraphandthedragongraph.Inthispaper,wecombinethelabelcharacteristicsofthepreviouscirclegraph,andprovetheoddgracefullabelingofcirclegraphsbyconstructingareasonablelabelingmethod.Thethesiscombinedthelabelingcharacteristicsofpreviouscirclegraphswiththeoddgracefulnessofcirclegraphscontainingtwoparallelchords.Thedetailsarefollowing:1.Oddgracefullabelingofcirclegraphswithadjacentchordsandsymmetrycircle;2.Oddgracefullabelingofcirclegraphswithadjacentchordsandasymmetriccircle;3.Oddgracefullabelingofcirclegraphswithnonadjacentchordsandsymmetrycircle;4.Oddgracefullabelingofcirclegraphswithnonadjacentchordsandasymmetriccircle.Byresearchthecharacteristicsandtherulesofthelabeling,thegeneraltheoreticalproblemcanberesolved,thatis,oddgracefullabelingofcycleswithtwoparallelchords.Moreover,accordingtooddgracefullabelingofsimplegraphs,moregeneralrulescanbefound,andthecorrespondingoddgracefullabelingcanbeconformed,illustratingtheaccuracyoflabelingbythecorrespondingproofandexamples.Keywords:Labelinggraph,Gracefulgraph,Oddgracefullabeling,Circle,Parallelchord 目录第1章绪论..............................................................................................................................11.1研究背景及意义..........................................................................................................11.2图论的基本概念..........................................................................................................31.3本文的主要工作..........................................................................................................5第2章图的标号理论..............................................................................................................62.1标号图的概念及国内外研究现状..............................................................................62.2圈图奇优美性的国内外研究现状..............................................................................92.3本章小结....................................................................................................................13第3章含有两条相邻平行弦的圈图的奇优美性................................................................143.1预备定理....................................................................................................................143.2当nn12=时，含有两条相邻平行弦的圈Cn1,n2的奇优美性...................................143.3当n1≠n2时，含有两条相邻平行弦的圈Cn1,n2的奇优美性...................................183.4本章小结....................................................................................................................22第4章含有两条不相邻平行弦的圈图的奇优美性............................................................244.1预备知识....................................................................................................................244.2当n1=n2时，含有两条不相邻平行弦的圈Cnmn12,,的奇优美性.............................244.3当n1≠n2时，含有两条不相邻平行弦的圈Cnmn12,,的奇优美性.............................344.4本章小结....................................................................................................................49结论..................................................................................................................................51参考文献..................................................................................................................................52攻读硕士学位期间的发表论文和取得的科研成果..............................................................56致谢..................................................................................................................................57 第1章绪论1.1研究背景及意义图论是数学的一个分支，以图为研究对象。图论中的图是由若干个已知顶点及若干条连接两个顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用顶点代表事物，用连接某两个顶点的边表示相应两个事物间具有这种关系。这种图提供了一个很自然的数据结构，可以对自然科学和社会科学中许多领域的问题进行恰当的描述或建模。因此，图论的研究越来越得到专家和学者们的重视。图论本身是应用数学的一部分，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载，最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。其实图论最早是源于人们对一些民间古老趣味游戏的研究，包括欧拉解决的柯尼斯堡七桥问题，如图1.1；哈密尔顿周游世界回路；图论中的染色问题等等。通过对这些实际问题的研究，使图论的发展逐步扩大，在近几十年中随着计算机的迅速发展，图论应用的领域也越来越广。在柯尼斯堡七桥问题中，欧拉通过反复分析，将问题转化为由一些确定的点和任意两点间的连线组成的图。欧拉通过此图发现该七桥问题无解并对该问题进行了更为深入的推广，最终得出结论：只有当通过奇数座桥的地方为0个或2个时，可以满足恰好通过每座桥一次的解，否则该问题无解。欧拉对七桥问题的研究，也引起了越来越多的研究学者对这一问题的关注，七桥问题促进了图论领域的发展。图1.1七桥问题Hamilton问题源于1856年，由英国天才数学家Hamilton提出的周游世界问题是图论发展的第二阶段，把图论的研究推向了又一个新的高潮。原问题叙述为：用一个规则的正十二面体做模型，将它的所有个顶点看做20个全国各地的大城市，要求：从某个1 城市出发，只能沿着正十二面体的棱前行，并且每个城市恰经过一次，最后需再返回原出发地。那么，这样的路线存在且唯一吗？这个问题就是一个典型的图论问题，可以把其叙述成在一个无向的正十二面体图中找到一条哈密尔顿回路，如图1.2。哈密尔顿回路的研究在编码学与计算机科学、运筹学等方面的用途都十分广泛，这使得对哈密尔顿图的研究一直备受关注。图1.2哈密尔顿回路在图论的研究历史中，还存在另一个著名的问题--四色猜想。四色问题起源于地图的绘制，即在一幅地图上，是否最多只用四种颜色就可以让任何两个相邻的地区填充不同的颜色。此问题最早是由伦敦大学数学教授DeMorgan在1852年向友人的私信中提到的，说是由UCL校友FrancisGuthrie提出的。DeMorgan对这个问题极为感兴趣，却无法给出证明，于是他开始四处向同行们求助，四色问题研究的漫长旅途由此开始。1872年，英国著名数学家Cayley正式向伦敦数学学会提出了这个问题，于是四色问题成为了全世界数学界所关注的问题。1878~1880年间，著名律师兼数学家Kempe和Tait两人分别完成了证明四色猜想的论文。1967年6月，美国伊利诺大学Haken和Appel借助于计算机，分别在两台计算机上，用了近1200小时，做了100亿次判断，终于完成了四色定理的证明，轰动了数学界。尽管四色定理的证明进一步证实了地图可以只用四种颜色进行染色，但这个结论在现实中的实际应用却较少得到应用，会出现两个不连通的区域属于同一国家的情况，如美国。所以在现实生活我们在制作地图的时候，需要将这两个区域染上相同的颜色。所以，四个颜色就会不够用。图论这一学科在这些趣味数学问题的启发下逐渐形成了一套完善的体系，直到19362 年，匈牙利数学家柯尼希经过潜心的研究，终于用德语完成了第一部图论著作--《有限图与无限图的理论》，该书的出版标志着图论这一数学分支的形成。渐渐地，图论在数学相关领域逐步发展壮大，形成了代数图论、超图理论、拓扑图论、随机图论、算法图论等等分块。图论简明、直观、易于分析等特点，使各个方面与之结合，在图论的研究中需要我们提出假设，悉心论证并列举出相应的例子进行说明，而且图论本身就能起到简化运算的效果。现如今，图论还可以与计算机算法相结合，更加凸显了图论的优势，由此可以看出，图论在未来具有很大的发展空间。1.2图论的基本概念图的标号问题的研究源于1967年A.Rosa的一篇论文《Oncertainvaluationoftheverticesofagraph》，图G的顶点标号是从标号f到G的顶点的分配，使得对每一条边xy[1]的标号都依赖于顶点标号f()x和f()y。其中，两个最著名的标号是优美标号和协调标号。具有q条边的图G称为优美的，若有一单射f从G的顶点集到集合{0,1,,}q，使得当一条边xy被分配标号f()xfy−()时，所产生的边标号是不同的。图是由顶点和连接顶点的边构成的离散结构，根据图中的边是否有方向、相同顶点之间是否可以有多条边相连，以及是否允许存在自环等，图可以分为多种不同的类型。在射电天文学中提到了这样一个数学问题：设m，n，d是给定的正整数，能否找j到m个集合A，A，,A，每一个集合A由n个整数a(1≤j≤n)组成，使得D={12miii'jj'a−a1:≤j≤j≤n}满足：D∪D∪...∪D={}k:d≤k≤mn(n−2/)1+d−1。这个问ii12m题也叫m−n−d问题。转化成图论的语言，就是研究m个完全图K恰有d个点重合的n图。本文所提到的图都是简单无向图，无自环，无重边。关于文中未定义的术语请参见DouglasB.West的《IntroductiontoGraphTheory》[2]，王树禾的《图论及其算法》[3]，徐俊明的《图论及其应用》[4]。首先，我们来介绍两个离散数学中的概念[5]：有序数对与有序积，无序数对与无序积按照一定的顺序排列的两个数a、b，若a在b前，记成(a,b)，则(a,b)称为一个有序数对。若A、B是两个集合，由a∈A,b∈B所组成的形如(a,b)的所有有序数对所构成的集合，叫做A和B的笛卡尔积，或有序积，记作A×B；不需按照一定的次序排列的两个数a、b构成的数对称为无序数对，即当(a,b)=(b,a)时，a和b所构成的数对称为无序数对。设由a∈A,b∈B所组成的两个集合A、B，称A和B的无序积为ab,构成的所有无序对组成的集合，记作A&B。3 无向图G可以用顶点集和边集构成的(有序)二元数组表示，记作G=(V,E)，其中V(G)表示顶点集，E(G)表示边集，边集E(G)是无序积V&V的一个子集。若V(G)、E(G)均为有限数集，则称图G为有限图，否则称图G为无限图。图G=(V,E)的顶点个数称为图的阶，记作V(G)，边数记作E(G)，一般情况下，我们默认p表示图的阶，用q表示图的边数。当p=0时，即顶点集为空集的图，我们称为空图，记作φ；当p=1时，即只包含一个顶点的图我们称其为平凡图，否则称为非平凡图。在图G=(V,E)中，若连接两点之间的边数大于1，则称该边为多重边，连接两个相同顶点的边的条数称为边的重数，含有多重边的图称为多重图。边记为uv，也可记uv为e，即e=uv。此时称u、v为e的顶点，则两个顶点u、v邻接，并且通过边e关联。如果存在两个图G、G，它们的顶点和边都一一对应，且连接关系完全相同，只是12顶点和边的对应标号不同，则称这两个图是同构的。若不同的顶点之间的数对都有边相关联，则该图称为完全图，且n阶完全图记为K，n21其中共有Cn=−(1n)条边。n2设V和V是VG()的子集，其中V∪V=V(G),V∩V=φ，且图G中每条边的一个121212端点都在V中，而另一个端点都在V中，则称图G为二部图，记作G=(V,V;E)；分划1212(V,V)称为图G的二分划，对于存在二分划的图G，如果V中的每个顶点与V中的每个1212顶点都有边相连，则称图G为完全二部图。若VmVn==,，则完全二部图记作K。12m,n每个顶点的度数都相等的图称为正则图[6]，每个顶点度数均为k的正则图我们称之为k−正则图。由于一条途径中所包含的顶点vvvv均不相同，从而边也均不相同的途径称为012k道路；闭的道路称作圈[7]。设u,v是图G的两个顶点，若G中存在一条从u到v或从v到u的道路，则称两顶点u,v是连通的；若图G中不同的顶点u,v之间都有一条连通的道路，则称图G是连通的。n个顶点所构成的道路记作P；n个顶点构成的圈记作C。nn对C源加一个孤立点V，分别连接V与圈上的所有n个点所构成的图称为轮图。n对于图G=(V,E)，设M是E的一个子集，它的任何两条边在G中都不相邻，则称M为图G的一个匹配。若图G中的任意顶点都对应M中的某条边的端点，则称M为图4 G的一个完美匹配[8]。1.3本文的主要工作本文主要研究圈图的奇优美标号问题，首先观察每种含有平行弦的圈图的特点，再根据其各自的结构特点，用构造法将奇优美标号构造出来，最后结合实例做相关奇优美标号的验证，主要解决了判断一类圈图是否为奇优美图的问题，并且给出了具体的奇优美标号。文章共分为四章：第一章介绍图论的起源和发展过程以及应用领域，主要介绍图论中的一些基本概念和专有名词，为更好的引入下文做铺垫。第二章主要介绍优美图和奇优美图的基本概念和相关结论，给出了优美标号图和奇优美标号图的定义，并总结了奇优美标号图的国内外研究成果。第三章主要讨论了弦相邻圈图的奇优美性，通过总结其特点与标号规律构造出相应的奇优美标号，并给出了相应的证明及例子来说明弦相邻圈对称和弦相邻圈不对称的圈图都是奇优美的。第四章主要讨论了弦不相邻圈图的奇优美性，通过总结其标号特点找出符合其客观规律的一种奇优美标号方法，并给出了相应的证明及例子来说明弦不相邻圈对称和弦不相邻圈不对称的圈图都是奇优美的。5 第2章图的标号理论2.1标号图的概念及国内外研究现状图的标号理论是现代图论中的一个分支，图的标号问题作为图论中的重要内容，有着良好的应用价值和广阔的研究背景，它的研究始于1963年G.Ringel提出的一个猜想和1966年A.Rosa的一篇论文。1963年G.Ringel提出如下的猜想：设T是一个给定的有n个顶点，n−1条边的树，那么K可以分解成21n−个树同构于T。2nr−1966年A.Rosa提出了著名的优美树猜想：所有的树都是优美的。A.Rosa还给出了更一般的结论：如果G是一个有q条边的优美图，那么由K可以分解出21q+个图同2nr−构于G。图论中的标号主要分为两类，一类是对顶点的标号，另一类是对边的标号。顶点标号集是指图中的所有顶点构成的集合与整数集之间的一种映射关系，而一般边标号集都是由顶点标号衍生出来的，多数是通过顶点标号的某种运算得出的边标号集。通过对这种映射关系的判断，我们可以定义出不同的标号图。在这几类标号图中，学者们研究的最多的就是优美标号图，其衍生出的标号图也是研究者们热衷的，如奇优美标号图、亲切标号图等等。我们也可以自定义一些有共同特点的图并对其进行研究，奇优美图标号、友好标号集、和谐标号集等等。优美图是图论中热门的研究课题之一，由于它的应用性和趣味性，自上个世纪60年代中期被提出来以后，很快便得到了人们的重视与研究。至今为止，优美图的发展已有40多年的历史，近几年来，国内外学者对于优美图的研究都获得了很多的成果。图的优美标号起始于1963年，Rosa[1]提出了四种相关的图的标号方法,并分别命名为α、β、σ和ρ，并且Rosa将著名的G.Ringel猜想[9]和图的标号问题联系在一起，证明了完全图K可以分解为21p+棵同构的树。Rosa还证明了Ringel猜想成立的充要条件21p+是这些树有ρ标号。后来学者们根据α标号的特点，将其称为二分标号。S.W.Golomb重新给了β标号一个名称：优美标号[10]，这被后来的研究者们广泛采用在优美标号的研究中[12]。Rosa提出的著名优美树猜想，即所有的树都是优美的。Rosa在文献[1]中还总结出了导致图G不是优美图的3个原因：(1)G有太多顶点且没有足够的边；(2)G有太多边；(3)G有错误的奇偶性，由于第(2)个原因，不难发现无限图不是优美图对于第(3)种情况，Rosa证明，如果图G中任意顶点的度为偶数且边数|E(G|)≡2,1(mod)4，则图G不是优美6 图。下面，我们来介绍一下优美图的具体定义：定义2.1对于一个图G=(V,E)，如果对每一个v∈V，都存在一个非负整数ϕ(v)与顶点v一一对应，称ϕ(v)为v的顶点标号，满足：(1)∀u,v∈V，若u≠v，则ϕ(u)≠ϕ(v)；(2)max{}ϕ(v|)v∈V=E；(3)∀e、e∈E，如果e≠e，则ϕϕ'()ee≠'()，其中ϕϕϕ'()euv=−()()，121212e=uv，则称图G为优美图，而称ϕ为图G的一个优美标号。近些年，国内外己取得了许多关于优美图的研究成果，尽管Ringel猜想和优美树猜想至今没有被证明或否定，但有好几类树已经被证明是优美树了[13]。(1)1979年，J.C.Bermond猜想所有的龙虾树都是优美树[14]，(2)A.M.pastel和H.Raynaud[15]在1978年证明所有的橄榄树都是优美树；(3)所有的通路都是优美的[16]；(4)有几类龙虾树己经被Wang等证明是优美树了[17-19]；(5)所有的毛毛虫树都是优美的[20]；(6)其他类型的优美树：最多有4个端点的树[21]；直径最多为5的树[22]；最多有27个顶点的树[23]。A.Rosa给出了一个欧拉图是优美图的前提条件：如果图G是一个q条边的欧拉图，则图G为优美图的前提条件是q≡0,3(mod4)。显然，优美图在图论中有着重要的应用价值，其研究成果在射电天文学、密码学、网络管理以及同步机码设计等领域都有广泛的应用。随着优美图的逐渐发展，在其基础上又衍生出来一些其他标号，其中关注度最高的就是Ganaajothi提出的奇优美标号了。奇优美标号的概念：定义2.2对于一个图G=(V,E)，如果对每一个v∈V，都存在一个非负整数ϕ(v)与顶点v一一对应，称ϕ(v)为v的顶点标号，且满足：(1)∀u,v∈V，若u≠v，则ϕ(u)≠ϕ(v)；(2)存在ϕ()vE到{0,1,2,,2−1}的一个映射；(3)∀e、e∈E，如果e≠e，则ϕϕ'()ee≠'()，其中ϕϕϕ'()euv=−()()，e=uv，121212使得存在ϕ'()e到{},3,12,E−1的一个一一映射，则称图G为奇优美图而称ϕ为图G的7 一个奇优美标号。在Ganaajothi证明了以下图是奇优美图：(1)连通图P是奇优美图，其中P为包含n个顶点的路径；nn(2)当且仅当n为偶数时圈C是奇优美图，其中圈C表示n个顶点构成的圈；nn(3)完全二部图Km,n是奇优美图；(4)所有毛毛虫树是奇优美图；(5)证明了P⊙K（表示路上每个顶点加一片叶子而形成的树）是奇优美图；n1(6)证明了王冠图C⊙K（表示圈上每个顶点加一条悬挂边所构成的图）是奇优美n1图[24]。Sekar已经证明了以下图是奇优美图：(1)C⊙P当且仅当n≥3且m为偶数；mn(2)n为偶数的所有n多边形蛇图；(3)P当且仅当a≥2且b为奇数或是a和b均为偶数且ab≥≥4,4；a,b(4)一系列有一个公共点的C或是C复制而成的图；68(5)所有的香蕉树都是奇优美的[25]。Barrientos证明了：(1)由毛毛虫树组成的森林图是奇优美图；(2)任意不相连的毛毛虫树的并图是奇优美图；(3)每一个直径最多为5的树是奇优美图；(4)延伸到阶数为12的树是奇优美图[26-27]。高振滨已经证明了如下并图是奇优美的：(1)任意数个路的无交并图是奇优美图；(2)一个星图的尾点链接一条指定的边后也是奇优美图；(3)任意数个星和路的无交并图是奇优美图；(4)任意数个星的无交并图是奇优美图；(5)C∪P(m为偶数)是奇优美图，其中C、P无交；mnmn(6)C∪C(m,n均为偶数)是奇优美图，其中C、C无交；nmmn(7)每一个阶数能整除4的任意个圈的无交并图是奇优美图[28-32]。以上结论均为一些常规图奇优美性的证明，学者们通过假设、猜想、推理、论证等方法，最后通过一些具体的实例的证明，从而得出了这些构成了复杂图形的基本图形的8 性质，本文就是基于圈相关图奇优美性的基础，进一步研究含有两条平行弦的圈图的奇优美性。2.2圈图奇优美性的国内外研究现状圈图是奇优美图中比较热门的研究，人们基于圈相关图奇优美性的基础上，又深入的研究了龙图，含有弦的圈图，并图等等。圈图具备了简单图所具有的基本性质，在此基础上，学者还可以继续深入研究，进行大胆假设，细心论证，从而获得更加普遍的规律，下面我们就来介绍一下近些年来圈相关图奇优美性的主要研究成果以及国内外发展现状。定义2.3m个四含有个顶点的圈恰有一个公共点所构成的图记作Dm4,，如图2.1所示[33]。图2.1Dm4,定义2.4在轮W的轮圈C上任意两个相邻点之间加入一个点并连接相邻顶点后所nn~[34]得到的图叫做齿轮图，记为W，如图2.2所示。n~图2.2Wn在文献[34]中不仅证明了以上两种新构造出来的图是奇优美图，还提出了一种判断9 优美图的必要条件：若图G是奇优美图，则图G中不含K。这主要是因为奇优美标号3要求任意边的两个端点均为奇数和偶数的交替标号，但完全图K中必有一条边的两个3端点同奇或同偶，与定义矛盾。由此结论作为前提，又得出了完全图K(n≥)3、轮图Wnn均不是奇优美图。定义2.5对于正整数n，F表示将n个圈图排成一列，使其有且仅有一个公共交n4,点(圈图C中用于粘结其他圈的点在C中不相邻)所连成的链状连通图，如图2.3所示[35]。44vn图2.3Fn4,定义2.6对于正整数m、n，TFP(,)表示在一个F的链尾处粘结上一个由m个nm,4n4,点构成的路，如图2.4所示[36]。图2.4TFP(,)nm,4定义2.7对于正整数n，M表示在n个圈图C间依次加一条边（圈图C中用于n4,44粘结其他圈的点在C中相邻）而成的连通图，如图2.5所示[37]。4图2.5Mn4,谢建民等人的文献[37]中用归纳，总结，分类的方法构造出了T(F,P)，M的奇n4,mn4,优美标号，从而证明了这两类结合图为奇优美图。定义2.8对于正整数m、n，太阳图S表示在圈C上的每个顶点都粘结一个含有m,nmn个悬挂点的星T而成的连通图，如图2.6所示为S[38]。n+14,n10 图2.6S4,n在文献[38]中作者论证了对于任意的正整数n，S,4n与S,8n是奇优美图，其实在更早的文献中，来自本哈大学的M.I.Moussa与E.M.Badr两位学者就曾经论证过Cn⊙mK1的奇优美性，并用构造的方法证明出当n为偶数时，对任意的正整数m，Cn⊙mK1是奇优美图。定义2.9两个圈图C共用一条公共边的图称为双圈图，记为D(n)，不妨假设nC∩C=e=uv(u、v∈V(D(n))),e=uv∈E(D(n))，双圈图D满足以下条件：nnn（1）双圈图D共享的一条公共边为；vn+2v3nn22（2）顶点集V(D)={}v1|≤i≤n，顶点数V(D)=2n−2；nin（3）边集，边数E(Dn)={vivi+11|≤i≤2n−}3∪{v2n−2v1}∪{vn+2v3n}E(D(n))=2n−1。22图2.7所示即为n=8的情况[39]：图2.7D(8)在文献[39]中得出当n为偶数时，D(n)是奇优美图的结论。定义2.10用一条长为L−1的路连接两个圈C(u)=uuuu和C(v)=vvvvn12n1m12m1中的任意两个点，记为u,v，所得到的连通图称为哑铃图，记为CCP++，如图2.8ijnmL11 所示[40]。图2.8CCP++nmL在该文中仅讨论了n=m时的情况，故将哑铃图记为2CP+，并证明出当n为偶数nL时，2CP+是奇优美图。nL定义2.11在任意一个含有偶数个顶点的圈图C(n≥)6内部依次连接上平行弦Pnk后，所得到得图叫做含有平行弦的圈图[41]。在文献[41]中证得当k=35或时，该图是奇优美图。图2.9所示为C内连接平行弦10P。3图2.9C10n222定义2.12对于自然mi，n，mCi4表示n个miC4的无交并图，其中miC4表示由mii=1个C圈且每个C圈恰有两条公共边构成的图，如图2.10所示[42]。44图2.102mCi4n2在文献[42]中证得mCi4是奇优美图。i=112 从以上对于圈相关图的奇优美性的调查研究中了解到，无论圈与任何图形构成结合图，都需要满足圈中所含顶点数为偶数时方能成立，从而对本文的构造及证明起到了很大的启示和帮助。该节主要介绍了一些圈图的性质以及圈相关图的奇优美标号，从这些文章中总结出了许多关于圈相关图标号的特点与方法，与接下来的证明关系密切。2.3本章小结本章重点介绍了优美标号的性质和一些圈相关图的奇优美标号的结论，通过对大量文献的参考和总结，将许多图的定义与所要研究的图的自身结合起来，能够更加准确的把握优美图的含义及意义，希望可以对以后的优美图的研究和学习有所帮助。13 第3章含有两条相邻平行弦的圈图的奇优美性3.1预备定理定义3.1对于有q条边的图G=(V,E)，设f:V→,2,1,0{2,q−}1是一单射，如果由g(uv)=f(u)−f(v)(u,v∈V)定义的边uv标号集是,5,3,1{2,q−}1，则称图G(V,E)为奇优美图。定理3.1当一个圈图中含有顶点数为奇数时，则该图没有奇优美标号[43]。证明设图G是含有奇数个顶点的圈图，若该图有奇优美标号，则它相邻的两个顶点标号一定是奇偶互异的，即标号为奇数的点和标号为偶数的点一定是交叉出现的。且圈中第一个顶点和最后一个顶点奇偶性相同，使得两个数的差的绝对值一定是偶数，这与奇优美标号的定义矛盾。所以，一个含有圈的图为奇优美图的必要条件是该圈含有偶数个顶点。定义3.2在任意含有偶数个顶点vv01,,,,,,vvii+1vn的圈图Cn中，其内部依次连接上两条平行弦后，所得到的图叫做含有两条相邻平行弦的圈图，记为Cnn,，如图3.1、123.2所示，其中nnn=+12。图3.1Cnn12,-1图3.2Cnn12,-2注：在接下来的证明中，引理3.1、3.3、3.4、3.5中图的标号如图3.1所示，引理3.2中图的标号如图3.2所示。3.2当nn12=时，含有两条相邻平行弦的圈Cn1,n2的奇优美性在接下来的证明中，我们将Cn1,n2中各点分别标记为v0,v1,,vi,vi+1,,vn1+n2−1，其中()奇i=,2,1,0,n1,n1+,1,n1+n2−1。用VCn1,n2表示Cn1,n2的顶点标号集，用VCnn12,表示VCnn12,14 (偶)中的奇数集，用VCn1,n2表示VCn1,n2中的偶数集，用ECn1,n2表示Cn1,n2的边标号集。其中，Cn1,n2图的顶点数为n1+n2个，边数为n1+n2+2个。引理3.1当nn12=≡0(mod4)时，含有两条相邻平行弦的圈Cnn12,是奇优美的。证明定义映射f如下：nn12++nn122(nn++−2)i,i=1,3,,−3,−11222nnnn++1212iin+1,=+1,+3,,+−+−n3,nn1121222nn+ii,0=−,2,,1224fv()i=(3-1)nnnn++nn+ii+=2,1212,+2,,12−2442nnnn++312122(nni+−−)(1),i=,+2,,(nn+−)21212224332(nni+−+)(1),i=()nn++,()nn++2,,nn−21212121244由此得到C上的顶点标号集为：nn12,nn+12Vn=+{2(2nn+)−+1,2(2n+)−3,,2(2n+n+)−(1−)}Cnn12,1212122n1+n2n1+n2n1+n2∪{+,2+,4,n1+n2}∪,2,0{,−}2224n+nn+nn+n121212∪{+,2+,4,}442n+nn+n1212∪(2{n+n)−(−(2,)1n+n)−(+,)1,12122232(nn+−)[(nn+−)3]}∪1212433(2{n+n)−[(n+n)+(2,]1n+n)−[(n+n)+,]3,1212121244(2n+n)−(n+n−})11212将VC中的奇数集和偶数集进行重新整理，得：n1,n2V(奇)=n1+n2n1+n2,1Cn1,n2(2{n1+n2)+(2,3n1+n2)+,1(2,n1+n2)−+(2,5n1+n2)−+22n+n3312()1，(2n+n)−−,1(2,n+n)−(n+n)+(2,3n+n)−n+n−12121212122443(2n+n)−(n+n-),3，n+n+}11212124V(偶)=0{，2，4，，n1+n2−,2n1+n2+,2n1+n2+,4,n1+n2,n1+n2+,2Cn1,n24442215 n+n12+,4,n+n}122(奇)(偶)显然，VC是由单调递减的奇数集组成的，VC是由单调递增的偶数集组成n1,n2n1,n2()奇()偶(奇)(偶)的，且VCnn12,∩VCnn12,=Φ。故所有VCn1,n2，VCn1,n2的顶点标号集中的元素一定互异，共有n1+n2个。通过以上总结可以看出，在Cn,n中，最小的顶点标号为0，最大的顶点标号为1222()nn12++−1。故图中所有顶点标号都是互异的，由定义3.1得到Cn1,n2上的边标号集为：En,n=,5,3,1{(2,n1+n2+)2−(2,3n1+n2+)2−}1。12这些边标号集也是单调递减的奇数集，故一定互异，共有n+n+2个。12因此，当n1=n2≡0(mod)4时，含有两条相邻平行弦的圈Cn1,n2是奇优美的。引理3.2当n1=n2≡2(mod)4时，含有两条相邻平行弦的圈Cn1,n2是奇优美的。证明定义映射f如下：nn12++nn122(nn++−2)i,i=1,3,,−7,−51222nn++nn1212ii,0=−,2,,4,−3,22nn+12−+1,,nnnn−3,+−112122fv()i=(3-2)nn+22ii+=,122nn+++nnnnnnnn++12121212122(nni+−+)6,i=−2,2+,4+,,++11222224nnnn++nnnn++121212122(nni+−+)2,i=++3,5+++,,nn−212122424由此得到Cn,n上的顶点标号集为：12n+n12}5V=(2{n+n+)2−(2,1n+n+)2−,3(2,n+n+)2−+Cn1n21212122n+nn+nn+n121212∪,2,0{,−,4−,3−,1,n1+n2−,3n1+n2−}1222n+nn+n1212∪{n+n+}2∪(2{n+n)−+(2,8n+n)−+,412121222n+nn+nn+n121212(2n+n)−+,2(2,n+n)−−+}5121222433∪(2{n1+n2)−(n1+n2)−(2,1n1+n2)−(n1+n2)−,3,44(2n+n)−(n+n)+}41212将VC中的奇数集和偶数集进行重新整理，得：n1,n216 nn+12()奇{2(2nn++−)1,2(2nn++−)3,,2(2nn++−)5+,V=121212Cnn12,2n+nn+n1212n+n−(,1n+n)−,3,−,1−}3121222(偶)n1+n2n1+n2V=,2,0{,−,4(2,n+n)−(n+n)+,4(2,n+n)Cn1,n222121212333−(n+n)−(2,3n+n)−(n+n)−(2,1n+n)−(n+n)1212121212444nn++nn1212++5,,2(nn)−+2,2(nn+)−+4,2(nn+)−12121222n+n12+}82(奇)(偶)显然，VC是由单调递减的奇数集组成的，VC是由单调递增的偶数集组成n1,n2n1,n2(奇)(偶)(奇)(偶)的，且VCn1,n2∩VCn1,n2=Φ。故所有VCn1,n2，VCn1,n2的顶点标号集中的元素一定互异，共有n1+n2个。通过以上总结可以看出，在Cn,n中，最小的顶点标号为0，最大的顶点标号为122()n1+n2+2−1。故图中所有顶点标号都是互异的，由定义3.1得到Cn1,n2上的边标号集为：En,n=,5,3,1{(2,n1+n2+)2−(2,3n1+n2+)2−}1。12这些边标号集也是单调递减的奇数集，故一定互异，共有n1+n2+2个。因此，当n1=n2≡2(mod)4时，含有两条平行弦的圈Cn1,n2是奇优美的。由引理3.1和引理3.2得到：定理3.2当n1=n2时，含有两条相邻平行弦的圈Cn1,n2是奇优美的。例3.1C和C圈图的奇优美标号如图3.3和图3.4所示。8,812,12图3.3C图3.4C8,812,12将C8,8和C12,12的顶点f(vi)带入公式(3-1)，易得其边标号集分别为：EC={1,3,,33,35}、EC={1,3,,49,51}，满足定理3.2，且C8,8和C12,12都是奇优美8,812,12的。例3.2C圈图的奇优美标号，如图3.5所示。10,1017 图3.5C10,10将C10,10的顶点f(vi)带入公式(3-2)，易得其边标号集为：EC={1,3,,41,43}，满10,10足定理3.2，且C10,10是奇优美的。3.3当n1≠n2时，含有两条相邻平行弦的圈Cn1,n2的奇优美性在接下来的证明中，我们将Cn1,n2中各点分别标记为v0,v1,,vi,vi+1,,vn1+n2−1，其中(奇)i=,2,1,0,n1+n2−1。用VCn1,n2表示Cn1,n2的顶点标号集，用VCn1,n2表示VCn1,n2中的奇数(偶)集，用VCn1,n2表示VCn1,n2中的偶数集，用ECn1,n2表示Cn1,n2的边标号集。其中，Cn1,n2图的顶点数为n1+n2个，边数为n1+n2+2个。引理3.3当n1,n2≡0(mod4)(n1≠n2)时，含有两条相邻平行弦的圈Cn1,n2是奇优美的。证明定义映射f如下：(2n1+n2+)2−i,i=,5,3,1,n1−1n(2n+n+)2−i−,3i=n,n+,2,n+2−2121112nn22(2n1+n2+)2−i−,5i=n1+,n1++,2,n1+n2−2f(v)=22(3-3)ini,i=,2,0,1−22nn11i+,2i=,+,2,n−2122i+,1i=n1+,1n1+3，，n1+n2−1由此得到Cn,n上的顶点标号集为：12V=(2{n+n+)2−(2,1n+n+)2−,3(2,n+n+)2−n+}1∪C1212121n1,n1n2(2{n+n+)2−n−(2,3n+n+)2−n−,5(2,n+n+)2−(n+)−}11211211212nn22∪(2{n1+n2+)2−(n1+)−(2,5n1+n2+)2−(n1+)−,7(2,n1+n2+)222nnnn−(n+n)−}3∪11}21112,2,0{,−,4−∪{+,2+,4,n1−,2n1}∪222218 {n+,2n+,4,n+n−,2n+n}111212将VC中的奇数集和偶数集进行重新整理，得：n1,n2()奇V={2(nn++−2)1,2(nn++−2)3,,2(nn++−+2)n1,2(nn++−−2)n3,Cnn12,1212121121nn22(2n+n+)2−n−,5(2,n+n+)2−(n+)−(2,1n+n+)2−(n+)−,512112112122n2(2n+n+)2−(n+)−,7(2,n+n+)2−(n+n)−}312112122()偶nnnn1111V={0,2,,−−++4,2,2,4,,nn−2,,nn++2,4,,n+nn−+2,n}Cnn12,222211111212(奇)(偶)显然，VC是由单调递减的奇数集组成的，VC是由单调递增的偶数集组成n1,n2n1,n2(奇)(偶)(奇)(偶)的，且VCn1,n2∩VCn1,n2=Φ。故所有VCn1,n2，VCn1,n2的顶点标号集中的元素一定互异，共有n1+n2个。通过以上总结可以看出，在Cn,n中，最小的顶点标号为0，最大的顶点标号为122()n1+n2+2−1。故图中所有顶点标号都是互异的，由定义3.1得到Cn1,n2上的边标号集为：En,n=,5,3,1{(2,n1+n2+)2−(2,3n1+n2+)2−}1。12这些边标号集也是单调递减的奇数集，故一定互异，共有n+n+2个。12因此，当n1,n2≡0(mod4)(n1≠n2)时，含有两条相邻平行弦的圈Cn1,n2是奇优美的。引理3.4当n1,n2≡2(mod()4n1≠n2)时，含有两条相邻平行弦的圈Cn1,n2是奇优美的。证明定义映射f如下：(2n1+n2+)2−i,i=,3,1,n1−,7n1−5i,i=,2,0,n−,6n−,4n−,3n−11111i+,1i=n,n+,2,n+n−21112f(v)=(2n1+n2+)3−i,i=n1−2(3-4)in(2n+n+)2−i+,1i=n+,1n+,3,n+2121112n2n2n1(2n+n+)2−i−,1i=n++,2n++,4,+n−112121222nn11(2n+n)−i+,1i=+n+,2+n+,4,n+n−112221222由此得到Cn,n上的顶点标号集为：12V=(2{n+n+)2−(2,1n+n+)2−,3(2,n+n+)2−n+(2,7n+n+)2−n+}5Cnn12,1212121121∪,2,0{,n−,6n−,4n−,3n−}1∪{n+,1n+,3,n+n−,3n+n−}1∪1111111212{2(nn++−+3)n2}∪{2(nn++−2)nnn,2(++−−2)n2,,2(nn++−2)12112112112nnn222(nn++)3,2(++−++n2)(n)1}∪{2(nn++−+−2)(n)3,2(nn++2)11211211222219 nnn211−+−(nn)5,2(++−+nn2)()}∪{2(nn+−+−)(n)1,2(nn+−)112212212222n1()+−nn3,,2()+−++n()nn2}212122将VC中的奇数集和偶数集进行重新整理，得：n1,n2(奇)V=(2{n+n+)2−(2,1n+n+)2−,3(2,n+n+)2−n+,5n+n−,1Cn1,n2121212112n+n−,3,n+,3n+,1n−,1n−}3121111n(偶)1V=,2,0{,n−(,4n+n)+(,2n+n)+,4(2,n+n)−(+n)−,)1Cn1,n2112121222nn11(2n+n+)2−(+n(2,)n+n+)2−(+n)+,2(2,n+n+)2−1221221222nnn222(n+)−(2,3n+n+)2−(n+)+(2,1n+n+)2−(n+)+,3,1121121222(2n+n+)2−n−(2,2n+n+)2−n(2,n+n+)3−n+}2121121121(奇)(偶)显然，VC是由单调递减的奇数集组成的，VC是由单调递增的偶数集组成n1,n2n1,n2(奇)(偶)(奇)(偶)的，且VCn1,n2∩VCn1,n2=Φ。故所有VCn1,n2，VCn1,n2的顶点标号集中的元素一定互异，共有n1+n2个。通过以上总结可以看出，在Cn,n中，最小的顶点标号为0，最大的顶点标号为122()n1+n2+2−1。故图中所有顶点标号都是互异的，由定义3.1得到Cn1,n2上的边标号集为：En,n=,5,3,1{(2,n1+n2+)2−(2,3n1+n2+)2−}1。12这些边标号集也是单调递减的奇数集，故一定互异，共有n1+n2+2个。因此，当n1,n2≡2(mod4)(n1≠n2)时，含有两条相邻平行弦的圈Cn1,n2是奇优美的。引理3.5当n1≡0(mod,)4n2≡2(mod)4时，含有两条相邻平行弦的圈Cn1,n2是奇优美的。证明定义映射f如下：2(nn++−2)i,i=1,3,,nn−−3,112112(nn++−−2)i3,inn=,+2,,nn+−2121112n1ii,0=−,2,,22f(vi)=nnii+=2,11,+2,,n−2(3-5)122n2ii+=1,n+1,n+3,,n+1112nn22ii+3,=++++n2,n4,,n+−n3111222ii+=5,n+n−11220 由此得到Cn,n上的顶点标号集为：12V=(2{n+n+)2−(2,1n+n+)2−,3(2,n+n+)2−n+}1∪(2{n+n+)2Cnn12,121212111n1−n1−(2,3n1+n2+)2−n1−,5(2,n1+n2+)2−(n1+n2)−}1∪,2,0{−}22nnnn1122∪{+,2+,4,n1−,2n1}∪{n1+,2n1+,4,n1++}1∪{n1++,52222n2n+n+n1++,7,n1+n2−,2n1+n2}∪{12}42将VC中的奇数集和偶数集进行重新整理，得：n1,n2(奇)V=(2{n+n+)2−(2,1n+n+)2−,3(2,n+n+)2−n+,1Cn1,n21212121(2n+n+)2−n−(2,3n+n+)2−n−,5(2,n+n+)212112112−(n+n)−}112(偶)n1n1n1V=,2,0{,−,2+,2+,4,n−,2n,n+,2n+,4,Cn1,n22221111nnn222n++,1n++,5n++,7,n+n−,2n+n,n+n+}4111121212222(奇)(偶)显然，VC是由单调递减的奇数集组成的，VC是由单调递增的偶数集组成n1,n2n1,n2(奇)(偶)(奇)(偶)的，且VCn1,n2∩VCn1,n2=Φ。故所有VCn1,n2，VCn1,n2的顶点标号集中的元素一定互异，共有n1+n2个。通过以上总结可以看出，在Cn,n中，最小的顶点标号为0，最大的顶点标号为122()n1+n2+2−1。故图中所有顶点标号都是互异的，由定义3.1得到Cn1,n2上的边标号集为：En,n=,5,3,1{(2,n1+n2+)2−(2,3n1+n2+)2−}1。12这些边标号集也是单调递减的奇数集，故一定互异，共有n1+n2+2个。因此，当n1≡0(mod,)4n2≡2(mod)4时，含有两条相邻平行弦的圈Cn1,n2是奇优美的。由引理3.3、引理3.4和引理3.5得到：定理3.3当n1≠n2时，含有两条相邻平行弦的圈Cn1,n2是奇优美的。例3.3C8,12圈图的奇优美标号，如图3.6所示。图3.6C8,1221 将C8,12的顶点f(vi)带入公式(3-3)，易得其边标号集为EC={1,3,,43,41}，满足8,12定理3.3，且C8,12是奇优美的。例3.4C10,14圈图的奇优美标号，如图3.7所示。图3.7C10,14将C10,14的顶点f(vi)带入公式(3-4)，易得其边标号集为：EC={1,3,,49,51}，满10,14足定理3.3，且C10,14是奇优美的。例3.5C12,18圈图的奇优美标号，如图3.8所示。图3.8C12,18将C12,18的顶点f(vi)带入公式(3-5)，易得其边标号集为：EC={1,3,,61,63}，满12,18足定理3.3，且C12,18是奇优美的。3.4本章小结本章重点介绍了含有两条相邻平行弦的圈图的奇优美标号，并分别证明了：(1)当nn=时，含有两条相邻平行弦的圈图是奇优美的。(2)当nn≠时，含有两条相邻平行1212弦的圈图是奇优美的。由(1)(2)可得含有两条相邻平行弦的圈图是奇优美的。在对上图进行标号时，将其分为n≡0(mod4)和n≡2(mod4)(其中nnn=+12)两种情22 况进行分类标号，最后对所有情况进行归纳，总结，得到了相应的标号规律，并给出了相应的证明及例子来说明标号的准确性。23 第4章含有两条不相邻平行弦的圈图的奇优美性4.1预备知识定义4.1在任意含有偶数个顶点vv01,,,,,,vvii+1vn的圈图Cn中，其内部连接上两条弦且两弦之间有m个顶点，所得到的图叫做含有两条不相邻平行弦的圈图,记为Cnmn12,,，如图4.1、4.2所示，其中nnmn=++12，m≥2。图4.1Cnmn12,,-1图4.2Cnmn12,,-2注：在接下来的证明中，引理4.1、4.3、4.4、4.5、4.7、4.8、4.9、4.10中图的标号如图4.1所示，引理4.2、4.6中的标号如图4.2所示，且ijkl>>>。4.2当n1=n2时，含有两条不相邻平行弦的圈Cnmn12,,的奇优美性在接下来的证明中，我们将Cnmn12,,中各顶点分别标记为v0,v1,,vi,vi+1,,vn1+m+n2−1，()奇其中i=,2,1,0,n1+m+n2−1。用Vnmn12,,表示Cnmn12,,的顶点标号集，用VCnmn12,,表示VCnmn12,,()偶中的奇数集，用VCnmn12,,表示Cnmn12,,中的偶数集，用ECnmn12,,表示Cnmn12,,的边标号集。其中，Cnmn12,,中的顶点数为n1+m+n2个，边数为n1+m+n2+2个。引理4.1当n1=n2≡0(mod)4，m≡0(mod)4时，含有两条不相邻的平行弦的圈C是奇优美的。nmn12,,证明定义映射f如下：(2n1+m+n2+)2−i,i=,3,1,n1−3f(vi)=2i−(n1−)1+,6i=n1+m+n2−124 mf(v)−,4i=n−,1n+,1n+,3,n+−,3i−211112mmf(vi)=n1++,1n1++,3,n1+m+n2−322mf(v)−,6i=n+−1i−212(4-1)n1i,i=,2,0,−22f(vi)=nni+,2i=1,1+,2,n221mn2fv()4,+=in+2,n+4,,n++−2,i−211122mmnnm22nn++++++2,4,,n++−n2,111222222mmf()v=+nnnnn++2,+++4,,+m+n−2i12121222mn2fv()1+=2,in++i−2122mfv()2+=,in++ni−2122首先，需证明当n1=n2≡0(mod)4，m≡0(mod)4时，Cnmn12,,中的所有顶点vi0(≤i