生成树

在图论中，無向圖 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}$的生成树。

一个图的生成树可能有多个。