主題
Search

串聯約簡樹


SeriesReducedTrees

串聯約簡樹是一種,其中所有節點的度數都不同於 2(換句話說,沒有節點僅僅允許單條邊“透過”)。串聯約簡樹也稱為同胚不可約樹(Harary 和 Palmer 1973,第 61-62 頁)或拓撲樹(Bergeron等人1998)。具有 1, 2, ... 個節點的串聯約簡樹的數量為 1, 1, 0, 1, 1, 2, 2, 4, 5, 10, 14, ... (OEIS A000014)。Harary 和 Palmer(1973,第 62 頁,圖 3.3.3)展示了節點數為 8 個及以下的串聯約簡樹。

串聯約簡樹的特殊情況包括烷烴圖星圖 S_n,其中 n>3 個節點。

串聯約簡樹在流行文化中最廣為人知,是因為它們出現在 1997 年電影心靈捕手的第二個黑板問題中,該問題提出了找到所有 (10) 個具有 10 個節點的此類樹的問題。

具有 n=1, 2, ... 個節點的串聯約簡種植樹的數量為 0, 1, 0, 1, 1, 2, 3, 6, 10, 19, 35, ... (OEIS A001678),串聯約簡有根樹的數量為 1, 1, 0, 2, 2, 4, 6, 12, 20, 39, 71, ... (OEIS A001679)。

將與 2 度頂點 v_j 相鄰的邊 e_(ij)e_(jk) 替換為單條邊 e_(ik) 的過程稱為圖平滑


另請參閱

心靈捕手問題, 圖平滑, 種植樹, 有根樹,

使用 探索

參考文獻

Bergeron, F.; Leroux, P.; 和 Labelle, G. 組合物種和樹狀結構。 英國劍橋:劍橋大學出版社,第 188, 283-284, 291 和 337 頁,1998 年。Cameron, P. J. “一些樹狀物件。” 牛津大學數學季刊 38, 155-183, 1987。Finch, S. R. §5.6 in 數學常數。 英國劍橋:劍橋大學出版社,2003 年。Harary, F. 圖論。 美國馬薩諸塞州雷丁:艾迪生-韋斯利出版社,第 232 頁,1994 年。Harary, F. 和 Palmer, E. M. 圖形計數。 紐約:學術出版社,第 61-62 頁,1973 年。Harary, F. 和 Palmer, E. M. “樹的點的固定機率。” 劍橋哲學學會數學學報 85, 407-415, 1979。Harary, F. 和 Prins, G. “同胚不可約樹和其他物種的數量。” 數學學報 101, 141-162, 1959。Harary, F.; Robinson, R. W. 和 Schwenk, A. J. “確定各種物種樹木的漸近數量的二十步演算法。” 澳大利亞數學學會雜誌,A 系列 20, 483-503, 1975。Sloane, N. J. A. 序列 A000014/M0320, A001678/M0768 和 A001679/M0327,來自“整數序列線上百科全書”。

在 中被引用

串聯約簡樹

請這樣引用

Weisstein, Eric W. “串聯約簡樹。” 來自 —— 資源。 https://mathworld.tw/Series-ReducedTree.html

主題分類