樹（圖理論）
| 樹木 | |
|---|---|
 一個標記的樹，有6個頂點和5個邊緣。 | |
| 頂點 | v |
| 邊緣 | V - 1 |
| 色數 | 2如果V > 1 |
| 圖和參數表 | |
在圖理論中，樹是一個無向圖，其中任何兩個頂點都通過一個路徑或等效連接的無向圖連接。森林是一個無方向的圖，其中任何兩個頂點在最多的路徑上都通過一個路徑連接，或者等效地是無向圖，或者等效地相等的樹木結合。
Polytree （或定向的樹或定向的樹或單一連接的網絡）是有向的無環圖（DAG），其基本的無向圖是樹。多孔（或定向森林或定向森林）是一個有向的無環圖，其基本的無向圖是森林。
計算機科學中稱為樹的各種數據結構具有圖理論中的樹的基礎圖，儘管這些數據結構通常是生根的樹。可以將根的樹指向，稱為有向根的樹，使其所有邊緣都遠離根部（在這種情況下稱為樹木或外面），或者使其所有邊緣都指向根部 - 在這種情況下它被稱為抗動力或樹木。一些作者將根的樹本身定義為有向圖。根森林是根生樹的不一致結合。可以指向一個生根的森林，稱為有向根的森林，要么使其所有邊緣從每棵根樹中的根部指向根部，在這種情況下，它稱為分支或森林，或者使其所有邊緣指向根部在每棵根樹中 - 在這種情況下，它稱為反分支或索林。
該詞是由英國數學家亞瑟·凱利（Arthur Cayley）於1857年創造的。
定義
樹
樹是滿足以下任何等效條件的無向圖G ：
- G連接並無環（沒有周期）。
- G是無環，如果將任何邊緣添加到G中，就會形成一個簡單的循環。
- G已連接，但是如果從G中刪除任何單個邊緣，則會斷開連接。
- G連接了G，完整的圖K 3不是G的少數。
- G中的任何兩個頂點都可以通過獨特的簡單路徑連接。
如果g在其中有很多有限的頂點，那麼上述陳述也等同於以下任何條件：
與圖理論中的其他位置一樣，零階的圖（無頂點的圖形）通常不被視為樹：雖然它被排空地連接為圖形（任何兩個頂點都可以通過路徑連接），但不是0與非空樹不同的代數拓撲結合（甚至（甚至（−1））連接（甚至（−1）連接），並且違反了“一個比邊緣更多的頂點”關係。但是，它可能被認為是由零樹組成的森林。
內部頂點（或內頂點）是一個至少2的頂點。類似地，外部頂點（或外頂點，末端頂點或葉子）是度1的頂點1。至少3個。
不可還原的樹（或串聯的樹）是一棵樹，其中沒有2度的頂點（在OEI中以序列A000014進行了列舉）。
森林
森林是一個無方向的圖，其中任何兩個頂點在最多一條路徑上都連接。同等地，森林是一個無方向的無環形圖，其所有連接的成分都是樹。換句話說，該圖由樹木的不相交結合。作為特殊情況，零訂單的圖（由零樹組成的森林），一棵樹和一個無金的圖形是森林的示例。由於對於每個樹v - e = 1 ，我們可以通過減去總頂點和總邊緣之間的差異來輕鬆計算森林內的樹的數量。電視- te =森林中的樹木數。
Polytree
Polytree （或定向的樹或定向的樹或單一連接的網絡）是有向的無環圖（DAG），其基本的無向圖是樹。換句話說，如果我們用無方向的邊替換其有向邊緣，我們將獲得一個既連接又是無環的無向圖。
一些作者將“定向樹”限制在邊緣均針對特定頂點或全部遠離特定頂點的情況下（請參閱Arborescence ）。
多孔
多孔（或定向森林或定向森林）是一個有向的無環圖，其基本的無向圖是森林。換句話說，如果我們用無方向的邊替換其有向的邊緣，我們將獲得一個無環的圖形。
一些作者將“定向森林”限制在每個連接組件的邊緣都針對特定頂點的情況下，或者全部遠離特定頂點（請參閱分支）。
生根
根樹是一棵樹，其中一個頂點被指定為根。可以將根樹的邊緣分配為遠離或向根部的自然取向，在這種情況下，結構變成了定向的生根樹。當有向根的樹具有遠離根部的方向時，它稱為樹木或樹。當它具有針對根的方向時，稱為抗抗碳酸鹽或樹木。當且僅當從根到v的唯一路徑通過u時，樹是在樹的頂點上的部分排序。如果g中的每個t端的末端在此樹訂單中相當（ Diestel 2005 ，p。15），則是某些圖G的植根樹T是正常的樹。紮根的樹通常具有其他結構，例如每個頂點處的鄰居的訂購，是計算機科學中的關鍵數據結構。請參閱樹數據結構。
在樹通常具有根的上下文中，沒有任何指定根的樹稱為自由樹。
標記的樹是一棵樹，每個頂點都有一個唯一的標籤。通常給出標籤1、2 ，…， n 。遞歸樹是一個標記的生根樹，頂點標籤尊重樹序（即，如果u < v對於兩個頂點u和v ，則u的標籤小於v的標籤）。
在根樹中，頂點V的父是在根部路徑上連接到V的頂點。每個頂點都有一個獨特的父，除了根沒有父母。頂點V的孩子是一個頂點， V是父母。頂點v的上升是V的任何頂點，它是V的母體或（遞歸） V的升天。頂點V的後代是V的任何頂點，它是V的孩子，或者是（遞歸） V子的後代。到頂點v的兄弟姐妹是樹上與v共享父母的其他任何頂點。葉子是沒有孩子的頂點。內部頂點是不是葉子的頂點。
根部樹中頂點的高度是從該頂點到葉子的最長向下路徑的長度。樹的高度是根的高度。頂點的深度是通往其根（根路徑）的路徑的長度。在操縱各種自動平衡樹，尤其是AVL樹時，通常需要這。根的深度為零，葉的高度為零，並且只有一個頂點（因此均和葉子）的樹具有深度和高度為零。通常，一棵空樹（如果允許的話，沒有頂點的樹）具有深度和高度-1。
K -Ary樹（用於非負整數K ）是一棵根的樹，每個頂點最多都有K子。 2-美洲的樹通常稱為二進制樹，而3-美洲樹有時稱為三元樹。
有序樹
有序的樹（或者是平面樹或位置樹）是一個生根的樹，其中為每個頂點的孩子指定了訂購。這稱為“平面樹”，因為孩子的順序等同於在平面中嵌入樹的嵌入，其根部在頂部，每個頂點的子女低於該頂點。給定紮根樹在平面中的嵌入，如果一個人固定了孩子的方向，例如從左到右，則嵌入給孩子們訂購。相反，給定有訂單的樹，並在常規上繪製根部的根，然後可以從從左到右繪製有序樹中的子頂點，從而產生本質上獨特的平面嵌入。
特性
- 每棵樹都是兩部分圖。當且僅當它包含奇數長度的循環時，圖是兩部分。由於一棵樹根本不包含循環，因此是雙方。
- 每棵樹只有許多頂點都是平面圖。
- 每個連接的圖G都允許一個生成樹，這是一個包含g的每個頂點並且其邊緣為g的樹。跨越每一個連接的有限圖中存在的更具體的類型，包括深度優先搜索樹和廣度優先的搜索樹。概括了深度優先搜索樹的存在，每個連接的圖形只有許多頂點都有一個Trémaux樹。但是，一些不可數的-訂單圖沒有這樣的樹。
- 每個具有N > 1的頂點的有限樹具有至少兩個終端頂點（葉）。這種最小的葉子是路徑圖的特徵。最大數字n -1僅通過恆星圖實現。葉子的數量至少是最大頂點度。
- 對於樹上的任何三個頂點，它們之間的三個路徑完全具有一個共同點。更一般地，圖中的頂點屬於三個頂點中三個最短路徑的最短路徑，稱為這些頂點的中位數。因為樹上的每三個頂點都有一個獨特的中間，所以每棵樹都是中間圖。
- 每個樹都有一個由一個頂點或兩個相鄰頂點組成的中心。中心是每個最長路徑中的中間頂點或中間兩個頂點。同樣，每個n -vertex樹都有一個由一個或兩個相鄰頂點組成的質心。在第一種情況下，取出頂點將樹分裂為小於N /2頂點的子樹。在第二種情況下，去除兩個質心頂點之間的邊緣將樹拆分為正好N /2頂點的兩個子樹。
- 一棵樹的最大集團正是它的邊緣，這意味著樹類幾乎沒有集團。
枚舉
標記的樹木
Cayley的公式指出， n個標記的頂點上有N -2樹。一個經典的證明使用prüfer序列，自然會顯示出更強的結果：分別具有頂點1，2， …的樹木數量D 1 ， d 2 ，…， d n是多項式係數
一個更普遍的問題是計數跨越無向圖中的樹，該圖由矩陣樹定理解決。 （Cayley的公式是在完整圖中跨越樹的特殊情況。）在一般情況下，計算所有子樹的類似問題是＃p-Complete （ Jerrum（1994） ）。
未標記的樹
計算未標記的免費樹的數量是一個更困難的問題。對於n位頂點到圖同構的樹的數字t （ n ）尚無封閉公式。 t （ n ）的前幾個值是
Otter（1948）證明了漸近估計值
c≈0.534949606 ...和α≈2.95576528565 ... （ OEI中的序列A051491 ）。在這裡， 〜符號意味著
這是他對未標記的植根樹的漸近估計值的結果：
與D≈0.43992401257...和與上述相同的α （參見Knuth（1997） ，第2.3.4.4章和Flajolet＆Sedgewick（2009） ，第VII.5章，第475頁）。
r （ n ）的前幾個值是
樹的類型
- 路徑圖（或線性圖）由排列在行中的N頂點組成，因此頂點I和I + 1由i = 1，…， n - 1的邊緣連接。
- 一棵類似星的樹由一個稱為root的中央頂點和附加的幾個路徑圖組成。更正式的是，如果樹具有一個大於2的程度的一個頂點，那麼樹是恆星的。
- 一棵恆星是一棵樹，由一個內部頂點（以及n - 1片）組成。換句話說， n秩序的星星是n階n樹，上面有盡可能多的葉子。
- 毛毛蟲樹是一棵樹，其中所有頂點都在中央路徑子圖的距離內。
- 龍蝦樹是一棵樹，其中所有頂點都在中央路徑子圖的距離2之內。
- D學位D的常規樹是無限樹，每個頂點都有D邊緣。這些是作為自由群體的開紗圖，以及山雀建築的理論。