路圖及有向路圖的同構(gòu)問題.pdf

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

2、和有向線圖的概念推廣到了有向路圖。 本文主要研究路圖及有向路圖的同構(gòu)問題。令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āng)且僅當(dāng)在D中有一條有向路→Pk+1或一個有向圈→Ckv1v2…vk+1(當(dāng)情況是→Ck時v1=vk+1)使得p=v1v2…vk和q=v2…vkvk+1。事實上,P2(G)和→P2(D)恰好分別是線圖L(G)和有向線圖→L(D)。 本論文由兩部分組成。第一部分主要研究(無向)路圖的同構(gòu)問題,而第二部分主要研究有向路圖

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

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

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

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