重构猜想

重构猜想(英语:Reconstruction Conjecture)，图论中的重構猜想，认为一个图能够由它的子图唯一决定。此猜想由PAUL J. KELLYKelly, 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.共同提出。
正式陈述
给定图 , 其 顶点子图（英文：vertex-deleted subgraph）是在中删除了一个顶点得到的子图. 根据定义, 它是图 的导出子图。

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

在给了以上的定义后，重构猜想可以表述为：
 重构猜想: 任何两个顶点数大于等于3的彼此hypomorphic的图是同构的。

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

HararyHarary, 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. 提出了一个更强的假设:

 顶点重构猜想Set Reconstruction Conjecture: 对任意两个顶点数大于等于4的图，若它们的顶点子图均相等，则它们是同构的。

给定图, 其 边子图（英文：edge-deleted subgraph）是在中删除了一条边得到的子图an edge-deleted subgraph of  

对于图, 其edge-deck, 记作,是由的所有边子图的同构类所组成的多重集。中的每一个图被叫做一张 edge-card。

 边重构猜想 Edge Reconstruction Conjecture: (Harary, 1964) 对对任意两个边的个数大于等于4的图，若它们的边子图均相等，则它们是同构的。

可识别的属性
在重构猜想中，一个图属性被称作
可识别的如果它可以被图的deck确定。以下的这些属性是可识别的：

图的阶数 – 图的阶数, ， 可以从中识别，因为 多重集 包含了每一个从 中删除一个顶点的子图，因此 

图的边数 – 阶数为的图的边的个数 , ，是可识别的。首先要注意到，中的每一条边会在中  个图中出现。其原因是：根据的定义，每次构造顶点子图时，当删掉的顶点并不是这条边的端点时，它就会在这个顶点子图中出现，因此它会出现次。根据以上这个观察， ，其中是中第i个图的边的个数。

度序列 – 图 的度序列是可识别的，因为每一个顶点的度都是可识别的。为了找到vertex 的度，我们研究删除这个顶点之后的图, 。它包含了所有不和相接的边，故如果是中边的个数，则 。

边连通性 –根据定义，图 是-边连通的如果删除任意一个顶点可以导出一个 -边连通图；因此，如果每一个card都是一个-边连通图，我们知道原图是-边连通图。 我们也可以确定原图是否是连通的，因为这等价于任意两个是连通的。

Tutte polynomial
图的特征多项式
平面性
图中生成树的种类
色多项式

验证情况
重构猜想和顶点重构猜想在图的阶数小于等于11的情况下均已被Brendan McKayMcKay, B. D., Small graphs are reconstructible, Australas. J. Combin. 15 (1997), 123–126.验证。

Béla Bollobás提出，在概率意义下几乎所有的图都是可重构的。 Bollobás, B., Almost every graph has reconstruction number three, J. Graph Theory 14 (1990), 1–4. ，这意味着随着图的阶数趋于无穷，一个随机选择的阶数为的图不能被重构的概率趋于0。事实上，可以证明不仅几乎所有的图重构的，而且重构它们并不需要整个deck，几乎所有的图都可以被deck中的3张card来决定。 

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

树
不连通图
Unit interval graphvon Rimscha, M.: Reconstructibility and perfect graphs. Discrete Mathematics 47, 283–291 (1983)
Separable graphs without end vertices
极大平面图
Maximal outerplanar graph
Outerplanar graph
Critical blocks

猜想的规约
如果所有的2-conected图都是可重构的，则重构猜想正确。 Yang Yongzhi:The reconstruction conjecture is true if all 2-connected graphs are reconstructible. Journal of graph theory 12, 237–243 (1988) 

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

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

其他结构
以下的一些图结构被证明在一般情况下都不能被重构：
 有向图: 无数种不能被重构的有向图已经被发现：其中包括tournaments (StockmeyerStockmeyer, P. K., The falsity of the reconstruction conjecture for tournaments, J. Graph Theory 1 (1977), 19–25.) 和 non-tournaments (StockmeyerStockmeyer, P. K., A census of non-reconstructable digraphs, I: six related families, J. Combin. Theory Ser. B 31 (1981), 232–239.)。 如果一个tournament不是强连接（strongly connected)，则是可重构的。Harary, F. and Palmer, E., On the problem of reconstructing a tournament from sub-tournaments, Monatsh. Math. 71 (1967), 14–23. 一个针对有向图的弱版本的重构猜想可以详见new digraph reconstruction conjecture。
 超图 (KocayKocay, W. L., A family of nonreconstructible hypergraphs, J. Combin. Theory Ser. B 42 (1987), 46–63.).
 无限图-令无限图T每个顶点的度都为无穷的树，令nT 为n 个T 的disjoint union 。 这些图相互hypomorphic，因此它们并不是可重构的。这些图的任以顶点子图都是同构的：它们都是无数个T的无交并。
另见
 New digraph reconstruction conjecture
 Partial symmetry

更多资料
更多关于重构猜想的内容详见 Nash-Williams的综述Nash-Williams, C. St. J. A., The Reconstruction Problem, in Selected topics in graph theory, 205–236 (1978).

 參考資料 

Category:图论