查看“︁重构猜想”︁的源代码

{{translating|[[:en:Complete graph]]||tpercent=95|time=2020-10-04}}{{unsolved|数学|一个图能够被它的子图唯一地决定吗？}}
'''重构猜想'''(英语:Reconstruction Conjecture)，[[图论]]中的重構猜想，认为一个图能够由它的子图唯一决定。此猜想由PAUL J. KELLY<ref name=Kelly57>Kelly, P. J., [http://projecteuclid.org/getRecord?id=euclid.pjm/1103043674 A congruence theorem for trees], ''Pacific J. Math.'' '''7''' (1957), 961&ndash;968.</ref>和[[斯塔尼斯拉夫·乌拉姆]]<ref name=Ulam60>Ulam, S. M., A collection of mathematical problems, Wiley, New York, 1960.</ref><ref>{{cite journal|author=O'Neil, Peter V.|title=Ulam's conjecture and graph reconstructions|journal=Amer. Math. Monthly|volume=77|year=1970|pages=35–43|url=http://www.maa.org/programs/maa-awards/writing-awards/ulams-conjecture-and-graph-reconstructions|doi=10.2307/2316851|access-date=2020-04-06|archive-date=2021-04-19|archive-url=https://web.archive.org/web/20210419123838/https://www.maa.org/programs/maa-awards/writing-awards/ulams-conjecture-and-graph-reconstructions|dead-url=no}}</ref>共同提出。
==正式陈述==
给定图 <math>G = (V,E)</math>, 其 '''顶点子图'''（英文：vertex-deleted subgraph）是在<math>G</math>中删除了一个顶点得到的[[图论术语|子图]]. 根据定义, 它是图 <math>G</math>的[[导出子图]]。

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

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

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

[[Frank Harary|Harary]]<ref name="Harary64">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.</ref> 提出了一个更强的假设:

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

给定图<math>G = (V,E)</math>, 其 '''边子图'''（英文：edge-deleted subgraph）是在<math>G</math>中删除了一条边得到的[[Glossary of graph theory#Subgraphs|子图]]an '''edge-deleted subgraph''' of <math>G</math> 

对于图<math>G</math>, 其'''edge-deck''', 记作<math>ED(G)</math>,是由<math>G</math>的所有边子图的同构类所组成的[[多重集]]。<math>D(G)</math>中的每一个图被叫做一张 '''edge-card'''。

* '''边重构猜想 Edge Reconstruction Conjecture:''' (Harary, 1964)<ref name="Harary64"/> 对对任意两个边的个数大于等于4的图，若它们的边子图均相等，则它们是同构的。

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

*[[图论术语|图的阶数]] – 图<math>G</math>的阶数, <math>|V(G)|</math>， 可以从<math>D(G)</math>中识别，因为 多重集<math>D(G)</math> 包含了每一个从 <math>G</math>中删除一个顶点的子图，因此<math>|V(G)| = |D(G)|</math> <ref name="Wall"/>

*[[图论术语|图的边数]] – 阶数为<math>n</math>的图<math>G</math>的边的个数 , <math>|E(G)|</math>，是可识别的。首先要注意到，<math>G</math>中的每一条边会在<math>D(G)</math>中 <math>n-2</math> 个图中出现。其原因是：根据<math>D(G)</math>的定义，每次构造顶点子图时，当删掉的顶点并不是这条边的端点时，它就会在这个顶点子图中出现，因此它会出现<math>n-2</math>次。根据以上这个观察， <math>|E(G)| = \sum \frac{q_i}{n-2}</math>，其中<math>q_i</math>是<math>D(G)</math>中第''i''个图的边的个数。<ref name="Wall"/>

*[[度 (图论)|度序列]] – 图 <math>G</math>的度序列是可识别的，因为每一个顶点的度都是可识别的。为了找到vertex <math>v_i</math>的度，我们研究删除这个顶点之后的图, <math>G_i</math>。它包含了所有不和<math>v_i</math>相接的边，故如果<math>q_i</math>是<math>G_i</math>中边的个数，则 <math>|E(G)| - q_i = \deg(v_i)</math>。<ref name="Wall"/>

*[[连通图|边连通性]] –根据定义，图 <math>G</math>是<math>n</math>-边连通的如果删除任意一个顶点可以导出一个 <math>n-1</math>-边连通图；因此，如果每一个card都是一个<math>n-1</math>-边连通图，我们知道原图是<math>n</math>-边连通图。 我们也可以确定原图是否是连通的，因为这等价于任意两个<math>G_i</math>是连通的。<ref name="Wall"/>

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

==验证情况==
重构猜想和顶点重构猜想在图的阶数小于等于11的情况下均已被[[Brendan McKay]]<ref name=McKay97>McKay, B. D., Small graphs are reconstructible, ''Australas. J. Combin.'' '''15''' (1997), 123&ndash;126.</ref>验证。

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

==可重构的图==
重构猜想已经在一些种类的图上被验证。
*[[正则图]]<ref name=h74>{{Citation | last=Harary | first=F. | contribution=A survey of the reconstruction conjecture | series=Graphs and Combinatorics. [[Lecture Notes in Mathematics]]| pages=18–28 | year=1974 | publisher=Springer | doi=10.1007/BFb0066431 | title=A survey of the reconstruction conjecture | volume=406}}</ref> - 通过直接应用一些能够被deck识别的属性,可以证明正则图是可重构的。给定一个 <math>n</math>-正则图<math>G</math>以及它的deck <math>D(G)</math>,我们可以通过识别每个顶点的度来识别图的正则性。我们观察 <math>D(G)</math>中的一个图, <math>G_i</math>。  它有一些度为<math>n</math>的顶点和<math>n</math>个度为<math>n-1</math>的顶点. 通过增加一个顶点，将其<math>n</math>个度为<math>n-1</math>的顶点相连，可以构造一个 <math>n</math>-正则图， 该图与图<math>G</math>同构。因此，所有的正则图都可以被它们的deck重构。一类特殊的正则图是完全图。<ref name="Wall">{{cite web|last=Wall|first=Nicole|title=The Reconstruction Conjecture}}</ref> 

*[[树 (图论)|树]]<ref name=h74/>
*[[连通图|不连通图]]<ref name=h74/>
*[[Unit interval graph]]<ref name=rim>von Rimscha, M.: Reconstructibility and perfect graphs. ''Discrete Mathematics'' '''47''', 283–291 (1983)</ref>
*[[Separable graph]]s without [[Leaf vertex|end vertices]]<ref name=Bondy>{{Cite journal | last=Bondy | first=J.-A. | title=On Ulam's conjecture for separable graphs | journal=Pacific J. Math. | volume=31 | year=1969 | pages=281–288 | doi=10.2140/pjm.1969.31.281 }}</ref>
*[[平面图（图论）|极大平面图]]
*[[Maximal outerplanar graph]]
*[[Outerplanar graph]]
*[[Critical blocks]]

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


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

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

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

==更多资料==
更多关于重构猜想的内容详见 [[Crispin St. J. A. Nash-Williams|Nash-Williams]]的综述<ref name=NashWilliams78>[[Crispin St. J. A. Nash-Williams|Nash-Williams, C. St. J. A.]], The Reconstruction Problem, in ''Selected topics in graph theory'', 205&ndash;236 (1978).</ref>

== 參考資料 ==

{{reflist}}

[[Category:图论]]