推论12.2改为12.3，且增加了对于G是非连通图的证明。 【推论12.3】G为n(n≥3)阶m条边的简单平面图，则m≤3n-6,且等号成立当且仅当 G是极大平面图。 【证】依据条件G中各面的度大于等于3，由定理12.1知，3r≤2m。再由推论12.2知n- m+r=k+1≥2，即r2m-n+2,代入3r≤2m中即得m≤3n-6。由定理12.5知，G是极 大平面图当且仅当G的每个面的度为3，从而3r=2m,即m=3n-6。证毕。 14.2生成树与最小生成树 在306页最后加上下面的定理。 【定理14.*】：对连通带权图G=(V,E)运行Kruskal算法，生成的树是最小生成树。 【证】：设V=n,记T是由Kruskal算法所得到的G的一棵生成树。T中的边的标号为 e,e2,en,这是该算法产生的顺序。对于G的每棵最小生成树T',定义f(T)=k，,如 果k是使得T和T'中都包括e,e2,…ek-1但exT'的最小正整数。 令T是一棵最小生成树并且满足f(T)=”最大。如果r=n,则T=T从而结论成立。 否则，有r<n并且把T中的边e,加到T上，就产生了圈C,其中存在C的一条边e,这 条边在T中，但不在T中。 从树T开始，把e,加到T上并且删除e,我们得到一个具有n个顶点和n-1条边的连 通图。这个图是一棵生成树，记为T。T和T满足W(T)=W(T)+W(e)-W(e)。 在Kurskal算法选择了e,e2e,-1后，e,的选取要使得W(e,)最小，并且当e,加到由 e,e2…e,-组成的图上时，不会产生圈。由于W(e,)的最小性，说明了W(e)≤W(e)。因 此W(T)≤W(T)。但是由于T是最小生成树，所以必须有W(T)=W(T),所以T是最 小生成树。 是最小生成树并且和T有公共边e,e2e,-1e,所以f(T)≥r+1>r=f(T),这 就和对T的选择矛盾。因此T=T并且由Kurskal算法所产生的树是最小生成树。推论 12.2 改为 12.3，且增加了对于 G 是非连通图的证明。 【推论 12.3】G 为 n（n  3）阶 m 条边的简单平面图，则 m  3n – 6，且等号成立当且仅当 G 是极大平面图。 【证】 依据条件 G 中各面的度大于等于 3，由定理 12.1 知，3r  2m。再由推论 12.2 知 n – m + r = k + 1  2，即 r  m – n + 2，代入 3r  2m 中即得 m  3n – 6。由定理 12.5 知，G 是极 大平面图当且仅当 G 的每个面的度为 3，从而 3r = 2m，即 m = 3n – 6。证毕。 14.2 生成树与最小生成树 在 306 页最后加上下面的定理。 【定理 14.*】：对连通带权图G  (V ,E) 运行 Kruskal 算法，生成的树是最小生成树。 【证】：设|V | n ，记T 是由 Kruskal 算法所得到的 G 的一棵生成树。T 中的边的标号为 1 2 1 , , n e e e   ，这是该算法产生的顺序。对于G 的每棵最小生成树T ，定义 f (T)  k ，如 果 k 是使得T 和T 中都包括 1 2 1 , , k e e e   但 ' k e T 的最小正整数。 令T1是一棵最小生成树并且满足 1 f (T )  r 最大。如果 r  n ，则T  T1 从而结论成立。 否则，有 r  n 并且把T 中的边 r e 加到T1上，就产生了圈C ，其中存在C 的一条边 r e ，这 条边在T1中，但不在T 中。 从树T1开始，把 r e 加到T1上并且删除 r e ，我们得到一个具有 n 个顶点和 n 1条边的连 通图。这个图是一棵生成树，记为T2 。T1和T2 满足 2 1 ( ) ( ) ( ) ( ) W T W T W r r   e W e 。 在 Kurskal 算法选择了 1 2 1 , r e e e   后， r e 的选取要使得 ( ) W r e 最小，并且当 r e 加到由 1 2 1 , r e e e   组成的图上时，不会产生圈。由于 ( ) W r e 的最小性，说明了 ( ) ( ) W r r e W e 。因 此 2 1 W (T ) W (T ) 。但是由于T1是最小生成树，所以必须有 2 1 W (T ) W (T ) ，所以T2 是最 小生成树。 T2 是最小生成树并且和T1有公共边 1 2 1 , , r r e e e e   ，所以 2 1 f (T )  r 1  r  f (T ) ，这 就和对T1的选择矛盾。因此T1  T 并且由 Kurskal 算法所产生的树是最小生成树