最小生成树
最小生成树是一副连通加权无向图中一棵权值最小的生成树。
在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即 
），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即 
）且 (V, T) 为树，使得
的 w(T) 最小，则此 T 为 G 的最小生成树。
最小生成树其实是最小权重生成树的简称。
一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言，对于非连通无向图来说，它的每一连通分量同样有最小生成树，它们的并被称为最小生成森林。
以有线电视电缆的架设为例，若只能沿着街道布线，则以街道为边，而路口为顶点，其中必然有一最小生成树能使布线成本最低。
相关性质
存在个数
最小生成树在一些情况下可能会有多个。例如，当图的每一条边的权值都相同时，该图的所有生成树都是最小生成树。
如果图的每一条边的权值都互不相同，那么最小生成树将只有一个。这一定理同样适用于最小生成森林。
证明（图的每一条边的权值皆不相同）：
- 1.
假设有两个最小生成树
和
。由于
和
是两个不同的最小生成树，那么中总会有一个或者多个边并不在中，设这些边中权值最低的那一条边为
。由于
是一个最小生成树，由树的一些定理可知
必然包含一个环
。因为环
中存在一条边
它的权值比
要大。因此用
替代
，成为了一个拥有更小权值的生成树。这和是最小生成树相矛盾，所以不可能存在两个最小生成树。
边的权值之和最低的子图
如果图的边的权值都为正数，那么最小生成树就是该图的所有包含所有顶点的子图中权值最低的子图。
环定理
对于连通图中的任意一个环
：如果
中有边
的权值大于该环中任意一个其它的边的权值，那么这个边不会是最小生成树中的边
证明：假设
属于最小生成树
，那么将删去将会使得
变为两个树。因为环必然还存在另一横切边ｆ可以连接两个子树形成生成树
，且由于
＜，生成树
权值更小，与
是最小生成树矛盾。
切分定理
在一幅连通加权无向图中，给定任意的切分，它的横切边中权值最小的边必然属于图的最小生成树。
证明：令为权重最小的横切边，
为图的最小生成树。假设
不包含
，那么如果将
加入
，得到的图必然含有一条经过的环，且这个环只是含有一条横切边--设为
，
的权重必然大于，那么用替换可以形成一个权值小于Ｔ的生成树，与为最小生成树矛盾。所以假设不成立。
最小权值边
如果图的具有最小权值的边只有一条，那么这条边包含在任意一个最小生成树中。
证明：假设该边没有在最小生成树中，那么将加入中会形成环，用替换环的另一对应的横切边，将会形成权值更小的生成树，与题设矛盾。