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