离散数学 杨圣洪 第五章习题解答.pdf

《离散数学 杨圣洪 第五章习题解答.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章习题解答1、确定图5.36中各点的度数，判断是否满足握手定理，是否构成一个欧拉图？是否满足哈密尔顿的充分条件，并用Powell着色方法对其各个结点进行着色？给出其对偶图，并对对偶图的结点进行着色？给出其邻接矩阵，算出任意二点之间长度为1、2、3、……、n-1的路的条数，从而判断它是否连通？给出其生成树？用Prim给出其最小生成树，用Kruskal给出其最小生成树。A6C4B34363525511342F4E1D5221图5.36图5.37解：(1)Deg(A)=3，deg(B)=3，deg(C)=3，deg(D)=2，deg(E

2、)=5，deg(F)=2点的度数和=3+3+3+2+5+2=18边数=9，所以度数和=边数的2倍，从而满足握手定理。(2)度数为奇数的结点4个，不可能存在欧拉路，也不可能存在欧拉回路。(3)n=6，(A,B)=6，(A,C)=6，(A,D)=5,(A,E)=8,(A,F)=5,(B,C)=6,(B,D)=5,(B,E)=8,(B,F)=5,(C,D)=5,(C,E)=8,(C,F)=5,(D,E)=7,(D,F)=4

3、，先要按结点的度数进行排序：deg(E)>deg(A)=deg(B)=deg(C)>deg(D)=deg(F)。E-A-B-C-D-F用1号色对结点E进行染，未着色有：A-B-C-D-F用2号色对结点A进行染色，与A不相邻的B也染2号色，未着色C-D-F用3号色对C染色，与C不相邻的D染3号色，与C、D均不相邻的F也染3号色。(5)其对偶图如下：deg(5)=6>deg(1)=deg(2)=deg(3)=deg(4)=356ACB42335525141F4ED结点5着1号色，结点1着2号色，结点3与1不相邻着2号色，结点2着3号色，结

4、点4与2不相邻着3号色。(6)其邻接矩阵为：⎛001011⎞⎜⎟⎜001110⎟⎜⎟110010⎜⎟⎜010010⎟⎜⎟111101⎜⎟⎜⎟⎝100010⎠(7)长为1，2，3，……，n-1的路之条数长为1的路的条数⎛001011⎞⎜⎟⎜001110⎟⎜⎟110010⎜⎟⎜010010⎟⎜⎟111101⎜⎟⎜⎟⎝100010⎠长为2的路的条数，即为邻接矩阵的平方⎛001011⎞⎛001011⎞⎛321121⎞⎜⎟⎜⎟⎜⎟⎜001110⎟⎜001110⎟⎜231121⎟⎜⎟⎜⎟⎜⎟110010110010113222⎜⎟×⎜⎟=⎜⎟⎜0

5、10010⎟⎜010010⎟⎜112211⎟⎜⎟⎜⎟⎜⎟111101111101222151⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎝100010⎠⎝100010⎠⎝112112⎠长为3的路的条数，即邻接矩阵的3次方⎛321121⎞⎛001011⎞⎛447485⎞⎜⎟⎜⎟⎜⎟⎜231121⎟⎜001110⎟⎜447584⎟⎜⎟⎜⎟⎜⎟113222110010774393⎜⎟×⎜⎟=⎜⎟⎜112211⎟⎜010010⎟⎜453272⎟⎜⎟⎜⎟⎜⎟222151111101889787⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎝112112⎠⎝100010⎠⎝543272⎠

6、长为4的路条数，即邻接矩阵的4次方⎛447485⎞⎛001011⎞⎛201916122412⎞⎜⎟⎜⎟⎜⎟⎜447584⎟⎜001110⎟⎜192016122412⎟⎜⎟⎜⎟⎜⎟774393110010161623162416⎜⎟×⎜⎟=⎜⎟⎜453272⎟⎜010010⎟⎜121216121611⎟⎜⎟⎜⎟⎜⎟889787111101242424163916⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎝543272⎠⎝100010⎠⎝121216111612⎠长度为5的路的条数，即邻接矩阵的5次方⎛201916122412⎞⎛⎜001011⎞⎟⎛525

7、263437944⎞⎜⎟⎜⎟⎜192016122412⎟⎜001110⎟⎜525263447943⎟⎜161623162416⎟⎜110010⎟⎜636356408740⎟⎜⎟×⎜⎟=⎜⎟⎜121216121611⎟⎜010010⎟⎜434440286328⎟⎜⎟⎜111101⎟⎜⎟⎜242424163916⎟⎜⎟⎜7979876310463⎟⎜⎝121216111612⎟⎠⎜⎝100010⎟⎠⎜⎝444340286328⎟⎠(8)由于任何二点之间均存在长度为2的路，即任意二点之间经过二条边均可达，所以它是连通的。(9)给出其生成树？

8、n=6，任取5条不构成回路的边，便构成一棵生成树，如AC,AE,AF,EB,ED。(10)用Prim给出其最小生成树解：以边为角度，寻找边权最小的5条边。ED(1)，EC(2),AF(3),FE(4),BC(4)(11)