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

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

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

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