樹
圖論
共18個含義
【看書領紅包】關注公..眾號【書友大本營】，看書抽最高888現金紅包！
樹（英語：tree）是一種抽象數據類型（ADT）或是實現這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。它是由n（n>0）個有限節點組成一個具有層次關系的集合。它是一種無向圖（undirectedgraph），其中任意兩個頂點間存在唯一一條路徑。樹圖廣泛應用于計算機科學的數據結構中，比如二叉查找樹、堆、Trie樹以及數據壓縮中的霍夫曼樹等。
頂點
v
邊
v-1
色數
2
定義
如果一個無向簡單圖G滿足以下相互等價的條件之一，那么G是一棵樹：
G是沒有回路的連通圖。
G沒有回路，但是在G內添加任意一條邊，就會形成一個回路。
G是連通的，但是如果去掉任意一條邊，就不再連通。
G是連通的，并且3頂點的完全圖?不是G的子圖。
G內的任意兩個頂點能被唯一路徑所連通。
如果無向簡單圖G有有限個頂點（設為n個頂點），那么G是一棵樹還等價于：
G是連通的，有n?1條邊，并且G沒有簡單回路。
如果一個無向簡單圖G中沒有簡單回路，那么G是森林。
性質
一棵樹中每兩個點之間都有且只有一條路徑（指沒有重復邊的路徑）。一顆有N個點的樹有N-1條邊，也就是連接N個點所需要的最少邊數。所以如果去掉樹中的一條邊，樹就會不連通。