圖論/樹

樹是一種連通圖。有向圖是樹，如果它是連通的，沒有環，並且所有頂點最多有一個父節點。無向圖被認為是樹，如果它是連通的，有$|V|-1$條邊，並且是無環的（滿足其中兩個屬性的圖就滿足所有三個屬性）。

練習：等價定義 證明以下是對樹的等價定義 具有最小邊數且連通的圖。 具有最大邊數且無環的圖。 無環圖，在其中新增任何邊都會建立一個環。 具有 n 個節點和 n-1 條邊且連通的圖。 任何兩個節點都透過唯一的路徑連線的圖（路徑邊只能遍歷一次）。 提示：為了使總證明簡短，以合適的順序排列定義，然後證明 A=>B=>C=>D=>E=>A。尤其要注意具有零個和一個節點的圖。 此外， 圖是連通的，並且每條邊都是橋。

$tree$

無環且連通的$graph$.
$forest$是無環圖。所以，$tree\subseteq forest$

�意義

• 樹 : 最小尺寸連通圖
• 環 : 最小尺寸 2-連通圖