關(guān)于正規(guī)圖的一些結(jié)果.pdf

1、圖論是一門發(fā)展迅速而又應(yīng)用廣泛的新興學(xué)科,它最早起源于一些在民間廣泛流傳的數(shù)學(xué)游戲的難題研究,如迷宮問(wèn)題,博弈問(wèn)題,棋盤上馬的行走路線問(wèn)題等.其中最早的文字記載出現(xiàn)在歐拉1736年發(fā)表的論文《與位置幾何有關(guān)的一個(gè)問(wèn)題的解》中,這就是著名的哥尼斯堡七橋問(wèn)題.歐拉將這個(gè)問(wèn)題轉(zhuǎn)化為第一個(gè)圖論問(wèn)題.證明了這個(gè)問(wèn)題是無(wú)解的,并推廣了這個(gè)問(wèn)題.
　　 像這些古老的數(shù)學(xué)游戲問(wèn)題,當(dāng)時(shí)吸引了很多學(xué)者的關(guān)注,學(xué)者們?cè)谘芯窟@些問(wèn)題的基礎(chǔ)上,又陸續(xù)提

2、出了著名的四色猜想和哈密爾頓回路等問(wèn)題.
　　 正規(guī)圖(normalgraph)是由信息理論的內(nèi)容自然而然出現(xiàn)的,是由圖的熵而引出的一個(gè)概念.K(o)mer在文獻(xiàn)[7]里證明了完美圖是正規(guī)圖.
　　 完美圖是在處理信息理論中的香農(nóng)容量(ShannonCapacity)問(wèn)題時(shí)引出的一個(gè)圖論概念.在圖論研究領(lǐng)域完美圖特別因Berge提出的強(qiáng)完美圖猜想而著名,即不存在無(wú)弦的奇圈C2k+1及它們的補(bǔ)圖C2k+1(k≥2)作為導(dǎo)出

3、子圖的圖是完美圖.這個(gè)猜想在2006年由Chudnovsky,Robertson,Seymour,和Tomas四人共同解決[4].但是由DeSimone和K(o)mer描述的正規(guī)圖的猜想(不含C5,C7,(C7)作為導(dǎo)出子圖的所有的圖都是正規(guī)的)至今仍然未被解決.
　　 除了完美圖及由K(o)rner在[7]中證明的一些圖類外,只有很少的圖類被證明是正規(guī)圖.在[14]中Walgler證明了Circulants是正規(guī)圖,這就證明了

4、正規(guī)圖猜想對(duì)Circulants是成立的.之后Patakfalvi在2007年在[15]中證明了立方圖的線圖是正規(guī)圖.
　　 本文主要證明了不含C5,C7的廣義Petersen圖G(n,k)(在第一章中定義)當(dāng)滿足3|n,或3|(n-1)且3|(k-2)時(shí)是正規(guī)圖.并對(duì)正規(guī)圖的結(jié)構(gòu)在文獻(xiàn)[13]的基礎(chǔ)上作了進(jìn)一步研究.
　　 本文由以下章節(jié)構(gòu)成:
　　 第一章中主要介紹了一些基本概念和已有結(jié)論；
　　 第