主题
Search

铺石数

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

将铺石移动定义为将两个石子从图边的一个顶点转移到相邻顶点，其中一个石子在转移过程中作为代价被移除。图 pi(G) 的铺石数 G 是最小的 t，使得每个 t 个石子的供应可以满足每个一个石子的需求 (Hurlbert 2011)。计算铺石数是 NP 完全问题 (Hurlbert 2011)。

下表给出了各种图类的铺石数值 (Hurlbert)。

图铺石数
完全二分图 K_(2,n)n+2
完全图 K_nn
循环图 C_n{2^(n/2) for n even; (2^((n+3)/2)-1)/3 for n odd
超立方体图 Q_n2^n
路径图 P_n2^(n-1)

铺石数满足许多界限。设 n=|G| 为顶点数，d(G) 为图直径，以及 gamma(G) 为图 G 的支配数。

宽度下界

pi(G)>=n
(1)

割下界 (其中 G_x 包含割顶点 x)

pi(G_x)>n
(2)

深度下界

pi(G)>=2^d
(3)

鸽巢原理上界

pi(G)<=(n-1)(2^d-1)+1
(4)

更精确的界限

pi(G)<=(n-d)(2^d-1)+1
(5)
pi(G)<=(n+|_n-1/d_|-1)2^(d-1)-n+2
(6)
pi(G)<=(n+2gamma)2^(d-1)-gamma+1
(7)

(Hurlbert)。

对于图 d(G)=2,

pi(G)<=n+1,
(8)

其中 n=|G| 是 G 的顶点数 (Hurlbert 2011)。

另请参阅

扰乱数

使用 Wolfram|Alpha 探索

参考文献

Chung, F. R. K. "'Pebbling in Hypercubes." SIAM J. Disc. Math. 2, 467-472, 1989.Hurlbert, G. "A Linear Optimization Technique for Graph Pebbling." 28 Jan 2011. https://arxiv.org/abs/1101.5641.Hurlbert, G. "General Graph Pebbling." Disc. Appl. Math. 161, 1221-1231, 2013.Hurlbert, G. "Graph Pebbling Numbers Page." http://www.people.vcu.edu/~ghurlbert/pebbling/pnummain.html.Milans, K. and Clark, B. "The Complexity of Graph Pebbling." SIAM J. Disc. Math. 20, 769-798, 2006.

请引用本文为

Weisstein, Eric W. "Pebbling Number." 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/PebblingNumber.html

主题分类