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

1、第六章 树及割集习题课1课堂例题例1 设T是一棵树，T有3个度为3顶点，1个2度顶点，其余均是1度顶点。则（1）求T有几个1度顶点？（2）画出满足上述要求的不同构的两棵树。分析：对于任一棵树，其顶点数和边数的关系是：且，根据这些性质容易求解。解：（1）设该树的顶点数为，边数为，并设树中有个1度顶点。于是且，得。（2）满足上述要求的两棵不同构的无向树，如图1所示。 图1例2设G是一棵树且，证明G中至少有k个度为1顶点。证：设中有个顶点，个树叶，则中其余个顶点的度数均大于等于2，且至少有一个顶点的度大于等于。由握手定理可得：，有。所以中至少有个树叶 。习题例1 若无向图中有个顶点，条边，则为树。这

2、个命题正确吗？为什么？解：不正确。与平凡图构成的非连通图中有四个顶点三条边，显然它不是树。例2设树中有个度为1的顶点，有个度为2的顶点，有个度为3的顶点，则这棵树有多少个顶点和多少条边？解：设有个顶点，条边，则。由有：，解得：=2。 故。例3证明恰有两个顶点度数为1的树必为一条通路。证：设是一棵具有两个顶点度数为1的树，则且。又除两个顶点度数为1外，其他顶点度均大于等于2，故，即。因此个分支点的度数都恰为2，即为一条通路。例4 画出具有4、5、6、7个顶点的所有非同构的无向树。解：4个顶点的非同构的无向树有两棵，如图2所示；5个顶点的非同构的无向树有3棵，如图2所示。 （a） (b) (c)

3、(d) (e)图26个顶点的非同构的无向树有6棵，如图3所示。图37个顶点的非同构的无向树有11棵，如图4所示。所画出的树具有6条边，因而七个顶点的度数之和应为12。由于每个顶点的度数均大于等于1，因而可产生以下七种度数序列：（1）；（2）；（3）；（4）；（5）；（6）；（7）。在（1）中只有一个星形图，因而只能产生1棵树 。在（2），（3）中有两个星形图，因而也只能各产生1棵非同构的树，分别设为 。 在（4），（5）中有三个星形图，但三个星形图是各有两个是同构的，因而各可产生两棵非同构的树，分别设为和。在（6）中，有四个星形图，有三个是同构的，考虑到不同的排列情况，共可产生三棵非同构的树，

4、设为。在（7）中，有五个星形图，都是同构的，因而可产生1棵树，设为。七个顶点的所有非同构的树如图2所示。 T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11图4例5设无向图是由棵树构成的森林，至少在中添加多少条边才能使成为一棵树？解：设中的个连通分支为：，。在中添加边，设所得新图为，则连通且无回路，因而为树。故所加边的条数是使得为树的最小数目。例6 证明：任意一棵非平凡树都是偶图。分析：若考虑一下数据结构中树（即有向树）的定义，则可以很简单地将树中的顶点按层次分类，偶数层顶点归于顶点集，奇数层顶点归于顶点集，图中每条边的端点一个属于，另一个属于，而不可能存在关联同一个顶点集的

5、边。同理，对于无向树，可以从任何一个顶点出发，给该树的顶点标记奇偶性，例如，标记，与相邻的顶点标记，再给与标记为的所有相邻的顶点标记，依次类推，直到把所有的顶点标记完为止。最后，根据树的性质证明，任何边只可能关联（标记为 1的顶点集）和（标记为0的顶点集）之间的顶点。证1从任何一个顶点出发，给该树的顶点做标记，标记，与相邻的顶点标记，然后再给与标记为的所有顶点相邻的顶点标记，依次类推，直到把所有的顶点标记完为止。 下面证明：对于任何边只能关联（标记为1的顶点集）和（标记为0的顶点集）之间的顶点。不妨假设，若某条边关联中的两个顶点，设为和，又因为根据上述的标记法则，有到的路和到的路。设与离和最近

6、的顶点为，所以，树中存在回路：，与树中无回路的性质矛盾。所以，任意边只能关联（标记为1的顶点集）和（标记为0的顶点集）之间的顶点。所以，任意一棵非平凡树都是偶图。证2 设是任一棵非平凡树，则无回路，即中所有回路长都是零。而零是偶数，故由偶图的判定定理可知是偶图。例7（1）一棵无向树有个度数为的顶点，。均为已知数，问应为多少？（2）在（1）中，若未知，均为已知数，问应为多少？解：（1）设为有个顶点，条边无向树，则，。由握手定理：，有，即 。 由式可知：。（2）对于，由可知： 。例8证明：任一非平凡树最长路的两个端点都是树叶。证：设为一棵非平凡的无向树，为中最长的路，若端点和中至少有一个不是树叶，

7、不妨设不是树叶，即有，则除与上的顶点相邻外，必存在与相邻，而不在上，否则将产生回路。于是仍为的一条比更长的路，这与为最长的路矛盾。故必为树叶。 同理，也是树叶。例9设无向图中有个顶点，条边，则为连通图当且仅当中无回路。证：必要性：因为中有个顶点，边数，又因为是连通的，由定理可知为树，因而中无回路。 充分性：因为中无回路，又边数，由定理可知为树，所以是连通的。例10设是一个图，证明：若，则中必有回路。证：（1）设是连通的，则若中无回路，则是树，故与矛盾。故中必有回路。（2）设不连通，则中有个分支，。若中无回路，则的各个分支中也无回路，于是各个分支都是树，所以有：，。相加得：与矛盾，故G中必有回路

8、。综上所述，图中必有回路。例11设是个正整数，且。证明存在一棵顶点度数为的树。证：对顶点进行归纳证明。当时，则，故以为度数的树存在，即为一条边。设对任意个正整数，只要，则存在一棵顶点度数为的树。对个正整数，若有，则中必有一个数为1，必有一个数大于等于2；不妨设，因此对个正整数，有，故存在一棵顶点度数为的树。设中的度数为，在中增加一个顶点及边，得到一个图，则为树。又的顶点度数为，故由归纳法知原命题成立。3.4 例题例1 的一条边不包含在的任一回路中当且仅当是的桥。分析：这个题给出了判断桥的充要条件，应该记住。证：必要性：设是连通图的桥，关联的两个顶点是和。若包含在的一个回路中，那么除边外还有一条

9、分别以和为端点的路，所以删去边后，仍是连通的，这与是桥相矛盾。 充分性：若边不包含在的任意回路中，则连接顶点和只有边，而不会有其它连接和的路。因为若连接和还有不同于边的路，此路与边就组成了一条包含边的回路，从而导致矛盾。所以，删去边后，和就不连通了，故边是桥。例2设是连通图，满足下面条件之一的边应具有什么性质 ？（1）在的任何生成树中；（2）不在的任何生成树中。解：（1）在的任何生成树中的边应为中的桥。（2）不在的任何生成树中的边应为中的环。例3 非平凡无向连通图是树当且仅当的的每条边都是桥。证：必要性：若中存在边不是桥，则仍连通，因而之间必另有一条（不通过）的路。设此路为：，于是中有回路，这与是树矛盾，故的每条边都是桥。 充分性：只要证明中无回路即可。若中有回路，则中任何边都不是桥，与题设中每条边都是桥矛盾。例4 图1给出的带权图表示7个城市及架起城市间直接通信线路的预测造价，试给出一个设计方案使得各城市间能够通信且总造价最小，要求计算出最小总造价。图1 图2 图3解：该题就是求图的最小生成树问题。因此，图的最小生成树即为所求的通信线路图，如图2所示。其权即是最小总造价，其权为：。例7设是一棵