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

第五章习题解答 1、确定图5.36 中各点的度数，判断是否满足握手定理，是否构成一个欧拉图？是否满 足哈密尔顿的充分条件，并用 Powell 着色方法对其各个结点进行着色？给出其对偶图，并 对对偶图的结点进行着色？给出其邻接矩阵，算出任意二点之间长度为 1、2 、3、……、n-1 的路的条数，从而判断它是否连通？给出其生成树？用Prim 给出其最小生成树，用Kruskal 给出其最小生成树。 A 6 C 4 B 3 4 3 6 3 5 2 5 5 1 1 3 4 2 F 4 E 1 D 5 2 2 1 图5.36 图5.37 解：(1) Deg(A)=3 ，deg(B)=3，deg(C)=3，deg(D)=2，deg(E)=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)=4n-1，不满足哈密尔顿路存在的充分条件，但它 确实存在H 回路，说明该充分条件并不是必要的。 (4)用Powell 方法染色时，先要按结点的度数进行排序：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)=6deg(1)=deg(2)=deg(3)=deg(4)=3 5 6 A C B 4 2 3 3 5 5 2 5 1 4 1 F 4 E D 结点5 着1 号色， 结点1 着2 号色，结点3 与1 不相邻着2 号色， 结点2 着3 号色，结点4 与2 不相邻着3 号色。 (6)其邻接矩阵为： 0 0 1 0 1 ⎛1 ⎞ ⎜ ⎟ 0 0 1 1 1 ⎜0 ⎟ 1 1 0 0 1 ⎜0 ⎟ ⎜ ⎟ 0 1 0 0 1 ⎜0 ⎟