交大离散期末考卷lisan200701ab答案

离散数学A卷答案一、选择题CBBCBAADACACCDCDBDAD二、填空题1．||2||2BA2．22n3．154．05．06．022/2/127．V1V2V4V5V3V2V5V1(答案多种)8．无9．510．≤4/5/1≤n≤4/0n5三.(8')证明：)))(((APPPAA。设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'))))(((APPPAA四.(8')设R是A中的对称关系，且RR2，证明：RISA是A上的等价关系。证：自反性(2')，SIA对称性(已知)传递性(6')若Rcbba,,,，则有RRca2,，所以Rca,五．(8')给定4,3,2,1A和A上的关系4,3,4,2,3,2,4,1,3,1R，求：R的自反闭包、对称闭包及传递闭包的关系矩阵。000100110111101111101101001100110000000100110011自反闭包对称闭包传递闭包(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+12)d*=n-k+1证明：1)对G的每个连通支有ni-mi+(di-1)=1(1')故对G有n-m+（d-1）=k(2')即n-m+d=k+12）G*为G的对偶图，故G*为连通图，(1')n*-m*+d*=2(1')n-m+d=k+1m=m*(1')d=n*(1')故d*=n-k+1(1')离散数学B卷答案一.(8')证明：)))(((APPPAA。设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'))))(((APPPAA二.(8')设R是A中的对称关系，且RR2，证明：RISA是A上的等价关系。证：自反性(2')，SIA对称性(已知)传递性(6')若Rcbba,,,，则有RRca2,，所以Rca,三．(8')给定4,3,2,1A和A上的关系4,3,4,2,3,2,4,1,3,1R，求：R的自反闭包、对称闭包及传递闭包的关系矩阵。000100110111101111101101001100110000000100110011自反闭包对称闭包传递闭包(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+12)d*=n-k+1证明：1)对G的每个连通支有ni-mi+(di-1)=1(1')故对G有n-m+（d-1）=k(2')即n-m+d=k+12）G*为G的对偶图，故G*为连通图，(1')n*-m*+d*=2(1')n-m+d=k+1m=m*(1')d=n*(1')故d*=n-k+1(1')六、填空题1.||2||2BA2.22n3.154.05.06.022/2/127.V1V2V4V5V3V2V5V1(答案多种)8.无9.510.≤4/5/1≤n≤4/0n5七、选择题CBBCBAADACACCDCDBDAD