重构猜想(英语: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的图,若它们的边子图均相等,则它们是同构的。

可识别的属性

编辑

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

  • 图的阶数 – 图 的阶数,  , 可以从 中识别,因为 多重集  包含了每一个从  中删除一个顶点的子图,因此  [5]
  • 图的边数 – 阶数为 的图 的边的个数 ,  ,是可识别的。首先要注意到, 中的每一条边会在   个图中出现。其原因是:根据 的定义,每次构造顶点子图时,当删掉的顶点并不是这条边的端点时,它就会在这个顶点子图中出现,因此它会出现 次。根据以上这个观察,  ,其中  中第i个图的边的个数。[5]
  • 度序列 – 图  的度序列是可识别的,因为每一个顶点的度都是可识别的。为了找到vertex  的度,我们研究删除这个顶点之后的图,  。它包含了所有不和 相接的边,故如果  中边的个数,则  [5]
  • 边连通性 –根据定义,图   -边连通的如果删除任意一个顶点可以导出一个  -边连通图;因此,如果每一个card都是一个 -边连通图,我们知道原图是 -边连通图。 我们也可以确定原图是否是连通的,因为这等价于任意两个 是连通的。[5]

验证情况

编辑

重构猜想和顶点重构猜想在图的阶数小于等于11的情况下均已被Brendan McKay[6]验证。

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

可重构的图

编辑

重构猜想已经在一些种类的图上被验证。

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

猜想的规约

编辑

如果所有的2-conected图都是可重构的,则重构猜想正确。 [11]


对偶性

编辑

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

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

其他结构

编辑

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

  • 有向图: 无数种不能被重构的有向图已经被发现:其中包括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的无交并。

另见

编辑

更多资料

编辑

更多关于重构猜想的内容详见 Nash-Williams的综述[16]

参考资料

编辑
  1. ^ Kelly, P. J., A congruence theorem for trees, Pacific J. Math. 7 (1957), 961–968.
  2. ^ Ulam, S. M., A collection of mathematical problems, Wiley, New York, 1960.
  3. ^ O'Neil, Peter V. Ulam's conjecture and graph reconstructions. Amer. Math. Monthly. 1970, 77: 35–43 [2020-04-06]. doi:10.2307/2316851. (原始内容存档于2021-04-19). 
  4. ^ 4.0 4.1 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.
  5. ^ 5.0 5.1 5.2 5.3 5.4 Wall, Nicole. The Reconstruction Conjecture. 
  6. ^ McKay, B. D., Small graphs are reconstructible, Australas. J. Combin. 15 (1997), 123–126.
  7. ^ Bollobás, B., Almost every graph has reconstruction number three, J. Graph Theory 14 (1990), 1–4.
  8. ^ 8.0 8.1 8.2 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 
  9. ^ von Rimscha, M.: Reconstructibility and perfect graphs. Discrete Mathematics 47, 283–291 (1983)
  10. ^ Bondy, J.-A. On Ulam's conjecture for separable graphs. Pacific J. Math. 1969, 31: 281–288. doi:10.2140/pjm.1969.31.281. 
  11. ^ Yang Yongzhi:The reconstruction conjecture is true if all 2-connected graphs are reconstructible. Journal of graph theory 12, 237–243 (1988)
  12. ^ Stockmeyer, P. K., The falsity of the reconstruction conjecture for tournaments, J. Graph Theory 1 (1977), 19–25.
  13. ^ Stockmeyer, P. K., A census of non-reconstructable digraphs, I: six related families, J. Combin. Theory Ser. B 31 (1981), 232–239.
  14. ^ Harary, F. and Palmer, E., On the problem of reconstructing a tournament from sub-tournaments, Monatsh. Math. 71 (1967), 14–23.
  15. ^ Kocay, W. L., A family of nonreconstructible hypergraphs, J. Combin. Theory Ser. B 42 (1987), 46–63.
  16. ^ Nash-Williams, C. St. J. A., The Reconstruction Problem, in Selected topics in graph theory, 205–236 (1978).