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

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

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

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

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

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

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

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

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

9、第四章討論了在給出一定色度與彩色圍長(zhǎng)的條件下，邊染色圖中存在的彩色路問(wèn)題. 下面，我們將列出本文的主要結(jié)論如下： 定理2.1.7.設(shè)G=（V1，V2；E）是一個(gè)平衡二分圖，并且|V1|=|V2|=2k，k≥3.如果δ（G）≥k+2，則G可以劃分為兩個(gè)6-圈和k-3個(gè)4-圈，并且這k-1個(gè)圈點(diǎn)不相交. 定理3.2.1.設(shè)G是具有n個(gè)頂點(diǎn)（n≥3）的邊染色圖，對(duì)任意υ∈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，如果對(duì)所有υ∈V（G）都有dc（υ）≥d成立，則G中存在長(zhǎng)至少為「kd/k+1」的彩色路. 定理4.3.1.設(shè)圖G為邊染色圖，且對(duì)任意υ∈V（G），dc（υ）≥d.如果圖G中不存在彩色圈，則G中存在長(zhǎng)至少為d的彩色路. 定理4.3.2.設(shè)圖G為邊染色圖，gc（G）≥k+1，其中k≥