重构猜想

重构猜想(英语:Reconstruction Conjecture)，图论中的重構猜想，认为一个图能够由它的子图唯一决定。此猜想由PAUL J. KELLY和斯塔尼斯拉夫·乌拉姆共同提出。
正式陈述
给定图 G = (V,E), 其 顶点子图（英文：vertex-deleted subgraph）是在G中删除了一个顶点得到的子图. 根据定义, 它是图 G的导出子图。

对于图G, 其deck, 记作D(G),是由G的所有顶点子图的同构类所组成的多重集。D(G)中的每一个图被叫做一张 card。两个拥有相同deck的图被称作彼此hypomorphic。

在给了以上的定义后，重构猜想可以表述为：

• 重构猜想: 任何两个顶点数大于等于3的彼此hypomorphic的图是同构的。

: (这里要求两个图的顶点数大于等于3是必要的，因为顶点数为2的图本就有相同的deck）

Harary 提出了一个更强的假设:

• 顶点重构猜想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)验证。

Béla Bollobás提出，在概率意义下几乎所有的图都是可重构的。 ，这意味着随着图的阶数n趋于无穷，一个随机选择的阶数为n的图不能被重构的概率趋于0。事实上，可以证明不仅几乎所有的图重构的，而且重构它们并不需要整个deck，几乎所有的图都可以被deck中的3张card来决定。

可重构的图
重构猜想已经在一些种类的图上被验证。
*正则图 - 通过直接应用一些能够被deck识别的属性,可以证明正则图是可重构的。给定一个 n-正则图G以及它的deck D(G),我们可以通过识别每个顶点的度来识别图的正则性。我们观察 D(G)中的一个图, G_i。 它有一些度为n的顶点和n个度为n-1的顶点. 通过增加一个顶点，将其n个度为n-1的顶点相连，可以构造一个 n-正则图， 该图与图G同构。因此，所有的正则图都可以被它们的deck重构。一类特殊的正则图是完全图。

*树
*Separable graphs without end vertices
*极大平面图
*Maximal outerplanar graph
*Outerplanar graph
*Critical blocks

猜想的规约
如果所有的2-conected图都是可重构的，则重构猜想正确。

对偶性
顶点重构定理有一定的对偶性质，如果 G可重构，则其补 G'可以以如下方式被D(G')重构：从D(G')中取出所有的card，分别取补得到D(G)，用它来重构 G，再取补得到G'。

边重构定理并没有这样的对偶性质：事实上，对于某些类型的边-可重构图来说，我们并不知道它们的补能否被边重构。

其他结构
以下的一些图结构被证明在一般情况下都不能被重构：

• 有向图: 无数种不能被重构的有向图已经被发现：其中包括tournaments (Stockmeyer) 和 non-tournaments (Stockmeyer)。 如果一个tournament不是强连接（strongly connected)，则是可重构的。 一个针对有向图的弱版本的重构猜想可以详见new digraph reconstruction conjecture。
• 超图 (Kocay).
• 无限图-令无限图T每个顶点的度都为无穷的树，令nT 为n 个T 的disjoint union 。 这些图相互hypomorphic，因此它们并不是可重构的。这些图的任以顶点子图都是同构的：它们都是无数个T的无交并。

另见

• New digraph reconstruction conjecture
• Partial symmetry

更多资料
更多关于重构猜想的内容详见 Nash-Williams的综述

參考資料