生成樹

在圖論中，無向圖 G 的生成樹（英語：Spanning Tree）是具有 G 的全部頂點，但邊數最少的連通子圖。^[1]

格子圖（英語：grid graph）的生成樹（圖中的藍色粗線）

8x8網格圖上的三個例子

以${\displaystyle V}$表示頂點，${\displaystyle E}$表示邊，若圖 ${\displaystyle G=(V(G),E(G))}$和樹${\displaystyle T=(V(T),E(T))}$，有${\displaystyle E(T)\subset E(G)}$和${\displaystyle V(G)=V(T)}$，那麼${\displaystyle T}$是${\displaystyle G}$的生成樹。

一個圖的生成樹可能有多個。