图论(3)

§1.4 生成树与最小生成树

一、生成树（spanning tree）

定义1.4.1 设T是图G的一个子图，如果T是一棵树，且?(T)??(G)，则称T是G的一个生成树。

定理1.4.1 每个连通图都有生成树。

证明：设G是一个连通图。令A?{G?|G?是G的连通子图且?(G?)??(G)}。易见A非空。从A中取边数最少的一个，记为T。下证T是G的生成树。显然只需证明T是树即可。

事实上，已知T连通，下证T无圈。

若T有圈C，则去掉C上任一条边e，T?e仍连通。从而T?e?A。但T?e比T少一条边，这与T的取法矛盾。证毕。 推论1.4.1 若G连通，则????1。

证明：取G的生成树T，则?(G)??(T)??(T)?1??(G)?1。证毕。

二、最小生成树问题

问题描述：在赋权图G中，求权最小的生成树。即：求G的一棵生成树T，使得

w(T)?min?w(e)。

Te?T算法： 1. Kruskal算法

step1. take e1?E(G)such that w(e)?min{w(e)},i:?1.

e?GStep2. find ei?1?E(G)\\{e1,e2,?,ei}such that (1) G[{e1,e2,?,ei,ei?1}] does not contain any cycle, and (2) ei?1 is the one with minimum weight that meet (1). Step3. if i+1 =?(G)?1, stop; else, i:?i?1, go to step2.

定理1.4.2 设e1,e2,?,e?(G)?1是Kruskal算法获得的边，则边导出子图G[{e1,e2,?,e?(G)?1}]是G的最小生成树。

证明：记T? G[{e1,e2,?,e?(G)?1}]。显然T无圈，因此T是森林。设它有w个连通分支，则?(T*)??(T*)?w??(T*)?1?(?(G)?1)?1??(G)。但T是G的子图，故?(T)??(G)，于是

11

*

**

*

*?(T*)??(G)?1??(T*)?1。

由定理1.3.1的（3），T是一棵树，从而是G的一棵生成树。

下证其最优性，用反证法。

假设T不是权最小的生成树（下称最优树）。

对G的任一棵生成树T，记f(T)?min{i|ei?{e1,e2,?,e??1}且ei?T}。选取一棵使f(T)最大的最优树，记为T。（T不会是T）。设f(T)?k。由f(T)的定义，

*

*

~~*

~~~~~e1,e2,?,ek?1既在T*上也在T上，但ek不在T上。因此T?ek含有一个圈C。C上必有一

