圖的標號問題的研究.pdf

1、分類號ICS學校代碼10136學號200900078籬★萎～菱一饕內(nèi)蒙毒民燕大學碩士學位論文圖的標號問題的研究StudyonGraphLabeling申請人：學科專業(yè)：研究方向：學位類別：指導(dǎo)教師：金斯琴圖雅應(yīng)用數(shù)學圖論及其應(yīng)用學術(shù)學位吉日木圖教授論文提交日期：二O一二年三月摘要圖的標號問題是圖論中具有實際應(yīng)用背景的研究課題近年來，國內(nèi)外這方面的研究比較活躍，研究成果被應(yīng)用于射電天文學、X一射線衍射晶體學、密碼學、通訊網(wǎng)絡(luò)編址、導(dǎo)彈控制

2、碼設(shè)計、同步機碼設(shè)計、無線電頻道分配和讀取DNA序列等它的研究始于1966年ARosa的著名的優(yōu)美樹猜想一個圖的頂點標號是圖的頂點集到整數(shù)集(一般的也可以是一個交換群)的映射，而邊標號則是圖的邊集到整數(shù)集的映射由于新的應(yīng)用背景的不斷出現(xiàn)產(chǎn)生了一些新的標號及公開問題，這些標號的構(gòu)造方法和理論有待于進一步研究這些研究有重要的理論意義和應(yīng)用價值本文利用已有的搜索圖的標號的算法，將計算機構(gòu)造性證明與數(shù)學證明相結(jié)合，主要研究了具有一個公共邊的門個

3、長為m的有向圈e。的并所構(gòu)成的有向圖玎一cm的優(yōu)美標號問題1991年，馬克杰證明了：當?shù)稙榕紨?shù)時，有向圖B一己為優(yōu)美圖2008年，趙凌琪等人證明了：當以為偶數(shù)，m=57，9，11，13時B—e。是優(yōu)美的；并提出猜想：當門為偶數(shù)時，對任意正整數(shù)m≥14，療一e。是優(yōu)美的2009年，徐喜榮等人證明了：當以為偶數(shù)且m=45，8，10時，B—e。是優(yōu)美的本文在第二章，第三章中分別證明了當m=17，19和m=21時此猜想成立關(guān)鍵詞：有向圖甩一己；