主題
Search

根圖

下載 Mathematica 筆記本下載 Wolfram 筆記本
RootedGraphs

根圖是一個 圖，其中一個節點以特殊方式標記，以便與其他節點區分開來。這個特殊節點稱為圖的根。在 n 個節點上的根圖與 對稱關係 同構於 n 個節點。具有 p 個點的根圖的數量的計數多項式是

r_p(x)=Z((S_1+S_(p-1))^((2)),1+x),
(1)

其中 S_1+S_(p-1) 是 對稱群 S_(p-1)，每個元素都附加了一個額外的元素 {p}，(S_1+S_(p-1))^((2)) 是它的對群，而 Z((S_1+S_(p-1))^((2))) 是相應的迴圈指標 (Harary 1994, p. 186)。前幾個迴圈指標是

Z((S_1+S_0)^((2)))=1
(2)
Z((S_1+S_1)^((2)))=x_1
(3)
Z((S_1+S_2)^((2)))=1/2x_1^3+1/2x_2x_1
(4)
Z((S_1+S_3)^((2)))=1/6x_1^6+1/2x_2^2x_1^2+1/3x_3^2
(5)
Z((S_1+S_4)^((2)))=1/(24)x_1^(10)+1/4x_2^3x_1^4+1/8x_2^4x_1^2+1/3x_3^3x_1+1/4x_2x_4^2.
(6)

代入 x_i=1+x^i 得到計數多項式

r_1=1
(7)
r_2=1+x
(8)
r_3=1+2x+2x^2+x^3
(9)
r_4=1+2x+4x^2+6x^3+4x^4+2x^5+x^6.
(10)

這給出了在下表中說明的具有 q 條邊的 p 個節點上的根圖的陣列 (OEIS A070166)。

pq=0, 1, 2, ...
11
21, 1
31, 2, 2, 1
41, 2, 4, 6, 4, 2, 1
51, 2, 5, 11, 17, 18, 17, 11, 5, 2, 1

然後將 x=1 代入 r_p(x) 得到 p=1, 2, ... 個節點上的根圖的數量，分別為 1, 2, 6, 20, 90, 544, ... (OEIS A000666)。

另請參閱

根頂點, 有根樹

使用 探索

參考文獻

Cameron, P. J. "Sequences Realized by Oligomorphic Permutation Groups." J. Integer Seqs. 3, #00.1.5, 2000.Harary, F. 圖論。 Reading, MA: Addison-Wesley, p. 186, 1994.Harary, F. and Palmer, E. M. 圖形計數。 New York: Academic Press, p. 241, 1973.Harary, F.; Palmer, E. M.; Robinson, R. W.; and Schwenk, A. J. "Enumeration of Graphs with Signed Points and Lines." J. Graph Theory 1, 295-308, 1977.McIlroy, M. D. "Calculation of Numbers of Structures of Relations on Finite Sets." Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports. No. 17, Sept. 15, pp. 14-22, 1955.Oberschelp, W. "Kombinatorische Anzahlbestimmungen in Relationen." Math. Ann. 174, 53-78, 1967.Sloane, N. J. A. Sequences A000666/M1650 and A070166 in "整數序列線上百科全書。"

在 中被引用

根圖

請引用為

Weisstein, Eric W. "根圖。" 來自 —— 資源。 https://mathworld.tw/RootedGraph.html

主題分類