路圖及有向路圖的同構問題.pdf

1、線圖的概念最早是由Whitney在1932年提出的。在所有圖的變換中,線圖變換可能是研究最廣泛的一種變換了。Whitney證明了除K3和K1,3外,兩個連通圖的邊同構暗示了其點同構。關于線圖有很多推廣,例如：全圖,中間圖,團圖,三角圖,路圖和超線圖,等等。路圖的概念是在1989年由Broersma和Hoede提出的。與(無向)圖類似,Harary和Norman在1960年首先提出了有向線圖的概念。最近Broersma和Li將(無向)路圖

2、和有向線圖的概念推廣到了有向路圖。 本文主要研究路圖及有向路圖的同構問題。令Pk和Ck分別表示一條k個頂點的路和一個k個頂點的圈?！莐(G)表示G中所有k個頂點的路的集合(k≥1)。一個圖G的路圖Pk(G),其頂點集是∏k(G),而邊是連接這樣成對的頂點：在G中它們代表兩條路Pk且這兩條路的并是一條路Pk+1或一個圈Ck。有向路圖可以類似地定義。令→Pk和→Ck分別表示一條k個頂點的有向路和一個k個頂點的有向圈?！莐(D)表示

3、有向圖D中所有→Pk的集合。一個有向圖D的有向路圖→Pk(D),其頂點集是→∏k(D);pg是→Pk(D)的一條弧當且僅當在D中有一條有向路→Pk+1或一個有向圈→Ckv1v2…vk+1(當情況是→Ck時v1=vk+1)使得p=v1v2…vk和q=v2…vkvk+1。事實上,P2(G)和→P2(D)恰好分別是線圖L(G)和有向線圖→L(D)。 本論文由兩部分組成。第一部分主要研究(無向)路圖的同構問題,而第二部分主要研究有向路圖

4、的同構問題。 第一部分由第二,第三和第四章組成。在第二章中,我們主要考慮論文"Broersma and Hoede,Path graphs,J.Graph Theory 13(1989)427-444”中的一個公開問題,即是否存在一組三個互不同構的連通圖但它們有同構的連通P3-圖。我們證明了這樣的三元組不存在。 對于一個圖的變換,存在著一個普遍問題,即判定問題。對于Pk-變換,其判定問題是判定哪些圖的Pk-圖是給定的圖。

5、當k=2,3時,這個問題已經被完全解決了。對于線圖,Whitney證明了K3和K1,3是唯一的一對其線圖相同但本身并不同構的連通圖。當k=3時,Aldred,Ellingham,Hemminger和Jipsen完全刻畫了圖的所有P3-同構,即具有同構P3-圖的兩個圖或者同構,或者是三個特殊圖類之一。當k=4時,Li和Zhao首先證明了對所有最小度至少是4的圖,P4-變換是一一對應的,后來他們又證明了這個結果對最小度至少是3且滿足另兩個條

6、件之一的圖也成立。事實上,這兩個結果僅對度數(shù)較高的圖成立。在第三和第四章中,我們主要考慮P4-變換的判定問題。在第三章中,我們證明了對所有最小度至少是3的圖,P4-變換是一一對應的,且除一族特殊圖(標記為H)外,兩個圖之間的任意P4-同構都可以由其點同構導出。這個P4-圖的結論與線圖中Whitney的結論是十分相似的。同時這個結論也暗示了所有的非導出P4-同構只取決于最小度至多是3的圖。 在第四章中,我們主要考慮兩個圖之間的非導

7、出同構。除H這族圖外,我們又發(fā)現(xiàn)了幾對其P4-圖同構但本身并不同構的連通圖,還有大量的由兩個最小度為1或者2的同構圖產生的非導出的P4-同構。 第二部分是第五章,在這章中我們主要考慮有向→P3-圖的判定問題,即判定哪些有向圖的有向→P3-圖是給定的有向圖。唯一的結果是由Broersma和Li證明了具有同構有向→P3-圖的兩個有向圖是“幾乎”同構的。在這章中,首先我們對于有向圖D引進了一個算子"C",它包含了D上的很多復雜運算但它