第六章 树及割集习题课1课堂例题例1 设T 是一棵树，T 有3个度为3顶点，1个2度顶点，其余均是1度顶点。

则（1）求T 有几个1度顶点（2）画出满足上述要求的不同构的两棵树。

分析：对于任一棵树T ，其顶点数p 和边数q 的关系是：1q p =-且1deg()2ipi v q ==∑，根据这些性质容易求解。

解：（1）设该树T 的顶点数为p ，边数为q ，并设树T 中有x 个1度顶点。

于是1deg()33122ipi v x q ==⨯+⨯+=∑且31p x =++，1q p =-，得5x =。

（2）满足上述要求的两棵不同构的无向树，如图1所示。

图1例2设G 是一棵树且()G k ∆≥，证明G 中至少有k 个度为1顶点。

证：设T 中有p 个顶点，s 个树叶，则T 中其余p s -个顶点的度数均大于等于2，且至少有一个顶点的度大于等于k 。

由握手定理可得：1222()2(1)pi i q p deg v p s k s ==-=≥--++∑，有s k ≥。

所以T 中至少有k 个树叶 。

习题例1 若无向图G 中有p 个顶点，1p -条边，则G 为树。

这个命题正确吗为什么解：不正确。

3K 与平凡图构成的非连通图中有四个顶点三条边，显然它不是树。

例2设树T 中有2n 个度为1的顶点，有3n 个度为2的顶点，有n 个度为3的顶点，则这棵树有多少个顶点和多少条边解：设T 有p 个顶点，q 条边，则123161q p n n n n =-=++-=-。

由deg()2v Vv q ∈=∑有：1223322(61)122n n n q n n ⨯+⨯+⨯==-=-，解得：n =2。

故11,12q p ==。

例3证明恰有两个顶点度数为1的树必为一条通路。

证：设T 是一棵具有两个顶点度数为1的(,)p q 树，则1q p =-且1deg()2pii v q ==∑2(1)p =-。

又T 除两个顶点度数为1外，其他顶点度均大于等于2，故211deg()2deg()2(1)p p iii i v v p -===+=-∑∑，即21deg()2(2)p ii v p -==-∑。

因此2p -个分支点的度数都恰为2，即T 为一条通路。

例4 画出具有4、5、6、7个顶点的所有非同构的无向树。

解：4个顶点的非同构的无向树有两棵，如图21(),()a b 所示； 5个顶点的非同构的无向树有3棵，如图21(),(),()c d e 所示。

（a ） (b) (c) (d) (e)图26个顶点的非同构的无向树有6棵，如图3所示。

图37个顶点的非同构的无向树有11棵，如图4所示。

所画出的树具有6条边，因而七个顶点的度数之和应为12。

由于每个顶点的度数均大于等于1，因而可产生以下七种度数序列127(,,,)d d d L ：（1）1111116；（2）1111125；（3）1111134；（4）1111224；（5）1111233；（6）1112223；（7）1122222。

在（1）中只有一个星形图，因而只能产生1棵树1T 。

在（2），（3）中有两个星形图，因而也只能各产生1棵非同构的树，分别设为 23,T T 。

在（4），（5）中有三个星形图，但三个星形图是各有两个是同构的，因而各可产生两棵非同构的树，分别设为45,T T 和67,T T 。

在（6）中，有四个星形图，有三个是同构的，考虑到不同的排 列情况，共可产生三棵非同构的树，设为8910,,T T T 。

在（7）中，有五个星形图，都是同构的，因而可产生1棵树， 设为11T 。

七个顶点的所有非同构的树111T T :如图2所示。

T 1 T 2 T 3 T 4 T 5 T 6T 7 T 8 T 9 T 10 T 11图4例5设无向图G 是由(2)k k ≥棵树构成的森林，至少在G 中添加多少条边才能使G 成为一棵树解：设G 中的k 个连通分支为：12,,,k T T T L ，i v ∈i T ，1,2,,i k =L 。

在G 中添加边1{,}i i v v +，1,2,,1i k =-L ，设所得新图为T ，则T 连通且无回路，因而T 为树。

故所加边的条数1k -是使得G 为树的最小数目。

例6 证明：任意一棵非平凡树都是偶图。

分析：若考虑一下数据结构中树（即有向树）的定义，则可以很简单地将树中的顶点按层次分类，偶数层顶点归于顶点集0V ，奇数层顶点归于顶点集1V ，图G 中每条边的端点一个属于0V ，另一个属于1V ，而不可能存在关联同一个顶点集的边。

同理，对于无向树，可以从任何一个顶点V 出发，给该树的顶点标记奇偶性，例如，v 标记0，与v 相邻的顶点标记1，再给与标记为1的所有相邻的顶点标记0，依次类推，直到把所有的顶点标记完为止。

最后，根据树的性质证明，任何边只可能关联1V （标记为 1的顶点集）和0V （标记为0的顶点集）之间的顶点。

证1从任何一个顶点v 出发，给该树的顶点做标记，v 标记0，与v 相邻的顶点标记1，然后再给与标记为1的所有顶点相邻的顶点标记0，……，依次类推，直到把所有的顶点标记完为止。

下面证明：对于任何边只能关联1V （标记为1的顶点集）和0V （标记为0的顶点集）之间的顶点。

