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

1第六章树及割集习题课1课堂例题例1设T是一棵树，T有3个度为3顶点，1个2度顶点，其余均是1度顶点。则（1）求T有几个1度顶点？（2）画出满足上述要求的不同构的两棵树。分析：对于任一棵树T，其顶点数p和边数q的关系是：1qp且1deg()2ipivq，根据这些性质容易求解。解：（1）设该树T的顶点数为p，边数为q，并设树T中有x个1度顶点。于是1deg()33122ipivxq且31px，1qp，得5x。（2）满足上述要求的两棵不同构的无向树，如图1所示。图1例2设G是一棵树且()Gk，证明G中至少有k个度为1顶点。证：设T中有p个顶点，s个树叶，则T中其余ps个顶点的度数均大于等于2，且至少有一个顶点的度大于等于k。由握手定理可得：1222()2(1)piiqpdegvpsks，有sk。所以T中至少有k个树叶。习题例1若无向图G中有p个顶点，1p条边，则G为树。这个命题正确吗？为什么？解：不正确。3K与平凡图构成的非连通图中有四个顶点三条边，显然它不是树。例2设树T中有2n个度为1的顶点，有3n个度为2的顶点，有n个度为3的顶点，则这棵树有多少个顶点和多少条边？2解：设T有p个顶点，q条边，则123161qpnnnn。由deg()2vVvq有：1223322(61)122nnnqnn，解得：n=2。故11,12qp。例3证明恰有两个顶点度数为1的树必为一条通路。证：设T是一棵具有两个顶点度数为1的(,)pq树，则1qp且1deg()2piivq2(1)p。又T除两个顶点度数为1外，其他顶点度均大于等于2，故211deg()2deg()2(1)ppiiiivvp，即21deg()2(2)piivp。因此2p个分支点的度数都恰为2，即T为一条通路。例4画出具有4、5、6、7个顶点的所有非同构的无向树。解：4个顶点的非同构的无向树有两棵，如图21(),()ab所示；5个顶点的非同构的无向树有3棵，如图21(),(),()cde所示。（a）(b)(c)(d)(e)图26个顶点的非同构的无向树有6棵，如图3所示。图37个顶点的非同构的无向树有11棵，如图4所示。所画出的树具有6条边，因而七个顶点的度数之和应为12。由于每个顶点的度数均大于等于1，因而可产生以下七种度数序列127(,,,)ddd：（1）1111116；（2）1111125；（3）1111134；（4）1111224；（5）1111233；3（6）1112223；（7）1122222。在（1）中只有一个星形图，因而只能产生1棵树1T。在（2），（3）中有两个星形图，因而也只能各产生1棵非同构的树，分别设为23,TT。在（4），（5）中有三个星形图，但三个星形图是各有两个是同构的，因而各可产生两棵非同构的树，分别设为45,TT和67,TT。在（6）中，有四个星形图，有三个是同构的，考虑到不同的排列情况，共可产生三棵非同构的树，设为8910,,TTT。在（7）中，有五个星形图，都是同构的，因而可产生1棵树，设为11T。七个顶点的所有非同构的树111TT如图2所示。T1T2T3T4T5T6T7T8T9T10T11图4例5设无向图G是由(2)kk棵树构成的森林，至少在G中添加多少条边才能使G成为一棵树？解：设G中的k个连通分支为：12,,,kTTT，iviT，1,2,,ik。在G中添加边1{,}iivv，1,2,,1ik，设所得新图为T，则T连通且无回路，因而T为树。故所加边的条数1k是使得G为树的最小数目。例6证明：任意一棵非平凡树都是偶图。分析：若考虑一下数据结构中树（即有向树）的定义，则可以很简单地将树中的顶点按层次分类，偶数层顶点归于顶点集0V，奇数层顶点归于顶点集1V，图G中每条边的端点一个属于0V，另一个属于1V，而不可能存在关联同一个顶点集的边。同理，对于无向树，可以从任何一个顶点V出发，给该树的顶点标记奇偶性，例如，v标记0，与v相邻的顶点标记1，再给与标记为1的所有相邻的顶点标记0，依次类推，直到把所有的顶点标记完为止。最后，根据树的性质证明，任何边只可能关联1V（标记为1的顶点集）和0V（标记为0的顶点集）之4间的顶点。证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，所以，树中存在回路：11221vPuPvev，与树中无回路的性质矛盾。所以，任意边只能关联1V（标记为1的顶点集）和0V（标记为0的顶点集）之间的顶点。所以，任意一棵非平凡树都是偶图。证2设T是任一棵非平凡树，则T无回路，即T中所有回路长都是零。而零是偶数，故由偶图的判定定理可知T是偶图。例7（1）一棵无向树有in个度数为i的顶点，1,2,,ik。23,,,knnn均为已知数，问1n应为多少？（2）在（1）中，若(3)rnrk未知，()jnjr均为已知数，问rn应为多少？解：（1）设T为有p个顶点，q条边无向树，则1qp，1kiipn。由握手定理：1deg2piivq，有11deg222pkiiiivinqp，即112222kkiiiiinpn。①由式①可知：122222(2)2kkkiiiiiininnin。（2）对于3r，由①可知：11(2)22kriiirninr。例8证明：任一非平凡树最长路的两个端点都是树叶。证：设T为一棵非平凡的无向树，12kLvvv为T中最长的路，若端点1v和kv中至少有一个不是树叶，不妨设kv不是树叶，即有deg()2kv，则kv除与L上的顶点1kv相邻外，必存在1kv与kv相邻，而1kv5不在L上，否则将产生回路。于是11kkvvv仍为T的一条比L更长的路，这与L为最长的路矛盾。故kv必为树叶。同理，1v也是树叶。例9设无向图G中有p个顶点，1q条边，则G为连通图当且仅当G中无回路。证：必要性：因为G中有p个顶点，边数1qp，又因为G是连通的，由定理可知G为树，因而G中无回路。充分性：因为G中无回路，又边数1qp，由定理可知G为树，所以G是连通的。例10设G是一个(,)pg图，证明：若gp，则G中必有回路。证：（1）设G是连通的，则若G中无回路，则G是树，故1qp与qp矛盾。故G中必有回路。（2）设G不连通，则G中有(2)kk个分支，12,,,kGGG。若G中无回路，则G的各个分支(1,2,,)iGik中也无回路，于是各个分支都是树，所以有：1iiqp，1,2,,ik。相加得：(2)qpkk与qp矛盾，故G中必有回路。综上所述，图G中必有回路。例11设12,,,pddd是p个正整数，2p，且122piidp。证明存在一棵顶点度数为12,,,pddd的树。证：对顶点p进行归纳证明。当2p时，122222dd，则121dd，故以12,dd为度数的树存在，即为一条边。设对任意1p个正整数121,,,pddd，只要112(1)2piidp，则存在一棵顶点度数为121,,,pddd的树。对p个正整数'''12,,,pddd，若有'122piidp，则'''12,,,pddd中必有一个数为1，必有一个数大于等于2；不妨设''11,2pdd，因此对1p个正整数''''231,,,,1ppdddd，有1''2(1)2(1)2pipiddp，故存在一棵顶点度数为''''231,,,,1ppdddd的树'T。设'T中u的度数为'1pd，在'T中增加一个顶点v及边{,}uv，得到一个图T，则T为树。又T的顶点度数为6'''12,,,pddd，故由归纳法知原命题成立。3.4例题例1G的一条边e不包含在G的任一回路中当且仅当e是G的桥。分析：这个题给出了判断桥的充要条件，应该记住。证：必要性：设e是连通图G的桥，e关联的两个顶点是u和v。若e包含在G的一个回路中，那么除边euv外还有一条分别以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）不在G的任何生成树中的边应为G中的环。例3非平凡无向连通图G是树当且仅当的G的每条边都是桥。证：必要性：若T中存在边ijevv不是桥，则Ge仍连通，因而,ijvv之间必另有一条（不通过e）的路。设此路为：11221iijijjkikjvveveevv，于是G中有回路122ijijjivevevev，这与G是树矛盾，故G的每条边都是桥。充分性：只要证明G中无回路即可。若G中有回路C，则C中任何边都不是桥，与题设中每条边都是桥矛盾。例4图1给出的带权图表示7个城市,,,,,,abcdefg及架起城市间直接通信线路的预测造价，试给出一个设计方案使得各城市间能够通信且总造价最小，要求计算出最小总造价。3681694115317282320gfedcba4938123gfedcbae8e6e5e7e4e3e2e1v5v3v4v2v17图1图2图3解：该题就是求图的最小生成树问题。因此，图的最小生成树即为所求的通信线路图，如图2所示。其权即是最小总造价，其权为：()134892348T。例7设T是一棵树，2p，则（1）p个顶点的树T至多有多少个割点；（2）p个顶点的树T有多少个桥？解：（1）树的度为1的顶点（叶子）不是割点，而树至少有2个顶点的度为1，故树至多有2p个顶点为割点。（2）树的每一条边都是桥，故p个顶点的树有1p个桥。例8证明或否定断言：连通图G的任意边是G的某一棵生成树的弦。答：错误。若e是桥，则不成立。