重構猜想

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

正式陳述

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

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

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

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

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

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

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

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

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

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

可識別的屬性

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

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

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

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

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

• Tutte polynomial
• 圖的特徵多項式
• 平面性
• 圖中生成樹的種類
• 色多項式

驗證情況

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

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

可重構的圖

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

• 正則圖^[8] - 通過直接應用一些能夠被deck識別的屬性,可以證明正則圖是可重構的。給定一個 ${\displaystyle n}$-正則圖${\displaystyle G}$以及它的deck ${\displaystyle D(G)}$,我們可以通過識別每個頂點的度來識別圖的正則性。我們觀察 ${\displaystyle D(G)}$中的一個圖, ${\displaystyle G_{i}}$。 它有一些度為${\displaystyle n}$的頂點和${\displaystyle n}$個度為${\displaystyle n-1}$的頂點. 通過增加一個頂點，將其${\displaystyle n}$個度為${\displaystyle n-1}$的頂點相連，可以構造一個 ${\displaystyle n}$-正則圖， 該圖與圖${\displaystyle 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]

對偶性

頂點重構定理有一定的對偶性質，如果 ${\displaystyle G}$可重構，則其補 ${\displaystyle G'}$可以以如下方式被${\displaystyle D(G')}$重構：從${\displaystyle D(G')}$中取出所有的card，分別取補得到${\displaystyle D(G)}$，用它來重構 ${\displaystyle G}$，再取補得到${\displaystyle 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的無交並。

另見

• New digraph reconstruction conjecture
• Partial symmetry

更多資料

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