离散数学_屈婉玲_耿素云_张立昂_主编_课后答案_(高等教育出版社)

《离散数学》试题一 第一章部分课后习题参考 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r) 0∨(0∧1) 0 （2）（p↔r）∧(﹁q∨s) （0↔1）∧(1∨1) 0∧1 0. （3）（ p∧ q∧r）↔(p∧q∧﹁r) （1∧1∧1） ↔ (0∧0∧0) 0 (4)（ r∧s）→(p∧ q) （0∧1）→(1∧0) 0→0 1 17．判断下面一段论述是否为真：“ 是无理数。并且，如果3是无理数，则 也是无理数。另外6能被2整除，6才能被4整除。” 答：p: 是无理数 1 q: 3是无理数 0 r: 是无理数 1 s:　6能被2整除 1 t: 6能被4整除 0 命题符号化为： p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 19．用真值判断下列公式的类型： （4）(p→q) →( q→ p) （5）(p∧r) ( p∧ q) （6）((p→q) ∧(q→r)) →(p→r) 答： （4） p q p→q q p q→ p (p→q)→( q→ p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) (p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r) ( p∨(p∨q))∨( p∨r) p∨p∨q∨r 1 所以公式类型为永真式 (3) P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r) (p→(q∧r)) (4)(p∧ q)∨( p∧q) (p∨q) ∧ (p∧q) 证明（2）(p→q)∧(p→r) ( p∨q)∧( p∨r) p∨(q∧r)) p→(q∧r) （4）(p∧ q)∨( p∧q) (p∨( p∧q)) ∧( q∨( p∧q) (p∨ p)∧(p∨q)∧( q∨ p) ∧( q∨q) 1∧(p∨q)∧ (p∧q)∧1 (p∨q)∧ (p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)( p→q)→( q∨p) (2) (p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解： （1）主析取范式 ( p→q)→( q p) (p q) ( q p) ( p q) ( q p) ( p q) ( q p) ( q p) (p q) (p q) ( p q) (p q) (p q) ∑(0,2,3) 主合取范式： ( p→q)→( q p) (p q) ( q p) ( p q) ( q p) ( p ( q p)) ( q ( q p)) 1 (p q) (p q) M1 ∏(1) (2) 主合取范式为： (p→q) q r ( p q) q r (p q) q r 0 所以该式为矛盾式. 主合取范式为∏(0,1,2,3,4,5,6,7) 矛盾式的主析取范式为 0 (3)主合取范式为： (p (q r))→(p q r) (p (q r))→(p q r) ( p ( q r)) (p q r) ( p (p q r)) (( q r)) (p q r)) 1 1 1 所以该式为永真式. 永真式的主合取范式为 1 主析取范式为∑(0,1,2,3,4,5,6,7) 第三章部分课后习题参考答案 14.​  在自然推理系统P中构造下面推理的证明： (2)前提：p q, (q r),r 结论： p (4)前提：q p,q s,s t,t r 结论：p q 证明：（2） ① (q r) 前提引入 ② q r ①置换 ③q r ②蕴含等值式 ④r 前提引入 ⑤ q ③④拒取式 ⑥p q 前提引入 ⑦￢p（3） ⑤⑥拒取式 证明（4）： ①t r 前提引入 ②t ①化简律 ③q s 前提引入 ④s t 前提引入 ⑤q t ③④等价三段论 ⑥（q t） (t q)  ⑤ 置换 ⑦（q t） ⑥化简 ⑧q ②⑥ 假言推理 ⑨q p 前提引入 ⑩p ⑧⑨假言推理 (11)p q ⑧⑩合取 15在自然推理系统P中用附加前提法证明下面各推理： (1)​ 前提：p (q r),s p,q 结论：s r 证明 ①s 附加前提引入 ②s p 前提引入 ③p ①②假言推理 ④p (q r) 前提引入 ⑤q r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 16在自然推理系统P中用归谬法证明下面各推理： (1)前提：p q, r q,r s 结论： p 证明： ①p 结论的否定引入 ②p ﹁q 前提引入 ③﹁q ①②假言推理 ④￢r q 前提引入 ⑤￢r ④化简律 ⑥r ￢s 前提引入 ⑦r ⑥化简律 ⑧r ﹁r ⑤⑦ 合取 由于最后一步r ﹁r 是矛盾式,所以推理正确. 第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有 2=(x+ )(x ). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 2=(x+ )(x ). G(x): x+5=9. (1)在两个个体域中都解释为 ，在（a）中为假命题，在(b)中为真命题。 (2)在两个个体域中都解释为 ，在（a）(b)中均为真命题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素 =0. (c) 特定函数 (x,y)=x y,x,y . (d) 特定谓词 (x,y):x=y, (x,y):x,<3,3>,<4,4>} EA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>} LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} DA={<2,4>} 13.设A={<1,2>,<2,4>,<3,3>} B={<1,3>,<2,4>,<4,2>} 求A B,A B, domA, domB, dom(A B), ranA, ranB, ran(A B ), fld(A-B). 解：A B={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>} A B={<2,4>} domA={1,2,3} domB={1,2,4} dom(A∨B)={1,2,3,4} ranA={2,3,4} ranB={2,3,4} ran(A B)={4} A-B={<1,2>,<3,3>}，fld(A-B)={1,2,3} 14.设R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>} 求R R, R-1, R {0,1,}, R[{1,2}] 解：R R={<0,2>,<0,3>,<1,3>} R-1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>} R {0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>} R[{1,2}]=ran(R|{1,2})={2,3} 16．设A={a,b,c,d}， ， 为A上的关系，其中 = 求 。 解: R1 R2={,,} R2 R1={} R12=R1 R1={,,} R22=R2 R2={,,} R23=R2 R22={,,} 36．设A={1，2，3，4}，在A A上定义二元关系R， , A A ，〈u,v> R u + y = x + v. (1)​ 证明R 是A A上的等价关系. (2)确定由R 引起的对A A的划分. （1）证明：∵R u+y=x-y ∴R u-v=x-y A A ∵u-v=u-v ∴R ∴R是自反的 任意的,∈A×A 如果R ，那么u-v=x-y ∴x-y=u-v ∴R ∴R是对称的 任意的,,∈A×A 若R,R 则u-v=x-y,x-y=a-b ∴u-v=a-b ∴R ∴R是传递的 ∴R是A×A上的等价关系 (2) ∏={{<1,1>,<2,2>,<3,3>,<4,4>}, {<2,1>,<3,2>,<4,3>}, {<3,1>,<4,2>}, {<4,1>}, {<1,2>,<2,3>,<3,4>}, {<1,3>,<2,4>}, {<1,4>} } 41.设A={1，2，3，4}，R为A A上的二元关系, 〈a，b〉，〈c，d〉 A A , 〈a，b〉R〈c，d〉 a + b = c + d (1)​ 证明R为等价关系. (2)​ 求R导出的划分. (1)证明： R ∴R是自反的 任意的,∈A×A 设R，则a+b=c+d ∴c+d=a+b ∴R ∴R是对称的 任意的,,∈A×A 若R,R 则a+b=c+d,c+d=x+y ∴a+b=x+y ∴R ∴R是传递的 ∴R是 A×A上的等价关系 (2)∏={{<1,1>}, {<1,2>,<2,1>}, {<1,3>,<2,2>,<3,1>}, {<1,4>,<4,1>,<2,3>,<3,2>}, {<2,4>,<4,2>,<3,3>}, {<3,4>,<4,3>}, {<4,4>}} 43. 对于下列集合与整除关系画出哈斯图: (1) {1,2,3,4,6,8,12,24} (2) {1,2,3,4,5,6,7,8,9,10,11,12} 解: (1) (2) 45.下图是两个偏序集的哈斯图.分别写出集合A和偏序关系R 的集合表达式. (a) (b) 解: (a)A={a,b,c,d,e,f,g} R ={,,,,,,,,,} (b) A={a,b,c,d,e,f,g} R ={,,,,,,} 46.分别画出下列各偏序集的哈斯图,并找出A的极大元`极小元`最大元和最小元. (1)A={a,b,c,d,e} R ={,,,,,,} IA. (2)A={a,b,c,d,e}, R ={} IA. 解: (1) (2) 项目 (1) (2) 极大元: e a,b,d,e 极小元: a a,b,c,e 最大元: e 无 最小元: a 无 第八章部分课后习题参考答案 1．​ 设f :N N,且 f (x)= 求f (0), f ({0}), f (1), f ({1}), f ({0,2,4,6,…})，f ({4,6,8}), f -1({3,5,7}). 解：f (0)=0, f ({0})={0}, f (1)=1, f ({1})={1}, f ({0,2,4,6,…})=N，f ({4,6,8})={2,3,4}, f -1 ({3,5,7})={6,10,14}. 4. 判断下列函数中哪些是满射的?哪些是单射的?哪些是双射的? (1) f:N N, f(x)=x2+2 不是满射，不是单射 (2) f:N N,f(x)=(x)mod 3,x除以3的余数 不是满射，不是单射 (3) f:N N,f(x)= 不是满射，不是单射 (4) f:N {0,1},f(x)= 是满射，不是单射 (5) f:N-{0} R,f(x)=lgx 不是满射，是单射 (6) f:R R,f(x)=x2-2x-15 不是满射，不是单射 5. 设X={a,b,c,d},Y={1,2,3},f={,,,}判断以下命题的真假: (1)f是从X到Y的二元关系,但不是从X到Y的函数; 对 (2)f是从X到Y的函数,但不是满射,也不是单射的; 错 (3)f是从X到Y的满射,但不是单射; 错 (4)f是从X到Y的双射. 错 第十章部分课后习题参考答案 4．判断下列集合对所给的二元运算是否封闭： （1）​ 整数集合Z和普通的减法运算。 封闭,不满足交换律和结合律，无零元和单位元 （2）​ 非零整数集合 普通的除法运算。不封闭 （3）​ 全体 实矩阵集合 （R）和矩阵加法及乘法运算，其中n 2。 封闭 均满足交换律，结合律，乘法对加法满足分配律； 加法单位元是零矩阵，无零元； 乘法单位元是单位矩阵，零元是零矩阵； （4）全体 实可逆矩阵集合关于矩阵加法及乘法运算，其中n 2。不封闭 （5）正实数集合 和 运算，其中 运算定义为： 不封闭 因为 （6） 关于普通的加法和乘法运算。 封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元； 乘法无单位元（ ），零元是0； 单位元是1 （7）A = { n 运算定义如下： 封闭 不满足交换律，满足结合律， （8）S = 关于普通的加法和乘法运算。 封闭 均满足交换律，结合律，乘法对加法满足分配律 （9）S = {0,1},S是关于普通的加法和乘法运算。 加法不封闭，乘法封闭；乘法满足交换律，结合律 （10）S = ,S关于普通的加法和乘法运算。 加法不封闭，乘法封闭，乘法满足交换律，结合律 5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。 见上题 7．设 * 为 上的二元运算 ， X * Y = min ( x，y ),即x和y之中较小的数. (1)​ 求4 * 6，7 * 3。 4, 3 (2)* 在 上是否适合交换律，结合律，和幂等律？ 满足交换律，结合律，和幂等律 (3)求*运算的单位元，零元及 中所有可逆元素的逆元。 单位元无，零元1, 所有元素无逆元 8． 为有理数集，*为S上的二元运算， , S有 < a，b >* = （1）*运算在S上是否可交换，可结合？是否为幂等的？ 不可交换：*= < a，b >* 可结合：(*)*=*= *(*)=*= (*)*=*(*) 不是幂等的 （2）*运算是否有单位元，零元？ 如果有请指出，并求S中所有可逆元素的逆元。 设是单位元， S ，*= *= 则==，解的=<1,0>，即为单位。 设是零元， S ，*= *= 则==，无解。即无零元。 S，设是它的逆元*= *=<1,0> ==<1,0> a=1/x,b=-y/x 所以当x 0时， 10．令S={a，b}，S上有四个运算：*， 分别有表10.8确定。 (a) (b) (c) (d) (1)这4个运算中哪些运算满足交换律，结合律，幂等律？ (a) 交换律，结合律，幂等律都满足， 零元为a,没有单位元； (b)满足交换律和结合律，不满足幂等律，单位元为a,没有零元 (c)满足交换律,不满足幂等律,不满足结合律 没有单位元, 没有零元 (d) 不满足交换律，满足结合律和幂等律 没有单位元, 没有零元 (2)​ 求每个运算的单位元，零元以及每一个可逆元素的逆元。 见上 16．设V=〈 N，+ ， 〉，其中+ ， 分别代表普通加法与乘法，对下面给定的每个集合确定它是否构成V的子代数，为什么？ （1）S1= 是 （2）S2= 不是 加法不封闭 （3）S3 = {-1，0，1} 不是，加法不封闭 第十一章部分课后习题参考答案 8.设S={0，1，2，3}， 为模4乘法，即 " x,y∈S, x y=(xy)mod 4 问〈S， 〉是否构成群？为什么？ 解：(1) x,y∈S, x y=(xy)mod 4 , 是S上的代数运算。 (2) x,y,z∈S,设xy=4k+r (x y) z =((xy)mod 4) z=r z=(rz)mod 4 =(4kz+rz)mod 4=((4k+r)z)mod 4 =(xyz)mod 4 同理x (y z) =(xyz)mod 4 所以，(x y) z = x (y z)，结合律成立。 (3) x∈S, (x 1)=(1 x)=x,，所以1是单位元。 (4) 0和2没有逆元 所以，〈S， 〉不构成群 9.设Z为整数集合，在Z上定义二元运算。如下： " x,y∈Z,xoy= x+y-2 问Z关于o运算能否构成群？为什么？ 解：(1) x,y∈Z, xoy= x+y-2 ,o是Z上的代数运算。 (2) x,y,z∈Z, (xoy) oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4 同理(xoy)oz= xo(yoz)，结合律成立。 (3)设 是单位元， x∈Z, xo = ox=x,即x+ -2= +x-2=x, e=2 (4) x∈Z , 设x的逆元是y, xoy= yox= , 即x+y-2=y+x-2=2, 所以， 所以〈Z，o〉构成群 11.设G= ，证明G关于矩阵乘法构成一个群． 解：(1) x,y∈G, 易知xy∈G,乘法是Z上的代数运算。 (2) 矩阵乘法满足结合律 (3)设 是单位元， (4)每个矩阵的逆元都是自己。 所以G关于矩阵乘法构成一个群． 14.设G为群，且存在a∈G,使得 G={ak∣k∈Z} 证明：G是交换群。 证明: x,y∈G，设 ，则 　　 所以，G是交换群 17.设G为群，证明e为G中唯一的幂等元。 证明:设 也是幂等元，则 ，即 ，由消去律知 18.设G为群，a,b,c∈G,证明 ∣abc∣=∣bca∣=∣cab∣ 证明：先证设 设 则 ， 即　　　 左边同乘 ，右边同乘 得 　　反过来，设 则 由元素阶的定义知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣ 19.证明：偶数阶群G必含2阶元。 证明：设群G不含2阶元， ，当 时， 是一阶元，当 时， 至少是3阶元,因为群G时有限阶的，所以 是有限阶的，设 是k阶的,则 也是k阶的，所以高于3阶的元成对出现的，G不含2阶元，G含唯一的1阶元 ,这与群G是偶数阶的矛盾。所以，偶数阶群G必含2阶元 20.设G为非Abel群，证明G中存在非单位元a和b,a≠b,且ab=ba. 证明：先证明G含至少含3阶元。 若G只含1阶元,则G={e},G为Abel群矛盾； 若G除了1阶元e外,其余元 均为2阶元，则 ， ， 与G为Abel群矛盾； 所以，G含至少含一个3阶元，设为 ，则 ，且 。 令 的证。 21.设G是Mn(R)上的加法群，n≥2，判断下述子集是否构成子群。 （1）全体对称矩阵 是子群 （2）全体对角矩阵 是子群 （3）全体行列式大于等于0的矩阵. 不是子群 （4）全体上（下）三角矩阵。 是子群 22.设G为群，a是G中给定元素，a的正规化子N（a）表示G中与a可交换的元素构成的集合，即 N（a）={x∣x∈G∧xa=ax} 证明N（a）构成G的子群。 证明：ea=ae, 　　 ,所以 由 ，得 ，即 ，所以 所以N（a）构成G的子群 31.设 1是群G1到G2的同态， 2是G2到G3的同态，证明 1 2是G1到G3的同态。 证明：有已知 1是G1到G2的函数， 2是G2到G3的函数，则 1· 2是G1到G3的函数。 所以: 1· 2是G1到G3的同态。 33.证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。 证明：设G是循环群,令G=, ,令 ,那么 ,G是阿贝尔群 克莱因四元群, 是交换群,但不是循环群,因为e是一阶元，a,b,c是二阶元。 36.设 是5元置换，且 ， (1)计算 ； (2)将 表成不交的轮换之积。 (3)将（2）中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。 解：(1) (2) (3) 奇置换， 偶置换 奇置换 第十四章部分课后习题参考答案 5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G至少有多少个顶点？在最少顶点的情况下，写出度数列、 。 　　解：由握手定理图G的度数之和为： 　　　　3度与4度顶点各2个，这4个顶点的度数之和为14度。 　　　　其余顶点的度数共有6度。 　　　　其余顶点的度数均小于3，欲使G的顶点最少，其余顶点的度数应都取2, 　　所以，G至少有7个顶点, 出度数列为3,3,4,4,2,2,2, . 7、设有向图D的度数列为2，3，2，3，出度列为1，2，1，1，求D的入度列，并求 ， , . 解：D的度数列为2，3，2，3，出度列为1，2，1，1，D的入度列为1,1,1,2. , , 8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？ 解：由握手定理图G的度数之和为： 　　设2度点 个，则 ， ，该图有4个顶点. 14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。 (1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4 解：(1) 2+2+3+3+4+4+5=23 是奇数，不可图化； (2) 2＋2+2+2+3+3+4+4=16, 是偶数，可图化； 18、设有3个4阶4条边的无向简单图G1、G2、G3，证明它们至少有两个是同构的。 证明：4阶4条边的无向简单图的顶点的最大度数为3，度数之和为8，因而度数列为2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1对应的图不是简单图。所以从同构的观点看，4阶4条边的无向简单图只有两个： 所以，G1、G2、G3至少有两个是同构的。 20、已知n阶无向简单图G有m条边，试求G的补图 的边数 。 解： 21、无向图G如下图 (1)求G的全部点割集与边割集，指出其中的割点和桥； (2) 求G的点连通度 与边连通度 。 解：点割集: {a,b},(d) 边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5} = =1 23、求G的点连通度 、边连通度 与最小度数 。 解： 、 、 28、设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m问这样的无向图有几种非同构的情况？ 解： 得n=6,m=9. 31、设图G和它的部图 的边数分别为 和 ，试确定G的阶数。 解： 得 45、有向图D如图 (1)求 到 长度为1，2，3，4的通路数； (2)求 到 长度为1，2，3，4的回路数； (3)求D中长度为4的通路数； (4)求D中长度小于或等于4的回路数； (5)写出D的可达矩阵。 解：有向图D的邻接矩阵为： ， (1) 到 长度为1，2，3，4的通路数为0,2,0,0； (2) 到 长度为1，2，3，4的回路数为0,0,4,0； (3)D中长度为4的通路数为32； (4)D中长度小于或等于4的回路数10； (4)出D的可达矩阵 第十六章部分课后习题参考答案 1、画出所有5阶和7阶非同构的无向树. 2、一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点? 解：设3度分支点 个，则 ，解得 T有11个顶点 3、无向树T有8个树叶，2个3度分支点，其余的分支点都是4度顶点，问T有几个4度分支点？根据T的度数列，请至少画出4棵非同构的无向树。 解：设4度分支点 个，则 ，解得 度数列111111113344 4、棵无向树T有 (i=2，3，…，k )个i度分支点，其余顶点都是树叶，问T应该有几片树叶? 解：设树叶 片，则 ，解得 评论：2，3，4题都是用了两个结论,一是握手定理，二是 5、n(n≥3)阶无向树T的最大度 至少为几？最多为几？ 解：2，n-1 6、若n(n≥3)阶无向树T的最大度 =2，问T中最长的路径长度为几？ 解：n-1 7、证明：n(n≥2) 阶无向树不是欧拉图. 证明：无向树没有回路，因而不是欧拉图。 8、证明：n(n≥2) 阶无向树不是哈密顿图. 证明：无向树没有回路，因而不是哈密顿图。 9、证明：任何无向树T都是二部图. 证明：无向树没有回路，因而不存在技术长度的圈，是二部图。 10、什么样的无向树T既是欧拉图，又是哈密顿图? 解：一阶无向树 14、设e为无向连通图G中的一条边， e在G的任何生成树中，问e应有什么性质? 解：e是桥 15、设e为无向连通图G中的一条边， e不在G的任何生成树中， 问e应有什么性质? 解：e是环 23、已知n阶m条的无向图 G是k(k≥2)棵树组成的森林，证明：m = n-k.； 证明：数学归纳法。k=1时, m = n-1，结论成立； 设k=t-1(t-1 )时，结论成立，当k=t时, 无向图 G是t棵树组成的森林,任取两棵树，每棵树任取一个顶点，这两个顶点连线。则所得新图有t-1棵树，所以m = n-（k-1）. 所以原图中m = n-k 得证。 24、在图16.6所示2图中，实边所示的生成子图T是该图的生成树. (1)指出T的弦，及每条弦对应的基本回路和对应T的基本回路系统. (2) 指出T的所有树枝， 及每条树枝对应的基本割集和对应T的基本割集系统. (a) (b) 图16.16 解：(a)T的弦：c,d,g,h T的基本回路系统: S={{a,c,b},{a,b,f,d},{e,a,b,h},{e,a,b,f,g}} T的所有树枝: e,a,b,f T的基本割集系统: S={{e,g,h},{a,c,d,g,h},{b,c,d,g,h},{f,d,g}} (b)有关问题仿照给出 25、求图16.17所示带权图中的最小生成树. (a) (b) 图16.17 解： 注：答案不唯一。 37、画一棵权为3，4，5，6，7，8，9的最优2叉树，并计算出它的权. 38.下面给出的各符号串集合哪些是前缀码? A1={0，10，110，1111} 是前缀码 A2={1，01，001，000} 是前缀码 A3={1，11，101，001，0011} 不是前缀码 A4={b，c，aa，ac，aba，abb，abc} 是前缀码 A5={ b，c，a，aa，ac，abc，abb，aba} 不是前缀码 41.设7个字母在通信中出现的频率如下: a: 35% b: 20% c: 15% d: 10% e: 10% f: 5% g: 5% 用Huffman算法求传输它们的前缀码.要求画出最优树，指出每个字母对应的编码.并指出传输10n(n≥2)个按上述频率出现的字母，需要多少个二进制数字. 解： a:01 b:10 c:000 d:110 e:001 f:1111 g:1110 W(T)=5*4+5*4+10*3+10*3+15*3+20*2+35*2=255 传输10n(n≥2)个按上述频率出现的字母，需要255*10n-2个二进制数字.