哈工大集合论习题课-第六章树及割集习题课

1、第六章树及割集习题课1课堂例题例1设T是一棵树，T有3个度为3顶点，1个2度顶点，其余 均是1度顶点。则(1)求T有几个1度顶点(2)画出满足上述要求的不同构的两棵树。分析：对于任一棵树T ,其顶点数p和边数q的关系是：q p 1且pdeg(Vi) 2q ,根据这些性质容易求解。 i 1解：(1)设该树T的顶点数为p,边数为q,并设树T中有x个1 度顶点。于是pdeg(Vi) 3 3 12 x 2q 且 p 3 1 x, q p1,得 x 5。 i 1(2)满足上述要求的两棵不同构的无向树，如图 1所示。图1例2设G是一棵树且(G) k ,证明G中至少有k个度为1项电c 证：设T中有p个顶点，

2、s个树叶，则T中其余p s个顶点的度数 均大于等于2,且至少有一个顶点的度大于等于k。由握手定理可得：p2q 2 p 2deg(vi) 2( p s 1) k s,有 s k。i 1所以T中至少有k个树叶。习题例1若无向图G中有p个顶点，p 1条边，则G为树。这个命题正确 吗为什么解：不正确。K3与平凡图构成的非连通图中有四个顶点三条边，显然它不是树。例2设树T中有2n个度为1的顶点，有3n个度为2的顶点，有n个度为3的顶点，则这棵树有多少个顶点和多少条边解：设T有p个顶点，q条边，则q p 1 2n 3n n 1 6n 1deg(v) 2q 有：12n 2 3n 3 n 2q 2(6n 1)

3、 12n 2,解得：n=2。 v V故 q 11, p 12。例3证明恰有两个顶点度数为1的树必为一条通路。证：设T是一棵具有两个顶点度数为1的(p,q)树，则q p 1且pdeg(Vi) 2q 2( p 1)。 i 1又T除两个顶点度数为1外，其他顶点度均大于等于2,故pp 2deg(Vi) 2deg(Vi) 2( p 1),即i 1i 1p 2 deg(Vi) 2( p 2)。1 1因此p 2个分支点的度数都恰为2,即T为一条通路。例4画出具有4、5、6、7个顶点的所有非同构的无向树。解：4个顶点的非同构的无向树有两棵，如图 21(a),(b)所示;5个顶点的非同构的无向树有3棵,如图21

4、(c),(d),(e)所示。（a） (b)(c)(d)(e)图26个顶点的非同构的无向树有6棵，如图3所示图37个顶点的非同构的无向树有11棵，如图4所示。所画出的树具有6条边，因而七个顶点的度数之和应为12。由于每个顶点的度数均大于等于1,因而可产生以下七种度数序列(d1,d2,L )：(1) 1111116； 1111125； (3) 1111134; (4) 1111224; (5) 1111233；（b） 1112223； （7） 1122222。在（1）中只有一个星形图，因而只能产生 1棵树3。在（2）, （3）中有两个星形图，因而也只能各产生1棵非同构的 树，分别设为丁2,丁3。在

5、（4）, （5）中有三个星形图，但三个星形图是各有两个是同构的，因而各可产生两棵非同构的树，分别设为T4,T5和丁6,丁7。在（6）中，有四个星形图，有三个是同构的，考虑到不同的排列情况，共可产生三棵非同构的树，设为 T8,T9,T10。在（7）中，有五个星形图，都是同构的，因而可产生1棵树，设为T11。七个顶点的所有非同构的树丁1：丁11如图2所示。T2T3T4T72）棵树构成的森林，至少在G中添加多少条T 1T9图4例5设无向图G是由k（k 边才能使G成为一棵树解：设G中的k个连通分支为：T1,T2,L ,Tk , Vi Ti , i 1,2,L ,k。在G 中添加边MM 1 , i 1,

6、2,L ,k 1 ,设所得新图为T ,则T连通且无回路， 因而T为树。故所加边的条数k 1是使得G为树的最小数目。 例6证明：任意一棵非平凡树都是偶图。分析：若考虑一下数据结构中树（即有向树）的定义，则可以很 简单地将树中的顶点按层次分类， 偶数层顶点归于顶点集K,奇数层 顶点归于顶点集V1 ,图G中每条边的端点一个属于Vo ,另一个属于V1 , 而不可能存在关联同一个顶点集的边。同理，对于无向树，可以从任 何一个顶点V出发，给该树的顶点标记奇偶性，例如，v标记0,与v 相邻的顶点标记1,再给与标记为1的所有相邻的顶点标记0,依次类 推，直到把所有的顶点标记完为止。最后，根据树的性质证明，任何

7、 边只可能关联V1 （标记为1的顶点集）和Vo （标记为0的顶点集）之 间的顶点。证1从任何一个顶点V出发，给该树的顶点做标记，V标记0,与 V相邻的顶点标记1,然后再给与标记为1的所有顶点相邻的顶点标记 0,，依次类推，直到把所有的顶点标记完为止。下面证明：对于任何边只能关联Vi (标记为1的顶点集)和Vo (标 记为0的顶点集)之间的顶点。不妨假设，若某条边e关联V中的两个顶点，设为和V2,又因为 根据上述的标记法则，有必至八的路P和V2至卜的路P2。设P1与P2离V1和 v2最近的顶点为u ,所以，树中存在回路：v1PuP2V2ev1 ,与树中无回路 的性质矛盾。所以，任意边只能关联V1

