交大 离散 期末考卷lisanab答案.docVIP

PAGE  离散数学A卷答案 选择题 C B B C B A A D A C A C C D C D B D A D 二、填空题 15 0 / / V1V2V4V5V3V2V5V1 (答案多种) 无 5 10．≤4 / 5 / 1≤n≤4 / 0n5 三. (8) 证明：。 设x,y?A (2) {x}?P(A), {x,y}?P(A) {{x},{x,y}}? P(A) (2) {{x},{x,y}}?P(P(A)) (2) x, y?P(P(A)) {x, y|x,y?A}? P(P(A)) (2) 四. (8) 设是中的对称关系，且，证明：是上的等价关系。 证：自反性(2)， 对称性(已知) 传递性(6) 若， 则有，所以 五．(8) 给定和A上的关系， 求：R的自反闭包、对称闭包及传递闭包的关系矩阵。 自反闭包 对称闭包 传递闭包 (2) (3) (3) 六．(8) 判断下图是否为欧拉图、哈密尔顿图，如果是，则给出欧拉回路、哈密尔顿回路， 否则证明它不是。 非欧拉图，（2） 因为奇度数结点 （2） 非哈密尔顿图（2） 同构于Perterson图，Perterson图非哈密尔顿图（2） 七．(8) 若G是平面图，它的点、边、域数分别是：n、m、d，有k个连通支， G*为G的对偶图，它的点、边、域数分别是：n*、m*、d*， 证明：1) n-m+d=k+1 2) d* = n-k+1 证明：1) 对G的每个连通支有 ni-mi+(di-1)=1 (1) 故对G有 n-m+（d-1）=k (2) 即 n-m+d=k+1 2）G*为G的对偶图，故G*为连通图， (1) n*-m*+d*=2 (1) n-m+d=k+1 m=m* (1) d=n* (1) 故d* = n-k+1 (1) 离散数学B卷答案 一. (8) 证明：。 设x,y?A (2) {x}?P(A), {x,y}?P(A) {{x},{x,y}}? P(A) (2) {{x},{x,y}}?P(P(A)) (2) x, y?P(P(A)) {x, y|x,y?A}? P(P(A)) (2) 二. (8) 设是中的对称关系，且，证明：是上的等价关系。 证：自反性(2)， 对称性(已知) 传递性(6) 若， 则有，所以 三．(8) 给定和A上的关系， 求：R的自反闭包、对称闭包及传递闭包的关系矩阵。 自反闭包 对称闭包 传递闭包 (2) (3) (3) 四．(8) 判断下图是否为欧拉图、哈密尔顿图，如果是，则给出欧拉回路、哈密尔顿回路， 否则证明它不是。 非欧拉图，（2） 因为奇度数结点 （2） 非哈密尔顿图（2） 同构于Perterson图，Perterson图非哈密尔顿图（2） 五．(8) 若G是平面图，它的点、边、域数分别是：n、m、d，有k个连通支， G*为G的对偶图，它的点、边、域数分别是：n*、m*、d*， 证明：1) n-m+d=k+1 2) d* = n-k+1 证明：1) 对G的每个连通支有 ni-mi+(di-1)=1 (1) 故对G有 n-m+（d-1）=k (2) 即 n-m+d=k+1 2）G*为G的对偶图，故G*为连通图， (1) n*-m*+d*=2 (1) n-m+d=k+1 m=m* (1) d=n* (1) 故d* = n-k+1 (1) 六、填空题 15 0 / / V1V2V4V5V3V2V5V1 (答案多种) 无 5 ≤4 / 5 / 1≤n≤4 / 0n5 七、选择题 C B B C B A A D A C A C C D C D B D