主题
Search

构造数


设图 G=(V,E) 定义在顶点集 V边集 E 上。则图 G 的构造序列(或 c-序列)是 V union E 上的线性顺序,其中每条边都出现在其两个端点之后。图 c(G) 的构造数 G 定义为图 G 的不同构造序列的数量 (Kainen 2023)。

PathGraphP3

例如,对于路径图 P_3,其顶点集为 1, 2, 3,边集为 12, 23,共有 16 个可能的构造序列:(1, 2, 3, 12, 23)、(1, 2, 3, 23, 12)、(1, 2, 12, 3, 23)、(1, 3, 2, 12, 23)、(1, 3, 2, 23, 12)、(2, 1, 3, 12, 23)、(2, 1, 3, 23, 12)、(2, 1, 12, 3, 23)、(2, 3, 1, 12, 23)、(2, 3, 1, 23, 12)、(2, 3, 23, 1, 12)、(3, 1, 2, 12, 23)、(3, 1, 2, 23, 12)、(3, 2, 1, 12, 23)、(3, 2, 1, 23, 12)、(3, 2, 23, 1, 12),因此 c(P_3)=16

下表总结了一些参数化图的构造数(参见 Kainen 2023),其中 (n; k)二项式系数n阶乘n!!双阶乘B_(2n)伯努利数,而 Gamma(n)伽玛函数。Kainen等人 (2023) 提出了确定 c(K_n) 的问题,并由 Tauraso (2024) 解决。


另请参阅

组装数

使用 Wolfram|Alpha 探索

参考文献

Kainen, P. C. "Construction Numbers: How to Build a Graph?" 2023 年 2 月 25 日。 https://arxiv.org/abs/2302.13186.Kainen, P. C.; Strong, R.; 和 Tilley, J. 问题 12401. Amer. Math. Monthly 130, 587, 2023.Sloane, N. J. A. 序列 A000142, A000182, A024255, A055546, A210277, 和 A374928,来自“整数序列在线百科全书”。Tauraso, R. 问题 12401 的解答. Amer. Math. Monthly. 2024. https://www.mat.uniroma2.it/~tauraso/AMM/AMM12401.pdf.

引用为

Weisstein, Eric W. "构造数。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/ConstructionNumber.html