重構猜想(英語:Reconstruction Conjecture),圖論中的重構猜想,認為一個圖能夠由它的子圖唯一決定。此猜想由PAUL J. KELLY[1]斯塔尼斯拉夫·烏拉姆[2][3]共同提出。

正式陳述

編輯

給定圖  , 其 頂點子圖(英文:vertex-deleted subgraph)是在 中刪除了一個頂點得到的子圖. 根據定義, 它是圖  導出子圖

對於圖 , 其deck, 記作 ,是由 的所有頂點子圖的同構類所組成的多重集 中的每一個圖被叫做一張 card。兩個擁有相同deck的圖被稱作彼此hypomorphic

在給了以上的定義後,重構猜想可以表述為:

  • 重構猜想: 任何兩個頂點數大於等於3的彼此hypomorphic的圖是同構的。
(這裡要求兩個圖的頂點數大於等於3是必要的,因為頂點數為2的圖本就有相同的deck)

Harary[4] 提出了一個更強的假設:

  • 頂點重構猜想Set Reconstruction Conjecture: 對任意兩個頂點數大於等於4的圖,若它們的頂點子圖均相等,則它們是同構的。

給定圖 , 其 邊子圖(英文:edge-deleted subgraph)是在 中刪除了一條邊得到的子圖an edge-deleted subgraph of  

對於圖 , 其edge-deck, 記作 ,是由 的所有邊子圖的同構類所組成的多重集 中的每一個圖被叫做一張 edge-card

  • 邊重構猜想 Edge Reconstruction Conjecture: (Harary, 1964)[4] 對對任意兩個邊的個數大於等於4的圖,若它們的邊子圖均相等,則它們是同構的。

可識別的屬性

編輯

在重構猜想中,一個圖屬性被稱作 可識別的如果它可以被圖的deck確定。以下的這些屬性是可識別的:

  • 圖的階數 – 圖 的階數,  , 可以從 中識別,因為 多重集  包含了每一個從  中刪除一個頂點的子圖,因此  [5]
  • 圖的邊數 – 階數為 的圖 的邊的個數 ,  ,是可識別的。首先要注意到, 中的每一條邊會在   個圖中出現。其原因是:根據 的定義,每次構造頂點子圖時,當刪掉的頂點並不是這條邊的端點時,它就會在這個頂點子圖中出現,因此它會出現 次。根據以上這個觀察,  ,其中  中第i個圖的邊的個數。[5]
  • 度序列 – 圖  的度序列是可識別的,因為每一個頂點的度都是可識別的。為了找到vertex  的度,我們研究刪除這個頂點之後的圖,  。它包含了所有不和 相接的邊,故如果  中邊的個數,則  [5]
  • 邊連通性 –根據定義,圖   -邊連通的如果刪除任意一個頂點可以導出一個  -邊連通圖;因此,如果每一個card都是一個 -邊連通圖,我們知道原圖是 -邊連通圖。 我們也可以確定原圖是否是連通的,因為這等價於任意兩個 是連通的。[5]

驗證情況

編輯

重構猜想和頂點重構猜想在圖的階數小於等於11的情況下均已被Brendan McKay[6]驗證。

Béla Bollobás提出,在概率意義下幾乎所有的圖都是可重構的。 [7] ,這意味着隨着圖的階數 趨於無窮,一個隨機選擇的階數為 的圖不能被重構的概率趨於0。事實上,可以證明不僅幾乎所有的圖重構的,而且重構它們並不需要整個deck,幾乎所有的圖都可以被deck中的3張card來決定。

可重構的圖

編輯

重構猜想已經在一些種類的圖上被驗證。

  • 正則圖[8] - 通過直接應用一些能夠被deck識別的屬性,可以證明正則圖是可重構的。給定一個  -正則圖 以及它的deck  ,我們可以通過識別每個頂點的度來識別圖的正則性。我們觀察  中的一個圖,  。 它有一些度為 的頂點和 個度為 的頂點. 通過增加一個頂點,將其 個度為 的頂點相連,可以構造一個  -正則圖, 該圖與圖 同構。因此,所有的正則圖都可以被它們的deck重構。一類特殊的正則圖是完全圖。[5]

