习题课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设树中有个度为1的顶点，有个度为2的顶点，有个度为3的顶点，则这棵树有多少个顶点和多少条边？

解：设有个顶点，条边，则。由有：，解得： =2。        

故。

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

证：设是一棵具有两个顶点度数为1的树，则且。

又除两个顶点度数为1外，其他顶点度均大于等于2，故

，即

。

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

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

解：4个顶点的非同构的无向树有两棵，如图2所示；

5个顶点的非同构的无向树有3棵，如图2所示。

         （a）    (b)     (c)       (d)      (e)

图2

6个顶点的非同构的无向树有6棵，如图3所示。

图3

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

所画出的树具有6条边，因而七个顶点的度数之和应为12。由于每个顶点的度数均大于等于1，因而可产生以下七种度数序列：

（1）；（2）；（3）；（4）；（5）；

（6）；（7）。

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

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

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

在（6）中，有四个星形图，有三个是同构的，考虑到不同的排

列情况，共可产生三棵非同构的树，设为。

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

设为。

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

      T1                        T2                         T3                      T4                      T5                  T6

T7                           T8                            T9                      T10                         T11

图4

例5设无向图是由棵树构成的森林，至少在中添加多少条边才能使成为一棵树？

解：设中的个连通分支为：， ，。在中添加边，，设所得新图为，则连通且无回路，因而为树。故所加边的条数是使得为树的最小数目。

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

分析：若考虑一下数据结构中树（即有向树）的定义，则可以很简单地将树中的顶点按层次分类，偶数层顶点归于顶点集，奇数层顶点归于顶点集，图中每条边的端点一个属于，另一个属于，而不可能存在关联同一个顶点集的边。同理，对于无向树，可以从任何一个顶点出发，给该树的顶点标记奇偶性，例如，标记，与相邻的顶点标记，再给与标记为的所有相邻的顶点标记，依次类推，直到把所有的顶点标记完为止。最后，根据树的性质证明，任何边只可能关联（标记为 1的顶点集）和（标记为0的顶点集）之间的顶点。

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

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

不妨假设，若某条边关联中的两个顶点，设为和，又因为根据上述的标记法则，有到的路和到的路。设与离和最近的顶点为，所以，树中存在回路：，与树中无回路的性质矛盾。所以，任意边只能关联（标记为1的顶点集）和（标记为0的顶点集）之间的顶点。所以，任意一棵非平凡树都是偶图。

证2 设是任一棵非平凡树，则无回路，即中所有回路长都是零。而零是偶数，故由偶图的判定定理可知是偶图。

例7（1）一棵无向树有个度数为的顶点，。均为已知数，问应为多少？

（2）在（1）中，若未知，均为已知数，问应为多少？

解：（1）设为有个顶点，条边无向树，则，。由握手定理：

，有，即

                       。             ①

由式①可知：

。

（2）对于，由①可知：

                      。

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

证：设为一棵非平凡的无向树，为中最长的路，若端点和中至少有一个不是树叶，不妨设不是树叶，即有，则除与上的顶点相邻外，必存在与相邻，而不在上，否则将产生回路。于是仍为的一条比更长的路，这与为最长的路矛盾。故必为树叶。

    同理，也是树叶。

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

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

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

例10设是一个图，证明：若，则中必有回路。

证：（1）设是连通的，则

若中无回路，则是树，故与矛盾。

故中必有回路。

（2）设不连通，则中有个分支，。

若中无回路，则的各个分支中也无回路，于是各个分支都是树，所以有：，。相加得：与矛盾，故G中必有回路。

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

例11设是个正整数，，且。证明存在一棵顶点度数为的树。

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

当时，，则，故以为度数的树存在，即为一条边。

设对任意个正整数，只要，则存在一棵顶点度数为的树。

对个正整数，若有，则中必有一个数为1，必有一个数大于等于2；不妨设，因此对个正整数，有，故存在一棵顶点度数为的树。设中的度数为，在中增加一个顶点及边，得到一个图，则为树。又的顶点度数为，故由归纳法知原命题成立。

3.4 例题

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

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

证：必要性：设是连通图的桥，关联的两个顶点是和。若包含在的一个回路中，那么除边外还有一条分别以和为端点的路，所以删去边后，仍是连通的，这与是桥相矛盾。

    充分性：若边不包含在的任意回路中，则连接顶点和只有边，而不会有其它连接和的路。因为若连接和还有不同于边的路，此路与边就组成了一条包含边的回路，从而导致矛盾。所以，删去边后，和就不连通了，故边是桥。

例2设是连通图，满足下面条件之一的边应具有什么性质 ？

（1）在的任何生成树中；

（2）不在的任何生成树中。

解：（1）在的任何生成树中的边应为中的桥。

（2）不在的任何生成树中的边应为中的环。

例3 非平凡无向连通图是树当且仅当的的每条边都是桥。

证：必要性：若中存在边不是桥，则仍连通，因而之间必另有一条（不通过）的路。设此路为：，于是中有回路，这与是树矛盾，故的每条边都是桥。

    充分性：只要证明中无回路即可。

若中有回路，则中任何边都不是桥，与题设中每条边都是

桥矛盾。

例4 图1给出的带权图表示7个城市及架起城市间直接通信线路的预测造价，试给出一个设计方案使得各城市间能够通信且总造价最小，要求计算出最小总造价。

图1                   图2                        图3

解：该题就是求图的最小生成树问题。因此，图的最小生成树即为所求的通信线路图，如图2所示。其权即是最小总造价，其权为：。

例7设是一棵树，，则

（1）个顶点的树至多有多少个割点；

（2）个顶点的树有多少个桥？

解：（1）树的度为1的顶点（叶子）不是割点，而树至少有2个顶点的度为1，故树至多有个顶点为割点。

（2）树的每一条边都是桥，故个顶点的树有个桥。

例8 证明或否定断言：连通图G的任意边是G的某一棵生成树的弦。

答：错误。若e是桥，则不成立。下载本文