一、概念
1、图的生成树
- 由图G=(V,E)的生成子图G1=(V,E1)(E1是E的子集）是一棵树，则称该树为图G的生成树（支撑树），简称G的树。
- 图G有支撑树的充分必要条件为图G连通。
2、最小生成树问题
连通图G=(V,E)，每条边上有非负权L(e)，一棵树上权的总和称为树的权，具有最小权的生成树称为最小生成树（最小支撑树），简称最小树。
许多网络问题，都可以归结为最小生成树问题：长度最小的公路网把城市连接起来；用最省的光缆把千家万户的电脑连接起来；用最省的水管把家家户户连接起来；用最少的低轨道卫星把5G信号布局全球；安排最少的节点尽快检索到需要的信息；等等。
3、最优二叉树
若二叉树的s个叶子上带权，s个权分别为p1，p2,…,ps，根到各叶子的距离（层数level）为d1,d2,…,ds，则这样的二叉树总权树为
满足权和m(T)最小的二叉树称为最优二叉树。
