网络12离散结构下重修试卷答案

1、。装。订。线。12 年13 年第二学期离散结构（下） 重修时间共 120 分钟1. 设 V=,其中+ 和分别代表普通加法和乘法,对下面给定的每个集合确定它是否构成 V 的子代数, 为什么? (1)S1=2n|nZ; (2)S2=2n+1|nZ; (3)S3=-1,0,1.解:能不能,不能,子代数,因为 S1 对加法和乘法封闭.(2 分)(2 分)(2 分)因为 S2 对加法不封闭.因为 S3 对加法不封闭.2. 画出群的子群格.解 :是 循 环 群 ,由于 18的正因子有 1,2,3,6,9,18,故的子群有 ,.(2 分) 子群格如下:(4 分)3. 写出下图中顶点 u1 的先驱元集-(u1

2、), 后继元集+(u1), 邻域 N(u1) 及闭邻域题号一二三四总分得分阅卷人解:-(u1)=u3,u4, +(u1)=u2,u3, N(u1)=u2,u3,u4,1. 有向图 D. 求:(1)v2 到 v5 长度为 1,2,3,4 的通路数. (2)v5 到 v5 长度为 1,2,3,4 的回路数. (3)D 中长度为 4 的通路数(含回路).(4)D 中长度小于或等于 4 的回路数.解: 利用 D 的邻接矩阵的前 4 次幂解此题.aS, 故 S 非空. x,yS, S 关于的封闭性:xyxa xyS S 关于的封闭性:xaya xya (1 分)(3 分)xyS(3 分)因此是 L 的.

3、3. 证明代数 B 满足模律.a,b,cB, ac, a(bc)=(ab)c证明:a(bc)=(ab)(ac)=(ab)c.(6 分)4. 设 T 为非平凡的无向树, (T)k, 证明 T 至少有 k 片树叶.证明:方法一 设T 中有s 片树叶, 剩余的n-s 个顶点的度数大于等于 2. (1 分)性质及握手定理, 有又因为(T)k, 由树的2m=2n-2k+2(n-s-1)+s(6 分)整理后得 sk.(1 分)方法二 利用 T 中最大度顶点是割点.(1 分)设 vV(T), 且 d(v)=(T)k, 则 v 为 T 的割点, 因而 T-v 至少产生 k 个连通分支(均为树)T1,T2,Tk

4、.(3 分)若Ti 为平凡树, 则它是T 的树叶; 否则Ti 至少有两片树叶, 其中至少有 1 片是T 的树叶. 所以, T 至少有 k 片树叶.(4 分)5. 设 G 是简单平面图, 面数 r12, (G)3. 证明 G 中存在次数小于或等于 4 的面.证明:不妨设 G 是连通的,由 G 的连通性, 有n-m+r=2否则可对它的某个连通分支.(2 分)又因为(G)3, 由握手定理知2m3n=3(m-r+2)(2 分)m3r-6.(1 分)得假设每个面的次数至少是 5, 则2m5r(2 分)于是3r-6m2.5r(2 分)得 r12. 因此, 当 r12 时必存在次数小于或等于 4 的面.(1

5、 分)四、应用题 （第 1 题 10, 第 2 题 11 分，共 21 分）1. 某工厂生产由 6 种不同颜色的纱织成的双色布. 已知在一批双色布中, 每种颜色至少与其他3 种颜色相搭配. 证明可以从这批双色布中挑出 3 种, 它们由 6 种不同颜色的纱织成.解:作无向简单图 G=, V=v|v 为 6 种颜色之一, E=(u,v)|u,vV, uv 且在这批布中有 u与 v 搭配的双色布.(2 分)由已知条件可知, u,vV, 有d(u)+d(v)3+3=6=|V|(2 分)根据图的充分条件可知, G 为图.(2 分)设C=vi1vi2vi6vi1 是G 中的一条这两个顶点代表的颜色搭配成的双色布.回路. 任何两个顶点若在C 中相邻, 则在这批布中有于是,在这批布中有vi1 与vi2, vi3 与vi4, vi5 与vi6 搭配成的 3 种双色布, 它们使用了全部 6 种颜色.(4 分)2. n 位教员教n 门课程, 已知每个教员至少能教两门课程, 而每门课程至多有两位教员能教, 问能否每位教员正好教一门课?解:作二部图 G=, 其中V1=v|v 是教员, V2=u|u 为课程, E=(u,v)|vV1uV2v 能教 u.(3 分)由题设|V1|=|V2