圖中的若干極值問題.pdf

1、令u1，u2，…，um是Rn中的向量。對于λi∈R，λi≥0，m∑i=1λi=1，u=λ1u1+λ2u2+…+λmum被稱為是{u1，u2，…，um)的凸組合。[u1，u2，…，um}所有凸組合的集合就是{u1，u2，…，um)的一個凸包。在Rn中的有限個向量的集合X的凸包被稱為是一個多面體，并且用P來表示。一個多面體P的頂點(diǎn)是多面體的零維面，并且P中的兩個頂點(diǎn)u和v相鄰當(dāng)且僅當(dāng)它們是多面體的同一個一維面中的點(diǎn)。一個多面體P的圖(或者骨

2、架)G(P)是一個圖，它的頂點(diǎn)是多面體的頂點(diǎn)，并且它有一條邊連接一對頂點(diǎn)，如果對應(yīng)于多面體的這對頂點(diǎn)是相鄰的，也就是這對頂點(diǎn)被多面體的一條邊所連。這類圖的研究已經(jīng)有較長的歷史。一個多面體稱為是(0，1)多面體，如果它的頂點(diǎn)所對應(yīng)的向量的每個分量都是0、或者1。在1984年，Naddef和Pulleyblank證明了如果一個(0，1)多面體的骨架G(P)是一個二部圖，那么G(P)是一個超立方體；如果G(P)是非二部圖，那么G(P)是哈密頓

3、連通的。這類(0，1)多面體包含很多著名的多面體，如：匹配多面體、擬陣基多面體、穩(wěn)定集多面體和置換多面體。我們研究了完美匹配多面體的若干極值問題。 人們對具有完美匹配的圖已經(jīng)做過大量的研究，其最基本的結(jié)果是在1947年，Tutte所給出的對具有完美匹配的圖的一個刻畫。最近，為了研究具有完美匹配的圖的Tutte集(或者barrier)和極端集，Bauer，Broersma，Morgana和Schmeichel提出了一種新的圖運(yùn)算被

4、稱為D—圖，并且得到了很多有趣的性質(zhì)。圖G的水平是一個最小的整數(shù)κ≥0使得Dκ+1(G)≌Dκ(G)，這里取D0(G)=G。我們主要研究了若干圖類的水平，并且給出了幾類特殊圖類的D—圖的刻畫。在匹配理論中，完美匹配的計數(shù)也是匹配理論的一個重要的研究方向。我們研究了幾類多邊形Cacti鏈的匹配和獨(dú)立集，并且確定了關(guān)于κ—匹配和κ—獨(dú)立集的多邊形Cacti鏈的極值鏈。Wiener數(shù)是理論化學(xué)研究中的一個重要參數(shù)，我們研究了樹狀多聯(lián)苯的Wie

5、ner數(shù)。 這篇論文分為六章。 在第一章，我們首先介紹了圖和匹配的一些相關(guān)定義和概念。其次，我們概述了匹配理論新近的一些主要結(jié)果和發(fā)展現(xiàn)狀。第三，我們概述了Wiener數(shù)的理論背景及其主要結(jié)果。在這章的最后，我們列舉了本文的主要研究成果。 在第二章，我們給出了完美匹配圖是二部圖的二部圖的刻畫。得到了這類圖關(guān)于邊的一個緊的上界，并且構(gòu)造了達(dá)到此上界的極值圖類。 在第三章，我們給出了完美匹配圖是二部圖的非二部

6、圖的刻畫。得到了這類圖關(guān)于邊的一個緊的上界，并且構(gòu)造了達(dá)到此上界的極值圖類。 在第四章，我們首先研究了基本圖的水平，并且證明了對于任意一個非二部圖的基本圖，它的D2(G)是一個完全圖。此外，我們還給出了飽和圖的D-圖的刻畫，對于非二部圖的情形給出了一個例子。第二，根據(jù)二部圖的典型分解，我們給出了二部圖的D-圖的精確構(gòu)造，并分別給出了level=0和level=1的二部圖的刻畫。最后，我們給出了level=0的具有唯一完美匹配的飽

7、和圖的D—圖的刻畫以及這類圖的邊數(shù)的一個緊的上界。 在第五章，我們考慮了幾類多邊形Cacti鏈，并研究了他們的匹配和獨(dú)立集，明確給出了這幾類多邊形Cacti鏈的匹配和獨(dú)立集多項(xiàng)式的遞推式以及若干特殊值的虧d-匹配數(shù)。另外，我們確定了關(guān)于κ-匹配和κ-獨(dú)立集的多邊形Cacti鏈的極值鏈。最后，我們明確給出具有n個多邊形的星形多邊形Cacti鏈的匹配和獨(dú)立集多項(xiàng)式。 在最后一章，我們確定了所有具有h個六邊形的最大和最小Wie