重構猜想(英語: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的圖,若它們的邊子圖均相等,則它們是同構的。
重構猜想和頂點重構猜想在圖的階數小於等於11的情況下均已被Brendan McKay[6]驗證。
Béla Bollobás提出,在概率意義下幾乎所有的圖都是可重構的。 [7] ,這意味着隨着圖的階數
趨於無窮,一個隨機選擇的階數為
的圖不能被重構的概率趨於0。事實上,可以證明不僅幾乎所有的圖重構的,而且重構它們並不需要整個deck,幾乎所有的圖都可以被deck中的3張card來決定。
如果所有的2-conected圖都是可重構的,則重構猜想正確。 [11]
以下的一些圖結構被證明在一般情況下都不能被重構:
- 有向圖: 無數種不能被重構的有向圖已經被發現:其中包括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]
Ulam, S. M., A collection of mathematical problems, Wiley, New York, 1960.
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, Nicole. The Reconstruction Conjecture.
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.
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)
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).