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

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

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