例:在下图中,(2)为(1)的一棵生成树T,(3) 为T的余树,但(3)不是树。 (3
例：在下图中，(2)为(1)的一棵生成树T， (3) 为T的余树，但（3）不是树。 a b c d e a b c d e a b c (1) (2) (3) d
定理:无向图G具有生成树的充分必要条件是 G为连通图。 证明:若无向图G具有生成树,显然G为连通图 以下证明若无向图G为连通图,则G具有生成树。 若连通图G无回路,则G本身就是一棵生成树;若G 至少有一个回路,删除此回路的一边,得到子图G1,它 仍然连通,并与G有相同结点集。着G1无回路,则G就 是一棵生成树:着G1仍有一个回路,再删除G1回路上 的一边。重复上述过程,直至得到一个无回路的连通图, 该图就是一棵生成树。 由该定理的证明过程可以看出,一个连通图可以有多 个生成树。因为在取定一个回路后,就可以从中去掉任 一条边,去掉的边不同,可能得到的生成树也不同
定理：无向图G具有生成树的充分必要条件是 G为连通图。 证明：若无向图G具有生成树，显然G为连通图。 以下证明若无向图G为连通图，则G具有生成树。 若连通图G无回路，则G本身就是一棵生成树；若G 至少有一个回路，删除此回路的一边，得到子图G1，它 仍然连通，并与G有相同结点集。若G1无回路，则G1就 是一棵生成树；若G1仍有一个回路，再删除G1回路上 的一边。重复上述过程，直至得到一个无回路的连通图， 该图就是一棵生成树。 由该定理的证明过程可以看出，一个连通图可以有多 个生成树。因为在取定一个回路后，就可以从中去掉任 一条边，去掉的边不同，可能得到的生成树也不同
推论1:无向连通图G有n个结点和m条边,则 m≥n-1。 证明:由上述定理的证明知,G有生成树 设为TE(G)=m,其中,E(G)是图G的边构 成的集合。|E()=n-1,其中,E(T)是树T的边 构成的集合。而E(G)E(T,所以mn-1。 推论2:在无向连通图中,一个回路和任何一 棵生成树的补至少有一条公共边。 证明:着有一个回路和一棵生成树的补 无公共边,那么,这个回路包含在该生成树 中,这与树的定义矛盾
推论1: 无向连通图G有n个结点和m条边，则 m≥n–1。 证明：由上述定理的证明知，G有生成树， 设为T。 |E(G)|=m，其中，E(G)是图G的边构 成的集合。|E(T)|=n–1, 其中，E(T)是树T的边 构成的集合。而|E(G)|≥|E(T)|，所以m≥n–1。 推论2： 在无向连通图中，一个回路和任何一 棵生成树的补至少有一条公共边。 证明：若有一个回路和一棵生成树的补 无公共边，那么，这个回路包含在该生成树 中，这与树的定义矛盾
推论3:在无向连通图中,一个边割集和 任何一棵生成树至少有一条公共边。 证明:若有一个边割集和一棵生成树 无公共边,那么,删除这个边割集所得的 子图必包含该生成树,从而该子图是连通 的。这与边割集的定义矛盾。 设G为无向连通图,有n个结点和m条 边。T为G的生成树,T有n个结点和n-1条 边。所以要得到G的一棵生成树,必须删 除G的m1(n-1)=mn+1条边
推论3： 在无向连通图中，一个边割集和 任何一棵生成树至少有一条公共边。 证明：若有一个边割集和一棵生成树 无公共边，那么，删除这个边割集所得的 子图必包含该生成树，从而该子图是连通 的。这与边割集的定义矛盾。 设G为无向连通图，有n个结点和m条 边。T为G的生成树，T有n个结点和n-1条 边。所以要得到G的一棵生成树，必须删 除G的m-(n-1)=m–n＋1条边
最小生成树 设无向连通带权图G=<vEW>T是G的一 棵生成树,T的各边权之和称为T的权,记作 W(T)。G的所有生成树中权最小的生成树称为 G的最小生成树。 求最小生成树的算法很多,我们只介绍避圈法 (克鲁斯克尔 Kruskal算法)
最小生成树 设无向连通带权图G=<V,E,W>,T是G的一 棵生成树，T的各边权之和称为T的权，记作 W(T)。G的所有生成树中权最小的生成树称为 G的最小生成树。 求最小生成树的算法很多，我们只介绍避圈法 （克鲁斯克尔Kruskal算法）