猜想的規約

編輯

如果所有的2-conected圖都是可重構的,則重構猜想正確。 [11]


對偶性

編輯

頂點重構定理有一定的對偶性質,如果  可重構,則其補  可以以如下方式被 重構:從 中取出所有的card,分別取補得到 ,用它來重構  ,再取補得到 

邊重構定理並沒有這樣的對偶性質:事實上,對於某些類型的邊-可重構圖來說,我們並不知道它們的補能否被邊重構。

其他結構

編輯

以下的一些圖結構被證明在一般情況下都不能被重構:

  • 有向圖: 無數種不能被重構的有向圖已經被發現:其中包括tournaments (Stockmeyer[12]) 和 non-tournaments (Stockmeyer[13])。 如果一個tournament不是強連接(strongly connected),則是可重構的。[14] 一個針對有向圖的弱版本的重構猜想可以詳見new digraph reconstruction conjecture
  • 超圖 (Kocay[15]).
  • 無限圖-令無限圖T每個頂點的度都為無窮的樹,令nT 為n 個T 的disjoint union 。 這些圖相互hypomorphic,因此它們並不是可重構的。這些圖的任以頂點子圖都是同構的:它們都是無數個T的無交並。

另見

編輯

更多資料

編輯

更多關於重構猜想的內容詳見 Nash-Williams的綜述[16]

參考資料

編輯
  1. ^ Kelly, P. J., A congruence theorem for trees, Pacific J. Math. 7 (1957), 961–968.
  2. ^ Ulam, S. M., A collection of mathematical problems, Wiley, New York, 1960.
  3. ^ O'Neil, Peter V. Ulam's conjecture and graph reconstructions. Amer. Math. Monthly. 1970, 77: 35–43 [2020-04-06]. doi:10.2307/2316851. (原始內容存檔於2021-04-19). 
  4. ^ 4.0 4.1 Harary, F., On the reconstruction of a graph from a collection of subgraphs. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963). Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 47–52.
  5. ^ 5.0 5.1 5.2 5.3 5.4 Wall, Nicole. The Reconstruction Conjecture. 
  6. ^ McKay, B. D., Small graphs are reconstructible, Australas. J. Combin. 15 (1997), 123–126.
  7. ^ Bollobás, B., Almost every graph has reconstruction number three, J. Graph Theory 14 (1990), 1–4.
  8. ^ 8.0 8.1 8.2 Harary, F., A survey of the reconstruction conjecture, A survey of the reconstruction conjecture, Graphs and Combinatorics. Lecture Notes in Mathematics 406, Springer: 18–28, 1974, doi:10.1007/BFb0066431 
  9. ^ von Rimscha, M.: Reconstructibility and perfect graphs. Discrete Mathematics 47, 283–291 (1983)
  10. ^ Bondy, J.-A. On Ulam's conjecture for separable graphs. Pacific J. Math. 1969, 31: 281–288. doi:10.2140/pjm.1969.31.281. 
  11. ^ Yang Yongzhi:The reconstruction conjecture is true if all 2-connected graphs are reconstructible. Journal of graph theory 12, 237–243 (1988)
  12. ^ Stockmeyer, P. K., The falsity of the reconstruction conjecture for tournaments, J. Graph Theory 1 (1977), 19–25.
  13. ^ Stockmeyer, P. K., A census of non-reconstructable digraphs, I: six related families, J. Combin. Theory Ser. B 31 (1981), 232–239.
  14. ^ Harary, F. and Palmer, E., On the problem of reconstructing a tournament from sub-tournaments, Monatsh. Math. 71 (1967), 14–23.
  15. ^ Kocay, W. L., A family of nonreconstructible hypergraphs, J. Combin. Theory Ser. B 42 (1987), 46–63.
  16. ^ Nash-Williams, C. St. J. A., The Reconstruction Problem, in Selected topics in graph theory, 205–236 (1978).