<!--go-->

樹

圖論

共18個含義

樹（英語：tree）是一種抽象資料型別（ADT）或是實現這種抽象資料型別的資料結構，用來模擬具有樹狀結構性質的資料集合。它是由n（n0）個有限節點組成一個具有層次關係的集合。它是一種無向圖（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個點所需要的最少邊數。所以如果去掉樹中的一條邊，樹就會不連通。

Loading...

未載入完，嘗試【重新整理】or【退出閱讀模式】or【關閉廣告遮蔽】。

嘗試更換【Firefox瀏覽器】or【Chrome谷歌瀏覽器】開啟多多收藏！

移動流量偶爾打不開，可以切換電信、聯通、Wifi。

收藏網址：www.ebook8.cc

(＞人＜；)