湘潭大学 刘任任版 离散数学课后习题答案 习题6 VIP专享VIP免费

22习题六1．设G是一个无回路的图,求证：若G中任意两个顶点间有惟一的通路,则G是树.证明：由假设知，G是一个无回路的连通图，故G是树。2．证明：非平凡树的最长通路的起点和终点均为悬挂点.分析：利用最长通路的性质可证。证明：设P是树T中的极长通路。若P的起点v满足1)(vd，则P不是T中极长的通路。对终点u也可同理讨论。故结论成立。3．证明：恰有两个悬挂点的树是一条通路.分析：因为树是连通没有回路的，所以树中至少存在一条通路P。因此只需证明恰有两个悬挂点的树中的所有的点都在这条通路P中即可。证明：设vu,是树T中的两个悬挂点，即1)()(vdud。因T是树，所以存在),(vu-通路P：0,1kvwuwk。显然，2)(iwd。若2)(iwd，则由T恰有两个悬挂点的假设，可知T中有回路；若T中还有顶点x不在P中，则存在),(xu-通路，显然u与x不邻接，且2)(xd。于是，可推得T中有回路，矛盾。故结论成立。4．设G是树,kG,求证：G中至少有k个悬挂点.分析：由于kG，所以G中至少存在一个顶点v的度≥k，于是至少有k个顶点与邻接，又G是树，所以G中没有回路，因此与v邻接的点往外延伸出去的分支中，每个分支的最后一个顶点必定是一个悬挂点，因此G中至少有k个悬挂点。证明：设)(GVu，且kmud)(。于是，存在)(,,1GVvvm，使miGEuvi,,1),(。若iv不是悬挂点，则有),(GVvi使。如此下去，有)()(GVvli，满足,,)(jivvjli且1)()(livd,mi,,1。故G中至少有k个悬挂点。5．设qpG,是一个图,求证：若pq,则G中必含回路.分析：利用树是没有回路且连通的图，且树中的顶点数和边数的关系可证。证明：设),(qpG有k个分支：),(][,),,(][1111kkkkqpGVGqpGVG。显然，,1kpppkqqq1。若G无回路，则每个),(iiiqpG均是树，ki,,1。于是kipqii,,1,1。从而pkpq，1k，即pq。此为矛盾，故G必含回路。6．设qpG,是有k个连通分支的图,求证：G是森林当且仅当kpq.证明：见题5的证明。237．画出4K的所有16棵生成树.解，K4的所有16棵生成树如下图所示。13241324132432413241324132413241324248．设qpG,是连通图,求证：1pq.分析：树应该是具有p个顶点中边数最少的连通图，而树中的边数q=p-1可证。证明：设G是连通图。若G无回路，则G是树，于是1pq。若G有回路，则删去G中0k条边使之保持连通且无回路。于是1pkq，即11pkpq。9．递推计算3,2K的生成树数目.132413241324132413241324132425=eK2,3e+e=e++e+e=e+++e+e+e+2610．通过考虑树中的最长通路,直接验证有标记的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），把上面四个顶点分别看作一个空，在构造树的时候可以先构造这四个顶点，剩下的一个顶点只能放在下面，选择上面四个顶点的数目应为可以从所有有标记的树的数目为45C*4！，但同样由对称性，如1234这样的排列和顶点5构成的树与1235这样的排列和4构成的数是一样的。因此这种情况下所有有标记的树的数目为：45C*4！/2=60个；对于（3），只要确定了中间度为4的顶点，这棵树就构造完了，所有这种情况下有标记的树的数目为：515C个；=++++++++e++=+++++++++++=1227解：有标记的5个顶点的树的总数为：60+60+5=125个。11．用nT表示n个顶点的有标记树的个数,求证：1112nkknCknTkTknknTn由此得恒等式1121112nknknknknnCknk分析：每个n阶树可由下面的方法构造出来：先从这n个顶点中任取k个顶点构造出一个k阶树，对剩下的n-k个顶点构造出一个n-k阶树，再将这两个树合并成一个树，显然这样得到的树是一个n阶的树。又由定理6.2.4有i个顶点的无标记的生成树共有ii-2个，可得下面的证明...