内容发布更新时间 : 2024/12/31 4:21:48星期一 下面是文章的全部内容请认真阅读。
(2) 求R导出的划分. (1)证明：? a+b=a+b ∴ 任意的 任意的 ∴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} 解: 24884211263126319511 107 42 (1) (2) 45.下图是两个偏序集 >的哈斯图.分别写出集合A和偏序关系R 的集合表达式. 11 debafcgbcfdeg a (a) (b) 解: (a)A={a,b,c,d,e,f,g} R ={ (b) A={a,b,c,d,e,f,g} R ={ >的哈斯图,并找出A的极大元`极小元`最大元和最小元. 46.分别画出下列各偏序集 ={ ={ (2)A={a,b,c,d,e}, R解: edbcadeabc (1) (2) 项目 (1) (2) 极大元: e a,b,d,e 极小元: a a,b,c,e 最大元: e 无 最小元: a 无 第八章部分课后习题参考答案 1． 设f :N?N,且 ?1，若x为奇数? f (x)=?x 若x为偶数?2，?求f (0), f ({0}), f (1), f ({1}), f ({0,2,4,6,…})，f ({4,6,8}), f -1({3,5,7}). 12 解：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)=? ?1，若x为奇数?0，若x为偶数 不是满射，不是单射 ?0，若x为奇数 (4) f:N?{0,1},f(x)=? 是满射，不是单射 1，若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={ 第十四章部分课后习题参考答案 5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G至少有多少个顶点？在最少顶点的情况下，写出度数列、?(G)、?(G)。 解：由握手定理图G的度数之和为：2?10?20 3度与4度顶点各2个，这4个顶点的度数之和为14度。 其余顶点的度数共有6度。 其余顶点的度数均小于3，欲使G的顶点最少，其余顶点的度数应都取2, 所以，G至少有7个顶点, 出度数列为3,3,4,4,2,2,2,?(G)?4,?(G)?2. 7、设有向图D的度数列为2，3，2，3，出度列为1，2，1，1，求D的入度列，并求?(D),?(D)， ??(D),??(D),??(D),??(D). 解：D的度数列为2，3，2，3，出度列为1，2，1，1，D的入度列为1,1,1,2. ?(D)?3,?(D)?2,??(D)?2,??(D)?1,??(D)?2,??(D)?1 8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？ 解：由握手定理图G的度数之和为：2?6?12 13 设2度点x个，则3?1?5?1?2x?12，x?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的补图G的边数m?。 解：m??n(n?1)?m 221、无向图G如下图 (1)求G的全部点割集与边割集，指出其中的割点和桥； (2) 求G的点连通度k(G)与边连通度?(G)。 ae2be3解：点割集: {a,b},(d) e1de5ee4c 边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5} k(G)=?(G)=1 23、求G的点连通度k(G)、边连通度?(G)与最小度数?(G)。 14 解：k(G)?2、?(G)?3 、?(G)?4 28、设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m问这样的无向图有几种非同构的情况？ 解：??3n?2mn?3?m 得n=6,m=9. ?2 31、设图G和它的部图G的边数分别为m和m，试确定G的阶数。 解：m?m?n(n?1)?1?1?8(m?m)2 得n?2 45、有向图D如图 (1)求v2到v5长度为1，2，3，4的通路数； (2)求v5到v5长度为1，2，3，4的回路数； (3)求D中长度为4的通路数； (4)求D中长度小于或等于4的回路数； (5)写出D的可达矩阵。 v1v4v5v2v3 解：有向图D的邻接矩阵为： ??00001??010??202?10100???01002????020A???0??000001，A2??01010?2??10100????002?A3??20???020?01010???00?20200????000 15 00?20??00? 20??04??