相交圖論的若干問題.pdf

1、如果一個圖的每一個頂點都可以與一個集合族s中的一個集合相對應,使得兩個頂點相鄰當且僅當他們對應的集合相交非空,那么就稱該圖是s的相交圖.相交圖的應用背景涉及計算機,生物,矩陣分析,統(tǒng)計學等多個領(lǐng)域.而由于它的廣泛應用性使得相交圖理論在最近二三十年間得到了迅速的發(fā)展.本文正是針對相交圖理論中的一些問題進行研究和探討.主要討論了在不同條件限制下的最節(jié)省的相交表示,相交數(shù)及表示的唯一性問題.并對一些重要的相交圖類的性質(zhì)進行了刻劃. 本

2、文的工作分為六部分. 第一部分是概述.主要講述了相交圖理論的研究背景和發(fā)展現(xiàn)狀,并介紹了本文的主要工作. 第二部分主要針對沒有條件限制的最節(jié)省的相交表示問題進行了研究.求任意一個圖的相交數(shù)的問題是一個NP一難的問題[54].我們可以通過分數(shù)相交數(shù)if(G)對相交數(shù)i(G)進行估計,并且對滿足i(G)=if(G)的圖類可以在多項式時間內(nèi)找出它們的相交數(shù)的值.Scheinerrnan and nenk[91]證明了如果一個圖

3、是弦圖,那么i(G)=if(G).本文推廣了他們的結(jié)果,證明了如果一個圖G的邊團圖是θ-弱完美的那么i(G):if(G).作為應用本文進一步從不同的角度對一些滿足邊團圖是θ-弱完美的圖類的性質(zhì)進行了刻劃,并且對它們之間的層次關(guān)系進行了描述.本文中還提出了一個貪婪算法,對任意的圖都可以通過該算法找到它的一個相交表示.并且本文還證明對一些相交圖類,如不受菱形約束的消去圖等,都可以通過該算法在多項式時間內(nèi)找到它們的最小相交表示. 第三

4、部分是對有條件限制的最節(jié)省的相交表示問題進行研究.本文分別給出了異相交數(shù)和Helly異相交數(shù)的一個下確界.并對取到最小確界的極值圖的性質(zhì)進行了刻劃. 第四部分對一些圖類的唯一可表性進行了討論,特別是上一部分中提到的極值圖的唯一可表性.這是對Mahadev and Wang[59]關(guān)于唯一可表性結(jié)果的推廣. 第五部分中通過引入頂點集合的一種線性排序,本文對探針區(qū)間圖的性質(zhì)進行了刻劃.并給出了STS-探針區(qū)間圖的兩個線性時間