圖包含指定長度的圈和泛弧問題的研究.pdf

1、圖論的研究已有200多年的歷史。圖論起源于1736年Euler發(fā)表的一篇論文，他用圖論的方法解決了哥尼斯堡(Konigsberg)七橋問題。自二十世紀(jì)六十年代以來，圖論得到迅速發(fā)展，涌現(xiàn)了大量結(jié)果。圖論中有很多著名問題，如歐拉圖問題，哈密頓圈問題，中國郵遞員問題，四色定理等。應(yīng)用圖論來解決運(yùn)籌學(xué)，物理學(xué)，化學(xué)，生物學(xué)，計(jì)算機(jī)網(wǎng)絡(luò)，信息論和博弈論等學(xué)科問題，已經(jīng)顯示出極大的優(yōu)越性。圖論作為離散數(shù)學(xué)和組合數(shù)學(xué)的一個(gè)重要分支，受到了各方面的普

2、遍重視。
　　 本文只考慮簡單有限圖，這些圖不包含環(huán)和重邊，并且只有有限個(gè)頂點(diǎn)和邊。設(shè)G是一個(gè)頂點(diǎn)數(shù)為n的圖，H是一個(gè)頂點(diǎn)數(shù)為h的圖，其中n和h是正整數(shù)。圖論中的包裝問題是指，在圖G中找到盡可能多的點(diǎn)不相交的同構(gòu)與H的子圖。圖G的H-因子是圖G的-個(gè)子圖，它由[n/h]個(gè)同構(gòu)與H的子圖組成。特別地，圖G的k-因子指的是圖G中的k-正則子圖，其中k是正整數(shù)。在日常生活中，很多優(yōu)化問題和網(wǎng)絡(luò)問題，諸如編碼設(shè)計(jì)，積木設(shè)計(jì)，生物DNA分

3、子結(jié)構(gòu)分析，進(jìn)度表等關(guān)于運(yùn)籌和網(wǎng)絡(luò)設(shè)計(jì)問題都涉及到圖的因子和因子分解。本文主要研究2-因子問題。一個(gè)圈稱為k-圈，如果它恰好包含k個(gè)頂點(diǎn)；類似地，一條路稱為k-路，如果它恰好包含k個(gè)頂點(diǎn)。圖中包含每個(gè)頂點(diǎn)的圈，稱為圖的哈密頓圈。顯然，一個(gè)哈密頓圈可以被看成是僅有一個(gè)分支的2-因子。1952年，G.Dirac給出了圖包含哈密頓圈的最小度條件。1960年，0.Ore給出了圖包含哈密頓圈的最小度和條件。這兩個(gè)結(jié)果可被認(rèn)為是2-因子問題的先驅(qū)。

4、對(duì)于一個(gè)給定的圖，找到2-因子存在性的條件是很困難的。常用的技巧是先找出一個(gè)頂點(diǎn)數(shù)目極小的包裝，然后擴(kuò)充成為2-因子。
　　 本文研究了圖論中的幾個(gè)問題，具體地，我們研究了圖中點(diǎn)不相交的子圖(主要是圈和路)及2-因子的存在性問題，有向圖中泛弧的存在性問題。圖的點(diǎn)不相交圈問題可以概括為：最小度(或者度和)滿足什么條件時(shí)，圖包含一個(gè)2-因子?進(jìn)一步地，從這些條件中，我們能否確定2-因子中圈的數(shù)目或者圈的長度?上述問題是極值圖論中的基

5、本問題。本文中，我們利用最小度與最小度和條件研究了圖包含4-圈、6-圈和8-圈的問題。一條弧e稱為有向圖D的泛弧，如果對(duì)于任意的點(diǎn)χ∈V(D)，存在一個(gè)包含弧e和點(diǎn)x的圈。顯然，如果有向圖包含一個(gè)哈密頓圈，則哈密頓圈的每一條弧都是泛弧。我們利用最小度條件研究了強(qiáng)連通多部競賽圖和圈連通多部競賽圖包含泛弧的問題。全文共分為五章。
　　 在第一章中，我們給出了一個(gè)簡短而完整的引言。首先我們列出了本文中會(huì)用到的所有術(shù)語和符號(hào)，然后我們介

