数学建模——最优连接（基于最小支撑树）

一、概念

1、图的生成树

1. 由图G=(V,E)的生成子图G1=(V,E1)(E1是E的子集）是一棵树，则称该树为图G的生成树（支撑树），简称G的树。
2. 图G有支撑树的充分必要条件为图G连通。

 2、最小生成树问题

连通图G=(V,E)，每条边上有非负权L(e)，一棵树上权的总和称为树的权，具有最小权的生成树称为最小生成树（最小支撑树），简称最小树。

许多网络问题，都可以归结为最小生成树问题：长度最小的公路网把城市连接起来；用最省的光缆把千家万户的电脑连接起来；用最省的水管把家家户户连接起来；用最少的低轨道卫星把5G信号布局全球；安排最少的节点尽快检索到需要的信息；等等。

3、最优二叉树

若二叉树的s个叶子上带权，s个权分别为p1，p2,…,ps，根到各叶子的距离（层数level）为d1,d2,…,ds，则这样的二叉树总权树为满足权和m(T)最小的二叉树称为最优二叉树。

二、求最小生成树算法

Kruskal算法

三、求最优二叉树

Huffman算法-CSDN博客