重構猜想

未解決的數學問題：一個圖能夠被它的子圖唯一地決定嗎？

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

正式陳述

給定圖 $G=(V,E)$ , 其 頂點子圖（英文：vertex-deleted subgraph）是在 $G$ 中刪除了一個頂點得到的子圖. 根據定義, 它是圖 $G$ 的導出子圖。

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

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

重構猜想: 任何兩個頂點數大於等於3的彼此hypomorphic的圖是同構的。

(這裡要求兩個圖的頂點數大於等於3是必要的，因為頂點數為2的圖本就有相同的deck）

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

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

給定圖 $G=(V,E)$ , 其 邊子圖（英文：edge-deleted subgraph）是在 $G$ 中刪除了一條邊得到的子圖an edge-deleted subgraph of $G$

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

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

可識別的屬性

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

圖的階數 – 圖 $G$ 的階數, $|V(G)|$ ，可以從 $D(G)$ 中識別，因為多重集 $D(G)$ 包含了每一個從 $G$ 中刪除一個頂點的子圖，因此 $|V(G)|=|D(G)|$ ^[5]

圖的邊數 – 階數為 $n$ 的圖 $G$ 的邊的個數 , $|E(G)|$ ，是可識別的。首先要注意到， $G$ 中的每一條邊會在 $D(G)$ 中 $n-2$ 個圖中出現。其原因是：根據 $D(G)$ 的定義，每次構造頂點子圖時，當刪掉的頂點並不是這條邊的端點時，它就會在這個頂點子圖中出現，因此它會出現 $n-2$ 次。根據以上這個觀察， $|E(G)|=\sum {\frac {q_{i}}{n-2}}$ ，其中 $q_{i}$ 是 $D(G)$ 中第i個圖的邊的個數。^[5]

度序列 – 圖 $G$ 的度序列是可識別的，因為每一個頂點的度都是可識別的。為了找到vertex $v_{i}$ 的度，我們研究刪除這個頂點之後的圖, $G_{i}$ 。它包含了所有不和 $v_{i}$ 相接的邊，故如果 $q_{i}$ 是 $G_{i}$ 中邊的個數，則 $|E(G)|-q_{i}=\deg(v_{i})$ 。^[5]

邊連通性 –根據定義，圖 $G$ 是 $n$ -邊連通的如果刪除任意一個頂點可以導出一個 $n-1$ -邊連通圖；因此，如果每一個card都是一個 $n-1$ -邊連通圖，我們知道原圖是 $n$ -邊連通圖。我們也可以確定原圖是否是連通的，因為這等價於任意兩個 $G_{i}$ 是連通的。^[5]

驗證情況

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

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

可重構的圖

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

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

樹^[8]
不連通圖^[8]
Unit interval graph^[9]
Separable graphs without end vertices^[10]
極大平面圖
Maximal outerplanar graph
Outerplanar graph
Critical blocks

猜想的規約

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

對偶性

頂點重構定理有一定的對偶性質，如果 $G$ 可重構，則其補 $G'$ 可以以如下方式被 $D(G')$ 重構：從 $D(G')$ 中取出所有的card，分別取補得到 $D(G)$ ，用它來重構 $G$ ，再取補得到 $G'$ 。

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

其他結構

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

有向圖: 無數種不能被重構的有向圖已經被發現：其中包括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的無交並。

另見

參考資料

^ Kelly, P. J., A congruence theorem for trees, Pacific J. Math. 7 (1957), 961–968.
^ Ulam, S. M., A collection of mathematical problems, Wiley, New York, 1960.
^ 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.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.0 ^5.1 ^5.2 ^5.3 ^5.4 Wall, Nicole. The Reconstruction Conjecture. 缺少或|url=為空 (幫助)
^ McKay, B. D., Small graphs are reconstructible, Australas. J. Combin. 15 (1997), 123–126.
^ Bollobás, B., Almost every graph has reconstruction number three, J. Graph Theory 14 (1990), 1–4.
^ ^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
^ von Rimscha, M.: Reconstructibility and perfect graphs. Discrete Mathematics 47, 283–291 (1983)
^ Bondy, J.-A. On Ulam's conjecture for separable graphs. Pacific J. Math. 1969, 31: 281–288. doi:10.2140/pjm.1969.31.281.
^ Yang Yongzhi:The reconstruction conjecture is true if all 2-connected graphs are reconstructible. Journal of graph theory 12, 237–243 (1988)
^ Stockmeyer, P. K., The falsity of the reconstruction conjecture for tournaments, J. Graph Theory 1 (1977), 19–25.
^ Stockmeyer, P. K., A census of non-reconstructable digraphs, I: six related families, J. Combin. Theory Ser. B 31 (1981), 232–239.
^ Harary, F. and Palmer, E., On the problem of reconstructing a tournament from sub-tournaments, Monatsh. Math. 71 (1967), 14–23.
^ Kocay, W. L., A family of nonreconstructible hypergraphs, J. Combin. Theory Ser. B 42 (1987), 46–63.
^ Nash-Williams, C. St. J. A., The Reconstruction Problem, in Selected topics in graph theory, 205–236 (1978).

[Kelly57-1] Kelly, P. J., A congruence theorem for trees, Pacific J. Math. 7 (1957), 961–968.

[Ulam60-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）.

[Harary64-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.

[Wall-5] 5.0 ^5.1 ^5.2 ^5.3 ^5.4 Wall, Nicole. The Reconstruction Conjecture. 缺少或|url=為空 (幫助)

[McKay97-6] McKay, B. D., Small graphs are reconstructible, Australas. J. Combin. 15 (1997), 123–126.

[Bollobas90-7] Bollobás, B., Almost every graph has reconstruction number three, J. Graph Theory 14 (1990), 1–4.

[h74-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

[rim-9] von Rimscha, M.: Reconstructibility and perfect graphs. Discrete Mathematics 47, 283–291 (1983)

[Bondy-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.

[yang-11] Yang Yongzhi:The reconstruction conjecture is true if all 2-connected graphs are reconstructible. Journal of graph theory 12, 237–243 (1988)

[Stockmeyer77-12] Stockmeyer, P. K., The falsity of the reconstruction conjecture for tournaments, J. Graph Theory 1 (1977), 19–25.

[Stockmeyer81-13] Stockmeyer, P. K., A census of non-reconstructable digraphs, I: six related families, J. Combin. Theory Ser. B 31 (1981), 232–239.

[HararyPalmer-14] Harary, F. and Palmer, E., On the problem of reconstructing a tournament from sub-tournaments, Monatsh. Math. 71 (1967), 14–23.

[Kocay87-15] Kocay, W. L., A family of nonreconstructible hypergraphs, J. Combin. Theory Ser. B 42 (1987), 46–63.

[NashWilliams78-16] Nash-Williams, C. St. J. A., The Reconstruction Problem, in Selected topics in graph theory, 205–236 (1978).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]