~~?也是一棵生成树，?)。??T*。条边ek显然T??(T?ek)?ek且w(T?)?w(T)?w(ek)?w(ek

按照算法，ek是使G[{e1,e2,?,ek}]中无圈的边中权最小的。注意

?}] 是T的子图，也无圈。故由算法规则知：w(ek?)?w(ek)。由前式，G[{e1,e2,?,ek?1,ek~~??Tw(T?)?w(T)，f(T)?k?f(T)（注意由于e1,e2,?,ek?1在T*这说明也是最优树，但

~??T*，故ek??{e1,e2,?,ek?1}）T上且ek。这与的取法矛盾。证毕。

例1.4.1 欲建设一个连接5个城市的光纤通信网络。各城市间线路的造价如图所示，求一个使总造价最少的线路建设方案。

2. Prim算法

3 6 ~v1 8.5 10v5 11 12 14 6.4 8 v2 5 v3 v4 step1. 任取v0?V(G)，令S0?{v0}，S0?V(G)\\S0，i:?0。

step2. 求Si到Si间权最小的边ei，设ei的属于Si的端点为vi，令Si?1:?Si?{vi}，

Si?1?V(G)\\Si?1。

Step3. 若i???1，停止；否则，令i:?i?1，继续step2。

12

习题一

1． 证明：??2????。

2． 如果??2,???，则连通图G至少有两个1度顶点。 3． 如果????1，则存在v?V(G)使得d(v)?3。 4． 在k度正则图G中，k??0(mod2)。

5． 晚会上大家握手言欢。证明：握过奇数次手的人必有偶数个。

6． n个运动队进行一项竞赛。已赛完n?1局。试证一定存在一个队至少参加过3局比赛。

习题二 1． 证明：若G是完全二部图，则???24。

2． 证明：若G?(X?Y,E)是一个k度正则二部图，则|X|?|Y|。 3． 若G是简单图且?(G)?k，则G有长为k的路。 4． 证明连通图中两条最长路必有公共顶点。

5． 设G是直径为2的简单图，且?(G)???2，则??2??4。 6． ??2的简单图必含有长至少为??1的圈。 7． 若???，则G中必有圈。

习题三

1． 不含圈的图称为森林（forest），证明：

（1） G是森林当且仅当????w；（2）无孤立点的森林至少有2w个1度顶点。 这里w表示G的连通分支数，孤立点指零度顶点。

2． 证明非平凡树中最长路的起点和终点都是叶子（1度点）。 3． 恰有两个叶子的树必是路。

4． 若G是树且??k，则G至少有k个1度顶点。 5． 证明每个树都是二部图。 6． 修改Kruskal算法用以：

（1）求赋权连通图中的最大权生成树；（2）求不连通赋权图中的最小权生成林。

13

课外阅读：

[1] 阅读参考书上有关内容。

[2] D. Jungnickel, Graphs, Networks and Algorithms, (Algorithms and Computation in Mathematics, Vol.5), Springer, 1998, 第3章、第4章。

[3] N.Deo and N.Kumar, Computation of Constrained Spanning Trees: A Unified Approach, in Network Optimization (P.M. Pardalos, D.W. Hearn and W.W. Hager editors.), Lecture Notes in Economics and Mathematical Systems 450, Springer-Verlag, 1997.

[4] M.R. Henzinger and V. King, Maintaining minimum spanning forests in dynamic graphs, SIAM J. Computing, 31:2(2001), pp364-374.

[5] Guoliang Xue and Shangzhi Sun, Optimal multicast tree in communication systems with channel capacities and channel reliabilities, IEEE Transactions on Communications, 47:5(1999), pp662-663.

14

第二章 图的连通性

连通图：任二顶点间有路相连。 例

可见在连通图中，连通的程度也是有高有低。

本章的目的就是定义一种参数来度量连通图连通程度的高低。

§2.1 割边、割点与连通度

一、割点：

定义2.1.1 设v?V(G)，如果w(G?v)?w(G)，则称v为G的一个割点。（该定义与某些著作有所不同，主要是在有环边的顶点是否算作割点上有区别）。

例

定理2.1.1 如果点v是图G的一个割点，则边集E(G)可划分为两个非空子集E1和E2，使得

G[E1]和G[E2]恰好有一个公共顶点v。

推论2.1.1 对连通图G，顶点v是G的割点当且仅当G?v不连通。

以上两个结论的证明留作习题。

定理2.1.2 设v是树T的顶点，则v是T的割点当且仅当d(v)?1。 证明：必要性：设v是T的割点，下面用反证法证明d(v)?1。 若d(v)?0，则T?K1，显然v不是割点。

若d(v)?1，则T?v是有?(T?v)?1条边的无圈图，故是树。从而w(T?v)?1?w(T)。因此v不是割点。

以上均与条件矛盾。

充分性：设d(v)?1，则v至少有两个邻点u,w。路uvw是T中一条(u,w)路。因T是树，uvw是T中唯一的(u,w)路，从而w(T?v)?1?w(T)。故v是割点。证毕。 推论2.1.2 每个非平凡无环连通图至少有两个顶点不是割点。

证明：设T是G的生成树，则T至少有两个叶子u,v，由上一定理知，u,v都不是T的割点，

15

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库图论(3)在线全文阅读。