主題
Search

樹

下載 Mathematica 筆記本下載 Wolfram 筆記本
Trees

樹是一種數學結構，可以被視為圖或資料結構。這兩種觀點是等價的，因為樹資料結構不僅包含一組元素，還包含元素之間的連線，從而形成樹圖。

樹最早由 Cayley (1857) 研究。McKay 維護著一個包含多達 18 個頂點的樹的資料庫，而 Royle 維護著一個包含多達 20 個頂點的樹的資料庫。

樹是一組首尾相連的直線段，不包含閉環（環）。換句話說，它是一個簡單、無向、連通、無環的圖（或等效地，一個連通的森林）。一個有 n 個節點的樹有 n-1 條圖邊。相反，一個具有 n 個節點和 n-1 條邊的連通圖是一棵樹。所有樹都是二分圖 (Skiena 1990, p. 213)。沒有特別指出節點的樹有時被稱為自由樹（或無根樹），以區別於有根樹（Skiena 1990, Knuth 1997）。

連線點被稱為叉，線段被稱為分支。末端線段和節點被稱為樹葉。在每個叉處有兩個分支，並且在每個分支的末端有一個或兩個樹葉的樹被稱為二叉樹。

可以使用Wolfram 語言測試圖是否為樹，使用TreeGraphQ[g]。

Hydrocarbons

樹在許多不同領域都有應用，包括計算機科學、飽和烴的列舉、電路研究等（Harary 1994, p. 4）。上面說明的與線性烴對應的圖被稱為 (n-)烷烴圖（或有時稱為毛毛蟲圖）。

樹是塊圖。

樹 T 要麼有一個節點是圖中心，在這種情況下它被稱為中心樹，要麼有兩個相鄰的節點是圖中心，在這種情況下它被稱為雙中心樹（Harary 1994, p. 35）。

當指定一個特殊節點將樹變成有根樹時，它被稱為根（或有時稱為“夏娃”）。在這樣的樹中，每個距離給定節點更遠一個圖邊的節點被稱為子節點，而連線到同一節點且與根頂點距離相同的節點被稱為兄弟節點。

請注意，兩個首尾相連的分支等同於一個分支，這意味著例如，只有一個 3 階樹。階數為 n=1, 2, ... 的非同構樹的數量 t(n) （其中階數為 1、2、...、6 的樹如上所示）為 1、1、1、2、3、6、11、23、47、106、235、551、1301、3159、... (OEIS A000055)。

有根樹數量的生成函式

T(x)=sum_(n=1)^(infty)T_nx^n
(1)
=xexp[sum_(r=1)^(infty)1/rT(x^r)]
(2)

與無根樹數量的生成函式 t(x) 相關，關係如下

t(x)=sum_(n=1)^(infty)t_nx^n
(3)
=T(x)-1/2[T^2(x)-T(x^2)].
(4)

Otter 表明

lim_(n->infty)(t_nn^(5/2))/(alpha^n)=beta,
(5)

(Otter 1948, Harary and Palmer 1973, Knuth 1997)，其中 alpha 和 beta 是兩個常數。alpha 由下式給出

alpha=lim_(n->infty)(T_n)/(T_(n-1))
(6)
=2.955765...
(7)

(OEIS A051491; Odlyzko 1995; Knuth 1997, p. 396, 其中 Knuth 寫道 1/alpha=2.9557... 而不是 alpha=2.9557...) 並且也是以下方程的唯一正根

T(1/x)=1.
(8)

常數 beta 由下式給出