8、 (标记为1的顶点集)和V。(标 记为0的顶点集)之间的顶点。所以，任意一棵非平凡树都是偶图。证2设T是任一棵非平凡树，则T无回路，即T中所有回路长都 是零。而零是偶数，故由偶图的判定定理可知 T是偶图。例7(1) 一棵无向树有n个度数为i的顶点，i 1,2,L ,k。e,飞人，、均 为已知数，问应为多少(2)在(1)中，若n,(3 r k)未知，nj(j r)均为已知数，问n, 应为多少k解：(1)设T为有p个顶点，q条边无向树，则q p 1, p r。i 1由握手定理：PPkdegvi 2q , 有 degviini 2q 2p 2 , 即i 1i 1i 1kkini 2P 2 2 ni

9、2。i 1i 1由式可知：kkknn2ni 2 (i 2)5 2。i 2i 2i 2(2)对于r 3,由可知：1 k ,nr (2 i)ni 2 。r 2 i 1 i r例8证明：任一非平凡树最长路的两个端点都是树叶。证：设T为一棵非平凡的无向树，L V1V2L Vk为T中最长的路，若 端点V1和Vk中至少有一个不是树叶，不妨设Vk不是树叶，即有deg(Vk) 2 ,则Vk除与L上的顶点Vk 1相邻外，必存在Vk 1与Vk相邻，而Vk 1 不在L上，否则将产生回路。于是ML VkVk i仍为T的一条比L更长的路，这与 L 为最长的路矛盾。故vk 必为树叶。同理，v1也是树叶。例 9 设无向图G

10、 中有 p 个顶点， q 1条边， 则 G 为连通图当且仅当G 中无回路。证 ：必要性：因为G 中有 p 个顶点，边数q p 1 ，又因为G 是连通的，由定理可知G 为树，因而G 中无回路。充分性：因为G 中无回路，又边数q p 1 ，由定理可知G 为树，所以 G 是连通的。例10设G是一个(p,g)图，证明：若g p,则G中必有回路。证：(1)设G是连通的，则若 G 中无回路，则G 是树，故q p 1 与 q p 矛盾。故 G 中必有回路。(2)设G不连通，则G中有k(k 2)个分支，G1,G2,L,Gk。若G中无回路，则G的各个分支G"i 1,2,L ,k)中也无回路，于是各个分

11、支都是树，所以有：qi pi 1 ， i 1,2,L ,k。 相加得：q p k(k 2)与q p矛盾，故G中必有回路。综上所述，图G 中必有回路。p例11设di,d2,L ,dp是p个正整数，p 2,且 di 2P 2。证明存在一棵顶点度数为d1,d2,L ,dp的树。i1证： 对顶点 p 进行归纳证明。当p 2时，d d2 2 2 2 2,则d1 d2 1 ,故以d1,d2为度数的树存在，即为一条边。p1设对任意p 1 个正整数d1,d2,L ,dp 1，只要di 2(p 1) 2，则存i1在一棵顶点度数为d1,d2,L ,dp 1的树。p对p个正整数d；,d2,L ,dp ,若有 d；

12、2P 2 ,则d；,d2,L ,dp中必有 i1一个数为1，必有一个数大于等于2；不妨设d1' 1,d'p 2，因此对p 1p1个正整数d2',d3',L ,dp' 1,d'p 1， 有di' (d'p 1) 2( p 1) 2， 故存在一棵顶i2点度数为d2,d3,L ,dp 1,dp 1的树T。设T中u的度数为dp 1,在丁中增加一个顶点v及边u,v,得到一个图T ,则T为树。又T的顶点度数为d；,d2,L ,dp,故由归纳法知原命题成立例题例1 G的一条边e不包含在G的任一回路中当且仅当e是G的桥。分析：这个题给出了判断桥的

13、充要条件，应该记住。证：必要性：设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的任何生成树中。解：(1)在G的任何生成树中的边应为G中的桥。(2)不

14、在G的任何生成树中的边应为G中的环。例3非平凡无向连通图G是树当且仅当的G的每条边都是桥。证：必要性：若T中存在边e vm不是桥，则G e仍连通，因而mm 之间必另有一，条(不通过e)的路。设此路为：vi vi1ejivi2ej2L 与刈vj , 于是G中有回路丫102021 vjev ,这与G是树矛盾，故G的每条边都是 桥。充分性：只要证明G中无回路即可。若G中有回路C ,则C中任何边都不是桥，与题设中每条边都是 桥矛盾。例4图1给出的带权图表示7个城市a,b,c,d,e, f ,g及架起城市间直接 通信线路的预测造价，试给出一个设计方案使得各城市间能够通信且 总造价最小，要求计算出最小总造价。bb20231523g36281617图1图2图3解 ：该题就是求图的最小生成树问题。因此，图的最小生成树即为所求的通信线路图，如图2 所示。