《【浙江工商大学】《离散数学》期末考试题(L)参考答案》由会员分享，可在线阅读，更多相关《【浙江工商大学】《离散数学》期末考试题(L)参考答案（2页珍藏版）》请在金锄头文库上搜索。
1、一、1. , 1, 3. 2. 4n + 2, (2n + 1)2, 2n2 + 1. 3. 2n, , X. 4. . 543253124vvvvvvvvv5. 2, 3, 2.二、15: CBABB; 610 CCCBA.三、1(); 2(); 3(); 4(); 5().四、解解 令 p: 小张去看电影, q: 小王去看电影, r: 小李去看电影, s: 小赵去看电影.(5 分)rsqpsrqp,(1) s P(附加) (2) Pps (3) p T(1)(2)I (4) q P (5) T(3)(4)Iqp (6) Prqp(7) r T(5)(6) (10 分)五、证证 因为 R 传
2、递，所以. (5 分)RRRo对于任意，由于 R 自反，于是，进而，因此Ryx),(Ryy),(RRyxo),(. (5 分)RRRo故.RRRo六、解解 (1), . (5 分)0010101011001010A1110111011101111P(2) , ,. (5 分)10001110102011102A00102120221021203A11001100314032304A七、解解 AB = , , 1, 1.AB = (A - B)(B - A) = 1 = , 1. (5 分)+P(A) = , , , 1, A. (5 分) 八、证证 用一个节点代表一个人, 若两个人是朋友，则对
3、应的两个节点邻接，于是得到一个 n 阶简单无向图 G = (V, E). 对于 G 的任意两个不相邻的节点 u 和 v, 考虑 w V u, v, 根据已知条件知，u 与 w 或 v 与 w 必相邻. 由于节点 u 和 v 不相邻，于是 u 与 w 且 v 与 w 必相邻. 根据 w 的任意性 知, deg(u)n 2 且 deg(u)n 2, 因而有 deg(u) + deg(u)2(n 2). (5 分)(1) 当 n3 时, deg(u) + deg(u)2(n 2) n 1, 因而 G 中存在 H 路. (2) 当 n4 时, deg(u) + deg(u)2(n 2) n, 因而 G 中存在 H 回路. (5 分)
