主題
Search

毛毛蟲圖

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook

毛毛蟲圖，毛毛蟲樹，或簡稱為“毛毛蟲”，是一種樹，其中每個圖頂點都在中心莖幹上，或僅距離莖幹一個圖邊（換句話說，移除其端點後會留下一個路徑圖；Gallian 2007）。一棵樹是毛毛蟲當且僅當所有度數 >=3 的節點最多被兩個度數為 2 或更大的節點包圍。

n-烷烴圖有時也被稱為毛毛蟲圖 (Boesch et al. 1974; Merrifield and Simmons 1989, pp. 161-162)。

毛毛蟲圖是優美的。

CaterpillarTrees

節點數為 n>=3 的毛毛蟲樹的數量是

C_n=2^(n-4)+2^(|_n/2-2_|),

其中 |_x_| 是向下取整函式 (Harary and Schwenk 1973)。對於 n=1, 2, ... 個節點，結果為 1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, ... (OEIS A005418)。上面展示了前幾個毛毛蟲圖。

CaterpillarGraph

節點數為 n=7, 8, ... 的非毛毛蟲樹的數量為 1, 3, 11, 34, 99, ... (OEIS A052471)。上面展示了節點數 n<=9 的非毛毛蟲樹。

另請參閱

香蕉樹, 蜈蚣圖, 龍蝦圖, 樹

使用 探索

參考文獻

Boesch, F. T.; Chen, S.; 和 McHugh, J. A. M. "關於用點不相交路徑覆蓋圖的點。" In Graphs and Combinatorics (Ed. R. A. Bari 和 F. Harary). Berlin: Springer-Verlag, pp. 201-212, 1974.Gallian, J. "圖示記的動態綜述。" Elec. J. Combin. DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Gardner, M. 輪子，生命和其他數學消遣。 New York: W. H. Freeman, p. 160, 1983.Gutman, I. 和 El-Basil, S. "苯並類系統的拓撲性質。XXXVII. 某些化學圖的表徵。" Z. Naturforsch. A 40, 923-926, 1985.Harary, F. 和 Schwenk, A. J. "毛毛蟲的數量。" Disc. Math. 6, 359-365, 1973.Hoffman, N. "二元網格和一個相關的計數問題。" Two Year Coll. Math. J. 9, 267-272, 1978.Horton, M. "優美樹：統計和演算法。" 榮譽計算學士論文。塔斯馬尼亞大學, 2003. https://eprints.utas.edu.au/19/1/GracefulTreesStatisticsAndAlgorithms.pdf.Merrifield, R. E. 和 Simmons, H. E. 化學中的拓撲方法。 New York: Wiley, 1989.Sloane, N. J. A. 序列 A005418/M0771 和 A052471 在 "The On-Line Encyclopedia of Integer Sequences." 中。Sulanke, R. A. "廣義莫茨金路徑的矩。" J. Integer Sequences 3, No. 00.1.1, 2000. http://www.math.uwaterloo.ca/JIS/VOL3/SULANKE/sulanke.

請引用為

Weisstein, Eric W. “毛毛蟲圖。” 來自 Web 資源。 https://mathworld.tw/CaterpillarGraph.html

主題分類