哈工大集合论习题课第六章树及割集习题课
第六章树及割集
习题课1
课堂例题
例1设T是一棵树，T有3个度为3顶点，1个2度顶点，其余均是1度顶点。则
（1）求T有几个1度顶点？
（2）画出满足上述要求的不同构的两棵树。
分析：对于任一棵树T，其顶点数p和边数q的关系是：q P 1且
p
deg（vj 2q，根据这些性质容易求解。
i 1
解：（1）设该树T的顶点数为p，边数为q，并设树T中有x个1 度顶点。于是
p
deg（v）3312 x 2q 且p 3 1 x，q p 1，得x 5。
i 1
（2）满足上述要求的两棵不同构的无向树，如图1所示。
图1
例2设G是一棵树且（G）k，证明G中至少有k个度为1顶点。证：设T中有p个顶点，s个树叶，则T中其余p s个顶点的度数均大于等于2，且至少有一个顶点的度大于等于k。由握手定理可得：
p
2q 2 p 2 deg（v i） 2（ p s 1） k s，有s k。
i 1
所以T中至少有k个树叶。
习题
例1若无向图G中有p个顶点，p 1条边，则G为树。这个命题正确吗？
为什么？
解：不正确。心与平凡图构成的非连通图中有四个顶点三条边，显然它不是树。
例2设树T中有2n个度为1的顶点，有3n个度为2的顶点，有n个度为
3的顶点，则这棵树有多少个顶点和多少条边？
解：设T 有p 个顶点，q 条边，则q P 1 2 n 3n n 1 6n 1。由 deg(v) 2q 有：1 2n 2 3n 3 n 2q 2(6n 1) 12n 2，解得：n =2。
v V
故 q 11, p 12。
例3证明恰有两个顶点度数为1的树必为一条通路。
证：设T 是一棵具有两个顶点度数为 1的(p,q)树，则q p 1且 p
deg(V i ) 2q 2(p 1)。
i 1
外，其他顶点度均大于等于2,故 p 2 deg(V i ) 2( p 1)，即
i 1 p 2
deg(V i ) 2( p 2)。
i 1
因此p 2个分支点的度数都恰为2，即T 为一条通路。
例4画出具有4、5、6、7个顶点的所有非同构的无向树。
解：4个顶点的非同构的无向树有两棵，如图 21(a),(b)所示; 5个顶点的非同构的无向树有3棵，如图21(c),(d),(e)所示。
(a ) (b) (c) (d)
(e)
图2 6个顶点的非同构的无向树有6棵，如图3所示
图3
7个顶点的非同构的无向树有11棵，如图4所示。
所画出的树具有6条边，因而七个顶点的度数之和应为 12。由 于每个顶点的度数均大于等于 1，因而可产生以下七种度数序列 (d 1,d 2,L ,d 7):
(1)1111116；(2)1111125;(3)1111134 ;(4)1111224 ；(5)1111233 ；
（6） 1112223； （7） 1122222。
又T 除两个顶点度数为
p deg(v)
i 1
在（1）中只有一个星形图，因而只能产生1棵树h。
在（2）, （3）中有两个星形图，因而也只能各产生1棵非同构的树，分别设为T2J3。
在（4），（5）中有三个星形图，但三个星形图是各有两个是同构的，因而各可产生两棵非同构的树，分别设为T4,T5和T6,T y。
在（6）中，有四个星形图，有三个是同构的，考虑到不同的排列情况，共可产生三棵非同构的树，设为T8,T9,T10。
在（7）中，有五个星形图，都是同构的，因而可产生1棵树，设为
T11。
七个顶点的所有非同构的树T1 : T11如图2所示。
T7 T8 T9 T1o 「1
图4
例5设无向图G是由k（k 2）棵树构成的森林，至少在G中添加多少条边
才能使G成为一棵树？
解：设G中的k个连通分支为：TJ丄，T＜，V i T i，i 1,2丄，k。在G 中添加边｛V i, V i 1｝，i 1,2丄，k 1，设所得新图为T，则T连通且无回路，
因而T为树。故所加边的条数k 1是使得G为树的最小数目。
例6证明：任意一棵非平凡树都是偶图
分析：若考虑一下数据结构中树（即有向树）的定义，则可以很简单地将树中的顶点按层次分类，偶数层顶点归于顶点集V o，奇数层顶点归于顶点集V1，图G中每条边的端点一个属于V。，另一个属于V1，而不可能存在关联同一个顶点集的边。同理，对于无向树，可以从任何一个顶点V出发，给该树的顶点标记奇偶性，例如，v标记0，与v 相邻的顶点标记1，再给与标记为1的所有相邻的顶点标记0，依次类推，直到把所有的顶点标记完为止。最后，根据树的性质证明，任何边只可能关联V1 （标记为1的顶点集）和V o （标记为0的顶点集）之间的顶点。
证1从任何一个顶点V出发，给该树的顶点做标记，v标记0,与V相
邻的顶点标记1，然后再给与标记为1的所有顶点相邻的顶点标记 0 ,……，依次类推，直到把所有的顶点标记完为止。
下面证明：对于任何边只能关联V i （标记为1的顶点集）和V o （标 记为0的顶点集）之间的顶点。
不妨假设，若某条边e 关联V 1中的两个顶点，设为V 1和V 2，又因为 根据上述的标记法则，有V 1到v 的路R 和V 2到v 的路P 2。设R 与P 2离w 和 v 2最近的顶点为u ,所以，树中存在回路：wRuP z V z evi ，与树中无回路 的性质矛盾。所以，任意边只能关联V 1 （标记为1的顶点集）和V o （标 记为0的顶点集）之间的顶点。所以，任意一棵非平凡树都是偶图。
证2设T 是任一棵非平凡树，则T 无回路，即T 中所有回路长都 是零。而零是偶数，故由偶图的判定定理可知 T 是偶图。 例7 （1） 一棵无向树有n 个度数为i 的顶点，i 1,2,L ,k 。n 2,匕丄，n k 均 为已知数，问n 1应为多少？
（2）在（1）中，若n r （3 r k ）未知，n j （j r ）均为已知数，问n 「 应为多少？
k
解：（1）设T 为有p 个顶点，q 条边无向树，则q p 1 , p n
i 1
由握手定理: p p degv i 2q ，有
degv i
k
i 2q 2p 2，即 i 1 i 1 i 1
k k
i 1
in i 2p 2 2 n i i 1 2 o
由式①可知： k k k
in i
2 m 2 (i 2m 2 i 2 i 2
i 2 （2）对于r 3，由①可知:
n r
（2 i ）门匚 2 o
r 2 i 1 i r 例8证明：任一非平凡树最长路的两个端点都是树叶。
证：设T 为一棵非平凡的无向树，L V 1V 2L V k 为T 中最长的路，若 端点v 1和v k 中至少有一个不是树叶，不妨设 v k 不是树叶，即有 deg （vj 2，则V k 除与L 上的顶点V k 1相邻外，必存在v k 1与V k 相邻，而V k 1 不在 L 上，否则将产生回路。于是 v 1L v k v k 1仍为 T 的一条比 L 更长的路， 这与 L 为最长的路矛盾。故 v k 必为树叶。