主题
Search

图划分

下载 Mathematica 笔记本下载 Wolfram 笔记本

一个划分 {a_1,...,a_n} 如果存在一个图 G 具有度序列 {a_1,...,a_n}, 则被称为图划分。 长度为 n 的图划分的数量等于没有孤立点的 n 节点图的数量。

对应于 n=1, 2, ... 个节点的图的不同图划分的数量为 0, 1, 2, 7, 20, 71, 240, 871, 3148, ... (OEIS A095268)。

阶数为 p 的图划分是指度数之和为 p 的划分。 p 阶图划分仅在 偶数 p 时存在。

GraphicalPartitions22211

拓扑结构不同的两个图可能具有相同的度序列，如上图所示的例子。

GraphicalPartitions

在 p_g(n) 上，n=2, 4, 6, ... 条边的图划分的数量 p_g(n) 为 1, 2, 5, 9, 17, 31, 54, 90, 151, 244, ... (OEIS A000569)。

Erdős 和 Richmond (1989) 表明

liminf_(n->infty)sqrt(n)p_g(n)>=pi/(sqrt(6))

和

limsup_(n)p_g(n)<=0.4258.

参见

割, 度序列, 孤立点, 谱图划分

使用 Wolfram|Alpha 探索

参考文献

Barnes, T. M. 和 Savage, C. D. "图划分计数的递推关系。" Electronic J. Combinatorics 2, No. 1, R11, 1-10, 1995. http://www.combinatorics.org/Volume_2/Abstracts/v2i1r11.html。Barnes, T. M. 和 Savage, C. D. "图划分的有效生成。" Disc. Appl. Math. 78, 17-26, 1997.Erdős, P. 和 Richmond, L. B. "关于图划分。" Combinatorics and Optimization Research Report COPR 89-42. Waterloo, Ontario: University of Waterloo, pp. 1-13, 1989.Harary, F. 图论。 Reading, MA: Addison-Wesley, p. 57, 1994.Ruskey, F. "关于图划分的信息。" http://www.theory.csc.uvic.ca/~cos/inf/nump/GraphicalPartition.html。Sloane, N. J. A. 序列 A000569, A002494/M1762, 和 A095268 在 "整数序列在线百科全书" 中。Wilf, H. "关于交叉数和一些未解决的问题。" 在 组合学、几何学和概率：向 Paul Erdős 致敬。1993 年 3 月在剑桥三一学院举行的纪念 Erdős 80 岁生日会议论文集 (Ed. B. Bollobás 和 A. Thomason). Cambridge, England: Cambridge University Press, pp. 557-562, 1997.

在 Wolfram|Alpha 上被引用

图划分

引用为

Weisstein, Eric W. "图划分。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/GraphicalPartition.html

主题分类