圖論中的組合方法和概率方法.pdf

1、一個圖如果其性質(zhì)如頂點、邊或者頂點與邊之間的關(guān)系具有隨機性，我們通常稱之為隨機圖．隨機圖理論創(chuàng)始于Erd(o)s與Rényi在上個世紀50年代末60年代初發(fā)表的一系列論文，他們發(fā)現(xiàn)概率方法在處理圖論的某些問題時非常有用．現(xiàn)在，隨機圖理論在很多方面都有一些很漂亮的結(jié)果，如隨機圖的進化過程、極限分布、子圖理論、極圖理論以及Ramsey理論等等。作為離散數(shù)學的一個重要分支，隨機圖在其他學科，如計算機科學、化學、社會學及生物學等都有廣泛的應(yīng)用。

2、另一方面，概率理論也已經(jīng)成為圖論研究的一種越來越重要的工具． 本篇論文主要包括三個部分：第一部分是序言(第1章)，第二部分我們主要是研究隨機多重圖和隨機超圖的度序列的分布問題(第2，3，4章)，第三部分我們主要研究關(guān)于邊染色超圖的彩色的哈密頓圈和H-因子問題(第5，6章)。 在本文中，如果在一個隨機圖模型中，一個圖性質(zhì)Q滿足limn→∞P{Q}=1，那么我們就說在該空間中幾乎所有的圖都具有性質(zhì)Q． 假設(shè)n是一個自

3、然數(shù)，r是一個固定的自然數(shù)，ni=ni(n)(1≤i≤r)是一系列關(guān)于n的非負整值函數(shù)且滿足n1+n2+…+nr=n．作為經(jīng)典隨機二部圖的的一種推廣，隨機r一致r部隨機超圖模型H(n1，n2，．．．，nr；n，p)定義如下： (i)樣本空間由所有具有頂點劃分V={V1，V2，．．．，Vr}且每條(超)邊恰好有一個端點落在Vi(1≤i≤r)的r一致r部超圖組成； (ii)пTi=1ni條邊中的每一條邊被選取構(gòu)成超圖的概率是

4、p(0＜p＜1)，且不同邊的選取互相獨立。 在第二章，我們研究了隨機r一致r部隨機超圖模型H(n1，n2，．．．，nr；n，p)中的隨機超圖在V1中的度序列的分布問題。 △V1=△V1(H)和δV1=δV1(G)分別表示圖H在V1中的最大度和最小度；Xd，V1=Xd，V1(H)，Yd，V1=Yd，V1(H)，Zd，V1，=Zd，V1(h)和Zc，d，V1=Zc，d，V1(H)分別表示圖H在V1中度為d，度大于或等于d，度

5、小于或等于d，和度大于或等于c且小于或等于d的頂點數(shù)目。 在第二章，我們證明在隨機r—致r部隨機超圖空間H(n1，n2，．．．，nr；n，p)中，隨機變量Xd，V1，Yd，V1，Zd，V1及Zc，d，V1都近似服從Poisson分布．另一方面，我么也考慮了下面兩個問題： (i)當p滿足什么條件時，我們能找到一個關(guān)于n的整值函數(shù)D(n)使得在空間H(n1，n2，．．．，nr；n，p)中，limn→∞P{△V1=D(n)}=

6、1? (ii)當p滿足什么條件時，在空間H(n1，n2，．．．，nr；n，p)中，幾乎所有的超圖在V1的最大度頂點是唯一的? 我們證明了第一個問題的答案是p=o(logn1/N)，而第二個問題的答案是Np/logn1→∞．假設(shè)d1，V1(H)≥d2，V1，(H)≥．．．≥dn1，V1(H)是H在V1的度序列。考慮完度序列中最大度和最小度的情況之后，我們考慮了度序列中一般元素di，V1的分布問題，另外我們還對di，V1—d

7、i+1，V1給出了一個估計。 在第三章，我們把經(jīng)典二項隨機圖模型推廣到多重隨機圖模型g(n；{pκ})，定義如下： (i)樣本空間由所有以V={u1，u2，．．．，un}為頂點集的無自同環(huán)多重圖組成； (ii)若用隨機變量tui，uj(1≤i＜j≤n)表示頂點ui與uj之間存在的邊數(shù)。則tui，uj(1≤i＜j≤n)相互獨立，且服從同分布： P{tui，uj=κ}=pκ，κ=0，1，2，．．．其中pκ≥0

8、且∑∞κ=0Pκ=1． 首先，我們給出了在空間g(n;{pκ})中多重圖的度序列近似服從Poisson分布的一個充分條件。然后，為了改進這個結(jié)果，我們還分別考查了當{pκ)服從幾何分布、二項分布及Poisson分布的情況，并給出了充要條件。 在第四章，我們把經(jīng)典隨機二部圖模型推廣到隨機多重二部圖模型g(n，m；{pκ})，定義如下： (i)樣本空間由所有以A∪B為頂點集的無自同環(huán)多重二部圖組成，其中A={a1，a

9、2，．．．，an}，B={b1，62，．．．，bm}； (ii)若用隨機變量tai，bj(1≤i≤n，1≤j≤m)表示頂點ai與bj之間存在的邊數(shù)。則tai，bj(1≤i≤n，1≤j≤m)相互獨立，且服從同分布：P{tai，bj=κ}=pκ，κ=0，1，2，．．．其中pκ≥0且∑∞κ=0pκ=1．在這一章我們得到一些類似于第二章的結(jié)果。 另一方面，圖的染色理論在圖論中占很重要的地位。近年來，對圖的染色問題的研究變得異常活

10、躍，得到了一系列漂亮的結(jié)果，也產(chǎn)生了很多新的研究方法，其中包括概率方法。在第5，6章我們考慮了邊染色超圖中的彩色H-因子和彩色哈密頓圈問題。 我們說一個邊染色子圖是彩色的，如果該子圖的任意兩條邊的顏色都不一樣．假設(shè)H是圖G的一個子圖，我們稱G的一個滿足每個連通分支都同構(gòu)于H的生成子圖為G的一個H-因子，且如果每個連通分支都是彩色的日，那么我們就稱之為G的一個彩色H—因子． 在第五章，我們用概率方法證明了如果一個具有n個頂

11、點的完全3一致超圖K(3)n的邊染色滿足任意一種顏色出現(xiàn)的次數(shù)不超過「cn」次，則該染色包含一個每一條邊顏色都不一樣的哈密頓圈，其中c是滿足c＜1/1152的任意常數(shù)。 在第六章，我們用概率方法證明了如果h，r和s是正整數(shù)且滿足s≤r≤h，H是具有h個頂點且滿足X(H)=r的s一致超圖，那么我們可以找到一個常數(shù)κ=κ(h，r，s)使得任何正常邊染色的超圖Ts，r(κ)都包含一個每條邊顏色都不一樣的彩色的H—因子，其中Ts，r(κ