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

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

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

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

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

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

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

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

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

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

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