洪帆《离散数学基础》（第三版）课后习题答案

离如下图所示，试找出完成该旅行的最短路线。

解：本题要求售货员将4个城市走且仅走一次，形成一个哈密顿环，并使得所走的路线最短。因此满足条件的走法应该是a?b?d?c?a。

18、构造互不同构的所有6结点的树。

解：先画出6个顶点，然后分别考虑顶点的度数最大为2,3,4,5的情况，不同构的树有5个，如下图所示：

19、试证明当且仅当图G中得每一条边均为割边时，图G是树林。

证明：设连通图G的每条边都是割边，则去掉任一条边后得到的子图不连通，这说明G中没有回路，根据树的定义知，G是一棵树。反之，若G是一棵树，根据树的性质，去掉任一条边后就不连通了，所以G的每条边都是割边。

20、证明或反驳下一结论：连通图G的任一边为G的某一生成树的弦。

49

解：若连通图G含有割边，则e为任何生成树的弦；

若G不含割边，那么对G的任一边e?，e?一定在某个环路?上，用破圈法构成生成树TG时，可在?中删去e?，相对生成树TG，e?一定是弦。

因此该结论当G不含割边时才成立。

21、试证明具有m条边的连通图最多具有m?1个结点。

证明：数学归纳法 当m?1时，显然一条边且连通，则只能有两个点，即n?2；假设当m?k时，点数n?k?1，则当m?k?1时，增加的一条边由于连通所以一定去某点相邻接的，因此最多增加一个点，所以点数n?k?2，所以由数学归纳法结论成立。

22、n个结点的完全图的环秩是多少？

n(n?1)22解：n个结点的完全图的边数为 C n ? ，因此其环秩为Cn?(n?1)。

2

23、一棵树有5个度为2的结点，3个度为3的结点，4个度为4的结点，2个度为5的结点，其余均为度为1的结点，问它有几个度为1的结点？ 解：设有n个度为1的结点，则总的度数为n+10+9+16+10=n+45

根据树的定义，一棵树的边数等于点数减去1，而总度数又等于边数的两倍，因此有

(n+45)/2=5+3+4+2+n-1=13+n 解得： n=19

50