重构猜想

重构猜想(英语: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]