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

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

解:本题要求售货员将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

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4