beta=1/(sqrt(2pi))[1+sum_(k=2)^(infty)T^'(1/(alpha^k))1/(alpha^k)]^(3/2)
(9)
=0.5349485...
(10)

(OEIS A086308; Knuth 1997, p. 396)。

如果 t_n 是 n 個節點上的非同構樹的數量，則 t_n 的漸近級數由下式給出

t_n∼alpha^nn^(-5/2)(0.5349496061...+(0.0441699018...)/n+(0.4853877311...)/(n^2)+(2.379745574...)/(n^3)+...),
(11)

其中常數可以用函式的部分導數計算

F(x,y)=xexp[y+sum_(k=2)^infty(T(x^k))/k]-y
(12)

(Plotkin and Rosenthal 1994; Finch 2003)。

另請參閱

烷烴圖, B 樹, 香蕉樹, Barnsley 樹, 雙中心樹, 二叉樹, 毛毛蟲圖, Cayley 樹, 中心樹, 子節點, Dijkstra 樹, 擴充套件二叉樹, 森林, 自由樹, k-樹, Kruskal 演算法, Kruskal 樹定理, 標記樹, 龍蝦圖, Mandelbrot 樹, 矩陣樹定理, 果園種植問題, 有序樹, Otter 定理, 路徑圖, 平面植根樹, Pólya 列舉定理, Polynema, 畢達哥拉斯樹, 四叉樹, Ramus 樹, 紅黑樹, 根頂點, 有根樹, 串聯約簡樹, 兄弟節點, 生成樹, 星圖, Steiner 樹, Stern-Brocot 樹, 樹分解, 樹葉, 樹搜尋, 弱二叉樹, 加權樹 在 課堂中探索此主題

使用 探索

參考文獻

Finch, S. R. "Otter's Tree Enumeration Constants." §5.6 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 295-316, 2003.Bergeron, F.; Leroux, P.; and Labelle, G. Combinatorial Species and Tree-Like Structures. Cambridge, England: Cambridge University Press, p. 284, 1998.Cayley, A. "On the Theory of Analytic Forms Called Trees." Philos. Mag. 13, 19-30, 1857. Reprinted in Mathematical Papers, Vol. 3. Cambridge: pp. 242-246, 1891.Chauvin, B.; Cohen, S.; and Rouault, A. (Eds.). Trees: Workshop in Versailles, June 14-16, 1995. Basel, Switzerland: Birkhäuser, 1996.Finch, S. "Two Asymptotic Series." December 10, 2003. http://algo.inria.fr/bsolve/.Gardner, M. "Trees." Ch. 17 in Mathematical Magic Show: More Puzzles, Games, Diversions, Illusions and Other Mathematical Sleight-of-Mind from Scientific American. New York: Vintage, pp. 240-250, 1978.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Harary, F. "Trees." Ch. 4 in Graph Theory. Reading, MA: Addison-Wesley, pp. 32-42, 187-194, and 231-234, 1994.Harary, F. and Manvel, B. "Trees." Scripta Math. 28, 327-333, 1970.Harary, F. and Palmer, E. M. "Trees." Ch. 3 in Graphical Enumeration. New York: Academic Press, pp. 51-80, 1973.Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1997.König, D. Theorie der endlichen und unendlichen Graphen. New York: Chelsea, p. 48, 1950.McKay, B. D. "Trees Sorted by Diameter." http://cs.anu.edu.au/~bdm/data/trees.html.Nijenhuis, A. and Wilf, H. Combinatorial Algorithms for Computers and Calculators, 2nd ed. New York: Academic Press, 1978.Odlyzko, A. M. "Asymptotic Enumeration Methods." In Handbook of Combinatorics, Vol. 2 (Ed. R. L. Graham, M. Grötschel, and L. Lovász). Cambridge, MA: MIT Press, pp. 1063-1229, 1995. http://www.dtc.umn.edu/~odlyzko/doc/asymptotic.enum.pdf.Otter, R. "The Number of Trees." Ann. Math. 49, 583-599, 1948.Plotkin, J. M. and Rosenthal, J. W. "How to Obtain an Asymptotic Expansion of a Sequence from an Analytic Identity Satisfied by Its Generating Function." J. Austral. Math. Soc. Ser. A 56, 131-143, 1994.Royle, G. "Trees On Up to 16 [sic] Vertices." http://school.maths.uwa.edu.au/~gordon/remote/graphs/#trees.Skiena, S. "Trees." Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 107 and 151-153, 1990.Sloane, N. J. A. Sequences A000055/M0791, A051491, and A086308 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. Figure M0791 in The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.Wilf, H. S. Combinatorial Algorithms: An Update. Philadelphia, PA: SIAM, 1989.

在 上被引用

樹

引用為

Weisstein, Eric W. "樹。" 來自 Web 資源。 https://mathworld.tw/Tree.html

主題分類