习 题 六
1．设G是一个无回路的图, 求证：若G中任意两个顶点间有惟一的通路, 则G是树. 证明：由假设知，G是一个无回路的连通图，故G是树。
2．证明：非平凡树的最长通路的起点和终点均为悬挂点. 分析：利用最长通路的性质可证。
证明：设P是树T中的极长通路。若P的起点v满足d(v)?1，则P不是T中极长的通路。对终点u也可同理讨论。故结论成立。
3．证明：恰有两个悬挂点的树是一条通路.
分析：因为树是连通没有回路的，所以树中至少存在一条通路P。因此只需证明恰有两个悬挂点的树中的所有的点都在这条通路P中即可。
证明：设u,v是树T中的两个悬挂点，即d(u)?d(v)?1。因T是树，所以存在(u,v)-通路
P：uw1?wkv,k?0。显然，d(wi)?2。若d(wi)?2，则由T恰有两个悬挂点的假设，可知T中有回路；若T中还有顶点x不在P中，则存在(u,x)-通路，显然u与x不邻接，且d(x)?2。于是，可推得T中有回路，矛盾。故结论成立。
4．设G是树, ??G??k, 求证：G中至少有k个悬挂点.
分析：由于??G??k，所以G中至少存在一个顶点v的度≥k，于是至少有k个顶点与邻接，又G是树，所以G中没有回路，因此与v邻接的点往外延伸出去的分支中，每个分支的最后一个顶点必定是一个悬挂点，因此G中至少有k个悬挂点。
证明：设u?V(G)，且d(u)?m?k。于是，存在v1,?,vm?V(G)，使
(l)uvi?E(G),i?1,?,m。若vi不是悬挂点，则有vi??V(G),使。如此下去，有vi?V(G)，
满足vi(l)?vj,i?j,且d(vi(l))?1, i?1,?,m。故G中至少有k个悬挂点。
5．设G?p,q?是一个图, 求证：若q?p, 则G中必含回路.
分析：利用树是没有回路且连通的图，且树中的顶点数和边数的关系可证。
证明：设G(p,q)有k个分支：G[V1]?G1(p1,q1),?,G[Vk]?Gk(pk,qk)。显然，
p?p1???pk,q?q1???qk。若G无回路，则每个Gi(pi,qi)均是树，i?1,?,k。
于是qi?pi?1,i?1,?,k。从而 q?p?k?p，k?1，即q?p。此为矛盾，故G必含回路。
6．设G?p,q?是有k个连通分支的图, 求证：G是森林当且仅当q?p?k.
证明：见题5的证明。
22
7．画出K4的所有16棵生成树.
解，K4的所有16棵生成树如下图所示。
1
4 4 1
4 2
1
3 4 2 1
3
4 2
1
3
4 23
2
1
3 4 2 1
3 4 2
1
3
4 2
3
2
3
2
3
1
2
1
2
1
2
4 3
4 3
4 3
1
2
1
2
1
2
4 3
4 3
4 3
1
2
4 3
8．设G?p,q?是连通图, 求证：q?p?1.
分析：树应该是具有p个顶点中边数最少的连通图，而树中的边数q=p-1可证。
证明：设G是连通图。若G无回路，则G是树，于是q?p?1。若G有回路，则删去G中k?0条边使之保持连通且无回路。于是q?k?p?1，即q?p?1?k?p?1。 9．递推计算K2,3的生成树数目.
24
e e =
e +
K2,3 e e +
+ +
e =
+ + + +
e e + +
25
=
e e
=
+ +
+ + + + + +
e +
+ =
+ + + + + =12
+ + + + + +
10．通过考虑树中的最长通路, 直接验证有标记的5个顶点的树的总数为125.
分析：设树中5个顶点的标记分别为1，2，3，4，5。而5个顶点的树的最长通路只能是4、3、2，如下（1）（2）（3）所示。 (1) 最长通路长度为4；
(2) 最长通路长度为3；
（3） 最长通路长度为2。 对于（1），把每个顶点看作是一个空，不同的顶点序列对应不同的树，但由于对称性12345和54321所形成的树应该是同一棵树，因此这种情况下所有有标记的树的数目为：5！/2=60个； 对于（2），把上面四个顶点分别看作一个空，在构造树的时候可以先构造这四个顶点，剩下的一
个顶点只能放在下面，选择上面四个顶点的数目应为可以从所有有标记的树的数目为C54*4！，但同样由对称性，如1234这样的排列和顶点5构成的树与1235这样的排列和4构
成的数是一样的。因此这种情况下所有有标记的树的数目为：C5*4！/2=60个； 对于（3），只要确定了中间度为4的顶点，这棵树就构造完了，所有这种情况下有标记的树的数
1目为：C5?5个；
4 26
相关推荐：
loading