圖中圈和路的相關(guān)結(jié)論.pdf

1、圖論的研究開始于200多年前，關(guān)于圖論的第一篇論文是1736年Euler發(fā)表的，他用圖論的方法解決了格尼斯堡（Konigsberg）七橋問題.二十世紀(jì)六十年代以來，圖論在科學(xué)界異軍突起，活躍非凡.圖論中也有很多著名的問題，如哈密爾頓問題，中國郵寄員問題，四色問題等等.應(yīng)用圖論來解決物理學(xué)、化學(xué)、生物學(xué)、信息與計算機科學(xué)以及社會科學(xué)等學(xué)科問題已顯示出極大的優(yōu)越性.圖的圈和路理論是圖論研究中的一個重要分支，在圖論乃至整個離散數(shù)學(xué)領(lǐng)域中占有非

2、常重要的地位，其實際應(yīng)用也越來越廣泛，在日常生活中，許多優(yōu)化問題和網(wǎng)絡(luò)問題諸如計算機網(wǎng)絡(luò)中的文件傳輸問題，時間表問題等等都涉及到圖的圈和路理論。本文我們主要研究圖中的圈和路問題. 本文考慮的圖若無特殊聲明均為簡單、無向有限圖，設(shè)G是一個具有頂點集V（G）和邊集E（G）的圖.對υ∈V（G），υ在G中的度用dG（υ）表示.我們用NG（υ）表示在G中與υ相鄰的頂點集合，NG[υ]表示NG（u）∪{υ}，△（G）和δ（G）分別表示圖G的

3、最大度和最小度，在不引起混淆的情況下簡記為△和δ.對于圖G，我們用|G|=|V（G）|表示G的階數(shù)，即G的頂點數(shù)。 對于一個圖G，若G的每條邊都染上顏色C，則稱G為邊染色圖，記作（G，C）給定—個邊染色圖G，關(guān)聯(lián)于頂點υ的不同顏色邊的數(shù)目，稱為頂點υ的色度，記為dc（υ）如果把一般的未染色圖看作是每條邊都染不同顏色的邊染色圖，則頂點的色度就等于它的度.除了在圖論和算法上的重要應(yīng)用外，邊染色圖中的許多問題還出現(xiàn)在遺傳學(xué)，心理學(xué)和網(wǎng)

4、絡(luò)理論等其它領(lǐng)域中.因此，這方面的研究近幾年變得活躍起來.主要集中在邊染色圖中某些特殊子圖的存在性上.邊染色圖中的子圖，如果任意相鄰的兩條邊的顏色都不相同，我們稱之為邊正常染色子圖，或者稱為交錯子圖.進(jìn)一步，如果該子圖中所有邊的顏色都不相同，我們稱之為彩色子圖.這兩類子圖的研究尤其受到關(guān)注.圈和路是圖論中的基礎(chǔ)研究領(lǐng)域，因此邊染色圖中的彩色圈和路就成了一個重要的研究方向. 圖G中過每個頂點的圈，稱為圖G的哈密爾頓圈.圖的哈密爾頓

5、圈問題是圖論中的一個經(jīng)典問題.G的一個2-因子是G的一個2-正則支撐子圖，易見2-因子的每一個連通分支為一個圈.圖的k個獨立圈是指G中k個頂點不相交的圈.同樣地、G的一個1-因子是G的一個1-正則支撐子圖，通常我們稱1-因子為完美對集或完美匹配.顯然G的一個1-因子是覆蓋G的所有頂點的一個邊集合.圖的一個路因子就是指每一個分支都是一條路的一個生成子圖，對于圖G中的一條路P和一個圈C，定義路和圈的長度分別為：l（P）=|V（P）|-1，l

6、（C）=|V（C）|.對圖的因子的研究始于一百多年以前.1859年，Reiss證明了K2n圖可分解為1-因子.1891年，J.Peterson證明了任意偶數(shù)度圖可以分解成邊不交2-因子的并，而且它證明了每一個2-連通3-正則圖都有一個1-因子.這兩個結(jié)果被認(rèn)為是現(xiàn)代圖因子理論的開端.圖的獨立圈、2-因子和路因子問題是圖的因子理論中非常重要的一部分，也是圖的哈密頓圈理論的推廣和延伸.它是圖論中非常有趣的一類問題，也是國內(nèi)外研究的熱門課題，

7、其理論研究主要集中在以下幾個方面：圖中含指定個數(shù)的獨立圈和2-因子；含指定長度的獨立圈和2-因子；圖中具有指定性質(zhì)的獨立圈和2-因子；具有指定性質(zhì)的路因子等等. 針對圖中大量涌現(xiàn)出的圈和路的可喜結(jié)果，我們很自然的會問：這些定理可以推廣到邊染色圖中的彩色圈和彩色路上嗎？由于邊染色圖中的彩色子圖研究起來比較困難，到目前為止關(guān)于其研究結(jié)果還比較少，且絕大部分結(jié)果都是類Ramsey的，這就意味著這些結(jié)果大多只研究了邊染色完全圖中的情況.

8、 全文共分四章，主要討論了三個方面的問題：（1）平衡二部圖中的2-因子問題；（2）邊染色圖中的彩色圍長問題；（3）邊染色圖中的彩色路問題. 第一章簡單介紹了圖論的基本概念，簡潔綜述了圖中圈和路理論的歷史和發(fā)展?fàn)顩r以及已有的一些與本文相關(guān)的結(jié)果，這一章是其余各章的基礎(chǔ).第二章首先介紹了平衡二部圖中的2-因子問題已有的較好結(jié)果；討論了含4k個頂點的二部圖中的圈結(jié)構(gòu)和度條件問題.第三章給出了邊染色圖中色度與彩色圍長的一種關(guān)系.

9、第四章討論了在給出一定色度與彩色圍長的條件下，邊染色圖中存在的彩色路問題. 下面，我們將列出本文的主要結(jié)論如下： 定理2.1.7.設(shè)G=（V1，V2；E）是一個平衡二分圖，并且|V1|=|V2|=2k，k≥3.如果δ（G）≥k+2，則G可以劃分為兩個6-圈和k-3個4-圈，并且這k-1個圈點不相交. 定理3.2.1.設(shè)G是具有n個頂點（n≥3）的邊染色圖，對任意υ∈V（G），如果dc（υ）≥n/2-α，其中α=（

10、3/s-3ln2+√7/3），s>3且s∈N，則有g(shù)c（G）≤s. 定理4.1.6.設(shè)圖G為gc（G）≥k+1的邊染色圖，其中k≥3，如果對所有υ∈V（G）都有dc（υ）≥d成立，則G中存在長至少為「kd/k+1」的彩色路. 定理4.3.1.設(shè)圖G為邊染色圖，且對任意υ∈V（G），dc（υ）≥d.如果圖G中不存在彩色圈，則G中存在長至少為d的彩色路. 定理4.3.2.設(shè)圖G為邊染色圖，gc（G）≥k+1，其中k≥