最小生成树性质

最小生成树性质

基本概念生成树定义树的性质最小生成树 相关性质最小边原则唯一性定理

基本概念

生成树定义

在一个$|V|$个点的无向连通图中，取其中$|V|-1$条边，并连接所有的顶点，所得到的子图称为原图的一棵生成树。

树的性质

树是图的一种特殊形态。图$G$是树当且仅当以下任意一个条件成立：

$G$有$|V|-1$条边，无环$G$有$|V|-1$条边，连通任意两点之间只有唯一的简单路径$G$连通，但任意删除一条边后就不连通

最小生成树

在一个带权的无向连通图中，各边权和最小的一棵生成树即为原图的最小生成树

相关性质

最小边原则

图中权值最小的边（如果唯一的话）一定在最小生成树上

唯一性定理

对于一个图$G$，如果图中的边权值都不相同，则图的最小生成树唯一，反之不然。