6、紹了圖中點(diǎn)不相交的子圖和指定長度的圈的研究背景和進(jìn)展。緊接著，我們介紹了有向圖中泛弧問題的研究進(jìn)展。最后，我們列出了本文的主要結(jié)果。
　　 在第二章中，我們給出了圖包含點(diǎn)不相交4-圈的度條件。首先我們定義兩類圖：M(k1，k2)=K4k1+2UK4k2+2和N(k1，k1)=K4k1+1UK4k2+3，其中k1，k2是非負(fù)整數(shù)。設(shè)G是一個(gè)無爪圖，頂點(diǎn)數(shù)為｜G｜=4k，其中k是-個(gè)正整數(shù)。如果圖G的最小度和σ2(G)至少為4k-2

7、，我們證明了圖G包含k-1個(gè)點(diǎn)不相交的4-圈和一條4-路，使得所有這些圈和路是點(diǎn)不相交的，除非G同構(gòu)與M(k1，k2)或N(k1，k2)，其中k1≥0，k2≥0，k1+k2=k-1。我們給出反例，說明了結(jié)論的度條件是最好的，而且無爪圖的要求是必需的。緊接著，我們給出了二部圖包含4-圈的度條件。設(shè)G=(V1，V2；E)是一個(gè)二部圖，滿足｜V1｜=｜V2｜=2k，其中k>0是一個(gè)正整數(shù)。假設(shè)對(duì)于任意的χ∈V1，y∈V2，χy()E(G)，d

8、(χ)+d(y)≥3k，我們證明了G包含k個(gè)點(diǎn)不相交的4-圈。
　　 在第三章中，我們研究了二部圖包含點(diǎn)不相交6-圈的問題。設(shè)G=(V2，V2；E)是一個(gè)二部圖，滿足｜V1｜=｜V2｜=3k，其中k是一個(gè)正整數(shù)。我們首先利用最小度條件證明了，如果最小度大于等于2k，則圖G或者包含k個(gè)點(diǎn)不相交的6-圈，或者包含k-1個(gè)點(diǎn)不相交的6-圈和一個(gè)4-圈，它們點(diǎn)不相交。緊接著，我們探討了二部圖包含點(diǎn)不相交6-圈的度和條件。設(shè)G=(V1，V

9、2；E)是-個(gè)二部圖，滿足｜V1｜=｜V2｜=3k，其中k是-個(gè)正整數(shù)。我們證明了，如果對(duì)于任意的χ∈V1，y∈V2，χy()E(G)，d(χ)+d(y)≥4k-1，則圖G有一個(gè)支撐子圖包含k-1個(gè)點(diǎn)不相交的6-圈和一條6-路，它們彼此點(diǎn)不相交；如果k>2，并且對(duì)于任意的χ∈V1，y∈V2，χy()E(G)，d(χ)+d(y)≥4k，則圖G有一個(gè)支撐子圖包含k-2個(gè)點(diǎn)不相交的6-圈和一個(gè)12-圈，它們彼此點(diǎn)不相交。
　　 在第四

10、章中，我們給出了二部圖包含帶弦8-圈的度條件。首先，我們找到了二部圖的一個(gè)2-因子，它的每個(gè)分支都是8-圈，然后通過調(diào)整邊，使得每個(gè)8-圈至少包含兩條弦。我們的結(jié)果如下：設(shè)G=(V1，V2；E)是一個(gè)二部圖，滿足｜V1｜=｜V2｜=4k，其中k是一個(gè)正整數(shù)。如果G的最小度δ(G)≥3k+1，則圖G包含k個(gè)點(diǎn)不相交的8-圈，使得每個(gè)8-圈至少包含兩條弦。
　　 最后，在第五章，我們研究了有向圖中的泛弧問題。對(duì)于任意最小度δ≥2的強(qiáng)