生成树

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

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