不妨假设，若某条边e 关联1V 中的两个顶点，设为1v 和2v ，又因为根据上述的标记法则，有1v 到v 的路1P 和2v 到v 的路2P 。

设1P 与2P 离1v 和2v 最近的顶点为u ，所以，树中存在回路：11221v PuP v ev ，与树中无回路的性质矛盾。

所以，任意边只能关联1V （标记为1的顶点集）和0V （标记为0的顶点集）之间的顶点。

所以，任意一棵非平凡树都是偶图。

证2 设T 是任一棵非平凡树，则T 无回路，即T 中所有回路长都是零。

而零是偶数，故由偶图的判定定理可知T 是偶图。

例7（1）一棵无向树有i n 个度数为i 的顶点，1,2,,i k =L 。

23,,,k n n n L 均为已知数，问1n 应为多少（2）在（1）中，若(3)r n r k ≤≤未知，()j n j r ≠均为已知数，问rn 应为多少解：（1）设T 为有p 个顶点，q 条边无向树，则1q p =-，1ki i p n ==∑。

由握手定理：1deg 2pii vq ==∑，有11deg 222p ki i i i v in q p =====-∑∑，即112222kki i i i in p n ===-=-∑∑。

①由式①可知：122222(2)2kkki i i i i i n in n i n ====-+=-+∑∑∑。

（2）对于3r ≥，由①可知：11(2)22k r i i i r n i n r =≠=---⎡⎤⎢⎥⎢⎥⎣⎦∑。

例8证明：任一非平凡树最长路的两个端点都是树叶。

证：设T 为一棵非平凡的无向树，12k L v v v =L 为T 中最长的路，若端点1v 和k v 中至少有一个不是树叶，不妨设k v 不是树叶，即有deg()2k v ≥，则k v 除与L 上的顶点1k v -相邻外，必存在1k v +与k v 相邻，而1k v +不在L 上，否则将产生回路。

于是11k k v v v +L 仍为T 的一条比L 更长的路，这与L 为最长的路矛盾。

故k v 必为树叶。

同理，1v 也是树叶。

例9设无向图G 中有p 个顶点，1q -条边，则G 为连通图当且仅当G 中无回路。

证：必要性：因为G 中有p 个顶点，边数1q p =-，又因为G 是连通的，由定理可知G 为树，因而G 中无回路。

充分性：因为G 中无回路，又边数1q p =-，由定理可知G 为树，所以G 是连通的。

例10设G 是一个(,)p g 图，证明：若g p ≥，则G 中必有回路。

证：（1）设G 是连通的，则若G 中无回路，则G 是树，故1q p =-与q p ≥矛盾。

故G 中必有回路。

（2）设G 不连通，则G 中有(2)k k ≥个分支，12,,,k G G G L 。

若G 中无回路，则G 的各个分支(1,2,,)i G i k =L 中也无回路，于是各个分支都是树，所以有：1i i q p =-，1,2,,i k =L 。

相加得：(2)q p k k =-≥与q p ≥矛盾，故G 中必有回路。

综上所述，图G 中必有回路。

例11设12,,,p d d d L 是p 个正整数，2p ≥，且122pi i d p ==-∑。

证明存在一棵顶点度数为12,,,p d d d L 的树。

证：对顶点p 进行归纳证明。

当2p =时，122222d d +=⋅-=，则121d d ==，故以12,d d 为度数的树存在，即为一条边。

设对任意1p -个正整数121,,,p d d d -L ，只要112(1)2p i i d p -==--∑，则存在一棵顶点度数为121,,,p d d d -L 的树。

对p 个正整数'''12,,,pd d d L ，若有'122pi i d p ==-∑，则'''12,,,p d d d L 中必有一个数为1，必有一个数大于等于2；不妨设''11,2p d d =≥，因此对1p -个正整数''''231,,,,1p pd d d d --L ，有1''2(1)2(1)2p i p i d d p -=+-=--∑，故存在一棵顶点度数为''''231,,,,1p p d d d d --L 的树'T 。

设'T 中u 的度数为'1p d -，在'T 中增加一个顶点v 及边{,}u v ，得到一个图T ，则T 为树。

又T 的顶点度数为'''12,,,pd d d L ，故由归纳法知原命题成立。

例题例1 G 的一条边e 不包含在G 的任一回路中当且仅当e 是G 的桥。

分析：这个题给出了判断桥的充要条件，应该记住。

证：必要性：设e 是连通图G 的桥，e 关联的两个顶点是u 和v 。

若e 包含在G 的一个回路中，那么除边e uv =外还有一条分别以u 和v 为端点的路，所以删去边e 后，G 仍是连通的，这与e 是桥相矛盾。

充分性：若边e 不包含在G 的任意回路中，则连接顶点u 和v 只有边e ，而不会有其它连接u 和v 的路。

因为若连接u 和v 还有不同于边e 的路，此路与边e 就组成了一条包含边e 的回路，从而导致矛盾。

所以，删去边e 后，u 和v 就不连通了，故边e 是桥。

例2设G 是连通图，满足下面条件之一的边应具有什么性质（1）在G 的任何生成树中； （2）不在G 的任何生成树中。