主題
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.

參見

割, 度序列, 孤立點, 譜圖劃分

使用 探索

參考文獻

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.

在 上被引用

圖劃分

引用為

Weisstein, Eric W. "圖劃分。" 來自 Web 資源。 https://mathworld.tw/GraphicalPartition.html

主題分類