有向图2k（?）的优美标号的研究

发布时间：2021-03-30 11:49

　　图的标号问题是图论中具有实际应用背景的研究课题之一.近年来国内外这方面的研究比较活跃,研究成果被应用于射电天文学、X-射线衍射晶体学、密码学和读取DNA序列等.它的研究始于1966年A.Rosa的著名的优美树猜想.一个图的顶点标号是图的顶点集到整数集（一般的也可以是一个交换群）的映射,而边标号则是图的边集到整数集的映射.由于新的应用背景的不断出现产生了一些新的标号及公开问题,这些标号的构造方法和理论有待于进一步研究.这些研究有重要的理论意义和应用价值.马克杰在《优美图》一书中介绍了几类有向图优美性的研究情况,并提出若干个继续研究的公开问题和猜想,其中猜想“当n为偶数时,有向图n（?）3是优美图”至今还没有被彻底被解决,本文对该猜想进行了研究.本文共分三章.第一章介绍有向图和超图的一些基本概念.第二章中用差分模式的方法和完全3-一致超图的理论来研究有向图n（?）3优美性,得到了当n≡0（mod 2）且2 ≤n≤16时,有向图n（?）3是优美的.第三章对n（?）3的优美性继续研究,得到了当n≡0（mod 4）且64 ≤ n ≤ 94时,有向图n（?）3的可行优美边标号. 

【文章来源】：内蒙古民族大学内蒙古自治区

【文章页数】：48 页

【学位级别】：硕士

【部分图文】：

图１?一个有向图￡＞??

６?内蒙古民族大学硕士学位论文???２有向图２＆－１６＆的优美性??为研宄方面，引入符号＆（ａ，６，ｃ）和＾３（ａ，ｃ，ｉｊ）如下：对无向完全图＆的有向标记有??如下图２中８种情况，其中只有两种情况为有向３－回路＆且方向互逆，分别为??Ｃ３（ａ，?ｂ，ｃ），?Ｃ３（ａ，?ｃ，?ｂ）．??入?ＡＡ‘Ａ‘，Ａ‘，??／?＼?Ｃ，（ｕ．Ａ．ｃ）?Ｄ?Ｄ?Ｄ??＾３?ｕ?‘／?ｈ??ｖ－?ｃ?Ｃ?＾??Ｃ＾（ｗ．ｃ－．／＞）?Ｄ?Ｄ?Ｄ??图２图尺３的所有有向图，其中有两个有向３－回路??记４（ａ，６，￡：）为＆（ａ，６，ｃ）的逆有向３－回路，并简记为＆（ａ－１＇－１，／？－１）．??我们的目的是利用所得的ｎ＆（ｎ?＝?２／〇的可行优美边标号来获得优美顶点标号，??为此我们定义如下矩阵并引入有向图同构的定义．??定义２．１设ｆｃ为任意正整数，令差分对集合??０（６＾?＋?１）?＝?｛（＾＾２）｜１＜＾＜＾?＜（６±ｔ＾?或【＜?把１＾＾，则对任意正整??数ｍ，０?乞?ｍ?Ｓ?６ｆｃ，ｅ?Ｄ（６ｆｃ?＋?１），使得??Ｈｆｊｃｐｋｚ）?＝?｛ｍ，ｍ?＋?ｋｖｍ?＋?Ｉｑ?＋?ｋ２）〇ｎ〇ｄ（６ｋ?＋?１））??构成（６ｆｃ?＋?ｌ）?ｘ３矩阵如下：??／?ｍ?ｍ?＋?ｆｅｉ?ｍ?＋?ｋｘ?－ｂ?ｋ２?＼??ｍ?＋?１?ｍ?＋?ｆｃｊ?＋?１?ｍ?４－?ｆｅａ?＋?ｆｅ２?＋?１??Ｈ（ｒｒｖ，?／＾２）（６ｆｅ＋ｉ）ｘ３?＝?：?：?：?（ｊｎｏｄ（ｆｉｋ?＋１））?Ｃｌ）??ｍ?＋?６ｆｅ?ｍ?＋?Ａ：！?＋?６ｆｃ?ｍ?＋?ｆｃｊ?Ｈ－?ｆｅ２?＋?６ｆｃ??＼?ｍ?—?１?ｍ

【参考文献】：
期刊论文
[1]有向图3■2p的优美性[J]. 斯琴巴特尔,冯伟.  纯粹数学与应用数学. 2013(02)
[2]有向图n·■9的优美性[J]. 刘小冬,付明彦,王力工,杨东升.  西南民族大学学报(自然科学版). 2005(03)
[3]图2Cn是优美有向图[J]. 丁孝全.  赣南师范学院学报. 2000(06)
[4]关于有向图n·3是优美图的一个猜想的证明[J]. 吉日木图,斯琴巴特尔.  数学的实践与认识. 2000(02)
[5]有向图2k·5及2k·7的优美性[J]. 吉日木图,斯琴巴特,陈建莉.  工程数学学报. 1999(02)
[6]n·C2P的优美性[J]. 杜之亭,孙惠泉.  北京邮电大学学报. 1994(03)

博士论文
[1]图的标号及超图分解问题研究[D]. 吉日木图.大连理工大学 2006



本文编号：3109456