生成树 在图论中無向圖 G 的生成树英語Spanning Tree是具有 G 的全部顶点但边数最少的連通子圖 以 V displaystyle V 表示顶点 E displaystyle E 表示边若图 G   V  G   E  G   displaystyle GVGEG 和树 T   V  T   E  T   displaystyle TVTET 有 E  T   E  G  displaystyle ETsubset EG 和 V  G   V  T  displaystyle VGVT 那么 T displaystyle T 是 G displaystyle G 的生成树 一个图的生成树可能有多个