資源描述:
《cayley圖與點(diǎn)傳遞圖之間關(guān)系討論》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、內(nèi)蒙古師范大學(xué)碩士學(xué)位論文中文摘要在數(shù)學(xué)和計(jì)算機(jī)科學(xué)這兩個(gè)平行發(fā)展的學(xué)術(shù)領(lǐng)域,都同時(shí)致力于研究組合結(jié)構(gòu)中的相同課題:圖論語(yǔ)言稱之為點(diǎn)傳遞圖,計(jì)算機(jī)語(yǔ)言稱之為具有較強(qiáng)對(duì)稱性的網(wǎng)絡(luò),特別是對(duì)于最初的典型例子Cayley圖的研究,己經(jīng)得到了很多令人滿意的結(jié)果.我們知道,Cayley圖一定是點(diǎn)傳遞圖,但點(diǎn)傳遞圖未必是Cayley圖.然而Godsil在文獻(xiàn)[1]得到結(jié)論:每一個(gè)連通的點(diǎn)傳遞圖都是一個(gè)Cayley圖的收縮核,并且具體地給出由點(diǎn)傳遞圖構(gòu)造Cayley圖的方法.本文主要研究連通的點(diǎn)傳圖與由它構(gòu)造的Cayley
2、圖之間的關(guān)系.首先研究這兩個(gè)圖幾個(gè)代數(shù)性質(zhì)方面的關(guān)系.如鄰接矩陣,特征多項(xiàng)式,鄰接矩陣的特征根,Laplace矩陣的特征根之間的關(guān)系,然后研究這兩個(gè)圖在完美性,Hamiiton性,強(qiáng)正則性等圖論性質(zhì)方面的關(guān)系.關(guān)鍵詞:鄰接矩陣,特征多項(xiàng)式,Laplace矩陣,完美圖,生成樹(shù)內(nèi)蒙古師范大學(xué)碩士學(xué)位論文ABSTRACTIntheacademicareaofmathematicsandcomputerscience,theyaimatstudyingthesimilartopicofcombinationstruc
3、ture:Graphtheorylanguageiscalledvertex—transitivegraph,computerlanguageisnamedthenetwithstrongersymmetry.Manyconclusionhavebeenprovedasthetypicalexample--Cayleygraph.Cayleygraphmustbeavertex—transitivegraph,butvertex—transitivegraphmaynotbeCayleygraph.Yet,G
4、odsilgotaresult:Anyconnectedvertex-transitivegraphisaretractofaCayleygraphandgavethewayconstructingtheCayleygraphbyaconnectedvertex—transitivegraph.Wemainlyresearchrelationsbetweentheminthispaper.Wefirstlyconcemalgebraicpropertiesincludingtheadjacencymatrix
5、,characteristicpolynomialandtheeigenvaluesoftheLaplace.Thenweinvestigatethegraphtheoryproperties--perfection,Hamiltonandstronglyregular.Keywords:Adjacencymatrix,Characteristicpolynomial,Laplacematrix,Perfectgraph.Thenumberofspanningtrees獨(dú)創(chuàng)性聲明本人聲明所呈交的學(xué)位論文是本人
6、在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果,盡我所知,除了文中特別加以標(biāo)注和致謝的地方外,論文中不包含其他人已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果,也不包含本人為獲得內(nèi)蒙古師范大學(xué)或其它教育機(jī)構(gòu)的學(xué)位或證書(shū)而使用過(guò)的材料。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說(shuō)明并表示感謝。簽名:日期:年月日關(guān)于論文使用授權(quán)的說(shuō)明本學(xué)位論文作者完全了解內(nèi)蒙古師范大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定:內(nèi)蒙古師范大學(xué)有權(quán)保留并向國(guó)家有關(guān)部門(mén)或機(jī)構(gòu)送交論文的復(fù)印件和磁盤(pán),允許論文被查閱和借閱,可以將學(xué)位論文的全部或部分內(nèi)容
7、編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索,可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文,并且本人電子文檔的內(nèi)容和紙質(zhì)論文的內(nèi)容相一致。保密的學(xué)位論文在解密后也遵守此規(guī)定。簽名:導(dǎo)師簽名:l勾童嗅日期:房砌尹年∥月羅日引言群和圖一直是人們關(guān)注的數(shù)學(xué)對(duì)象.但是二者結(jié)合起來(lái),用圖來(lái)研究群及用群來(lái)研究圖成為一個(gè)新的數(shù)學(xué)領(lǐng)域,是從上個(gè)世紀(jì)的三四十年代開(kāi)始的.從已知的研究結(jié)果中可以看出,用群論方法研究有較高對(duì)稱性的圖有非常重要的意義,比較典型的具有較高對(duì)稱性的圖是點(diǎn)傳遞圖(特別是Cayley圖).用對(duì)稱性對(duì)圖進(jìn)行劃分,可以分為:主
8、要有點(diǎn)傳遞圖(也稱為可遷圖或點(diǎn)對(duì)稱性圖),邊傳遞圖,對(duì)稱圖,距離傳遞圖,弧傳遞圖等.在計(jì)算機(jī)科學(xué)方面,計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是決定網(wǎng)絡(luò)性能的重要因素,而網(wǎng)絡(luò)結(jié)構(gòu)的高對(duì)稱性和正則性是網(wǎng)絡(luò)設(shè)計(jì)者所追求的目標(biāo)之一【¨,現(xiàn)在,網(wǎng)絡(luò)設(shè)計(jì)者經(jīng)常使用有限圖或者有限有向圖作為互聯(lián)網(wǎng)絡(luò)的模型.用圖的頂點(diǎn)代表網(wǎng)絡(luò)的結(jié)點(diǎn),用圖的邊代表網(wǎng)絡(luò)的通信線[21,在大型互聯(lián)網(wǎng)絡(luò)設(shè)計(jì)中,經(jīng)常使用的模型大部分是各種熟悉的群的Cayl