主題
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)。

另請參閱

擾亂數

使用 探索

參考文獻

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." 來自 Web 資源。 https://mathworld.tw/PebblingNumber.html

主題分類