《离散数学 Discrete Mathematics》课程教学资源（习题集）集合与图论期终考试试题2012级（b卷）解答.doc_大学文库

第 2 页（装订线内不要答题） 4．设 A, B 是集合，若存在 A 到 B 的满射，则|B||A|。（真）设存在 A 到 B 的满射 f，对任意 bB，存在 xA，f(a)=b。而由函数的定义，f(a1)=b1，f(a2)=b2，若 b1b2，则 a1a2。则|B||A|。二、证明：任何平面图是 5-可着色的。（10 分）证明：定理 9.10 证明，112 页。三、如果在一个地图上任何两个地区都相邻，问在该地图上最多有几个地区？（10 分） 4 四、R 是集合 A 上的等价关系，|A|=n，|R|=s。对于 A 关于 R 的商集 A/R，|A/R|=r。证明： rsn 2。（14 分）习题解析： • R、A 和 A/R 三者的基数之间存在什么关系？ 1）R 是集合 A 上的等价关系 R 对 A 形成的一个划分，这个划分就是商集 A/R。 2）取划分的一个块，若块中元素 k 个，则该块产生的有序对为 k 2 个。 3）r 个块的有序对相加，和等于 s。r 个块中所含元素的个数相加，和等于 n。证明思路和过程：设 A/R 的 r 个等价类集合的元素个数分别是 m1, m2, …, mr。则 m1+m2+… … +mr =n， m1 2+m2 2+… … +mr 2 =s。因此，问题转换为证明(m1 2+m2 2+… … +mr 2 )/r(( m1+m2+… … +mr)/r)2，即证明 r (m1 2+m2 2+… … +mr 2 ) ( m1+m2+… … +mr) 2。（可以用数学归纳法进行证明）。数学归纳法证明：r (m1 2+m2 2+… … +mr 2 ) ( m1+m2+… … +mr) 2。归纳基础：当 r=1 时，左式= m1 2，右式= m1 2，左式右式，命题成立。归纳步骤：设当 r=k 时，命题成立。即，k (m1 2+m2 2+… … +mk 2 ) ( m1+m2+… … +mk) 2。则当 r=k+1 时，左式= (k+1) (m1 2+m2 2+… … +mk+12 ) =k(m1 2+m2 2+… … +mk+12 )+ (m1 2+m2 2+… … +mk+12 ) =k(m1 2+m2 2+… … +mk 2 )+kmk+12+(m1 2+m2 2+… … +mk 2 ) + mk+12 =k (m1 2+m2 2+… … +mk 2 )+( m1 2+mk+12 )+ ( m2 2+mk+12 )+……+( mk 2+mk+12 )+ mk+12 右式=( m1+m2+… … +mk+1) 2 =( m1+m2+… … +mk) 2+2 mk+1 ( m1+m2+… … +mk)+ mk+12 =( m1+m2+… … +mk) 2+2 mk+1 m1+2 mk+1 m2+… … +2 mk+1 mk+ mk+12 由归纳假设 k (m1 2+m2 2+… … +mk 2 ) ( m1+m2+… … +mk) 2，以及基本不等式，左式右式，命题成立。所以 rsn 2。五、如果有一群人，其中有 k 个人彼此认识或者有 l 个人彼此不认识。我们用 r(k, l)表示这群人至少

是有几个人的人数,称为 Ramsey数。证明:r(3,3)=6。(10分) 证明:6个点V,,B,w,W6表示6个人,两人认识时,在对应的两点连一条绿边,否则连一条红边。根据鸽笼原理,与v相连的5条边中,必有3条同色。不访设vv2,vv和vν是3条绿边。如果三角形v2,v3,V4上有一条绿边,则此绿边与v构成一个绿色三角形,于是有3人彼此认识,否则 v2,,构成红色三角形,有3人彼此不认识。则r(3,3×6。5个点构成的完全图中,可以既无绿色三角形也无红色三角形,则r3.3)>5。则r(3,3)=6 六、证明:任何一个竞赛图是半哈密顿图。(10分) 证明: 归纳基础:若竞赛图的顶点数小于4,显然有一条哈密顿有向图。归纳步骤:假设n个顶点的任一竞赛图是半哈密顿有向图。设G是n+1个顶点的竞赛图,从G中删去顶点v及其关联边,得到有向图G’,由归纳假设,G′有哈密顿有向路(vl,v2…;,mn),G有3 种情况 (1)在G中有一条弧(,v,则有哈密顿有向路(v,Vb,v2…,vn (2)在G中没有弧(v,v1),则必有弧(,v。若存在vi,v是v之后第一个碰到并且有弧(,ri) 线的顶点,则显然得到一条哈密顿有向路(vb,V2…,Vi-l,v,vi,…"Vn 内不要答题 (3)在G中没有弧(v,v,而对所有v均有弧(,v,i=1,2,…n,则得一条哈密顿有向路(v 七、某一个市镇只有一家旅馆,这个旅馆与通常旅馆没有不同,只是房间数不是有限而是无穷多间,房间号码为1,2,3,4,……我们不妨管它叫希尔伯特旅馆。这个旅馆的房间可排成一列的无穷集合(1,2,3,4,…),称为可列集。有一天,所有房间都住满了。后来来了一位客人,坚持要住房间。旅馆老板于是引用“旅馆公理”说:“满了就是满了,非常对不起!”。正好这时候,聪明的旅馆老板的女儿来了,她看见客人和她爸爸都很着急,就说:“这好办,请每位顾客都搬一下,从这间房搬到下一间”。于是1号房间的客人搬到2号房间,2号房间的客人搬到3号房间… 依此类推。最后1号房间空出来,请这位迟到的客人住下了。第二天,希尔伯特旅馆又来了一个庞大的代表团要求住旅馆,他们声称有可数无穷多位代表一定要住,这又把旅馆经理难住了。老板的女儿再一次来解围,她说:“您让号房间客人搬到2号,2号房间客人搬到4号……,k号房间客人搬到2k号,这样,1 号,3号,5号,……房间就都空出来了,代表团的代表都能住下了第三天,这个代表团每位代表又出新花招,他们想每个人占可数无穷多间房来安排他们的亲戚朋友,这回不仅把老板难住了,连老板的女儿也被难住了 (1)现在您担任希尔伯特旅馆的客房经理,您准备采取什么方法解决当前的住宿问题 (2)后来老板的女儿进了大学数学系。有一天,康托尔教授来上课,他问老板的女儿:“要是区间[0,1上每一点都占一个房间,是不是还能安排?”也请您回答康托尔教授的这一问题,并论证。第3页

第 3 页（装订线内不要答题）是有几个人的人数，称为 Ramsey 数。证明：r(3, 3)=6。(10 分) 证明：6 个点 v1, v2, v3, v4, v5, v6 表示 6 个人，两人认识时，在对应的两点连一条绿边，否则连一条红边。根据鸽笼原理，与 v1 相连的 5 条边中，必有 3 条同色。不访设 v1 v2 ，v1 v3 和 v1 v4 是 3 条绿边。如果三角形 v2, v3, v4 上有一条绿边，则此绿边与 v1 构成一个绿色三角形，于是有 3 人彼此认识，否则 v2, v3, v4 构成红色三角形，有 3 人彼此不认识。则 r(3, 3)6。5 个点构成的完全图中，可以既无绿色三角形也无红色三角形，则 r(3, 3)>5。则 r(3, 3)=6。六、证明：任何一个竞赛图是半哈密顿图。（10 分）证明：归纳基础：若竞赛图的顶点数小于 4，显然有一条哈密顿有向图。归纳步骤：假设 n 个顶点的任一竞赛图是半哈密顿有向图。设 G 是 n+1 个顶点的竞赛图，从 G 中删去顶点 v 及其关联边，得到有向图 G’，由归纳假设，G’有哈密顿有向路(v1, v2, …, vn)，G 有 3 种情况：（1）在 G 中有一条弧(v, v1)，则有哈密顿有向路(v, v1, v2, …, vn)；；（2）在 G 中没有弧(v, v1)，则必有弧(v1, v)。若存在 vi，vi 是 v1 之后第一个碰到并且有弧(v, vi) 的顶点，则显然得到一条哈密顿有向路(v1, v2, …, vi--1, v, vi, …vn)；；（3）在 G 中没有弧(v, vi)，而对所有 vi，均有弧(vi, v)，i=1, 2, …, n，则得一条哈密顿有向路(v1, v2, …, vn, v)。七、某一个市镇只有一家旅馆，这个旅馆与通常旅馆没有不同，只是房间数不是有限而是无穷多间，房间号码为 1，2，3，4，……我们不妨管它叫希尔伯特旅馆。这个旅馆的房间可排成一列的无穷集合(1，2，3，4，…)，称为可列集。有一天，所有房间都住满了。后来来了一位客人，坚持要住房间。旅馆老板于是引用“旅馆公理”说：“满了就是满了，非常对不起！”。正好这时候，聪明的旅馆老板的女儿来了，她看见客人和她爸爸都很着急，就说：“这好办，请每位顾客都搬一下，从这间房搬到下一间”。于是 1 号房间的客人搬到 2 号房间，2 号房间的客人搬到 3 号房间…… 依此类推。最后 1 号房间空出来，请这位迟到的客人住下了。第二天，希尔伯特旅馆又来了一个庞大的代表团要求住旅馆，他们声称有可数无穷多位代表一定要住，这又把旅馆经理难住了。老板的女儿再一次来解围，她说：“您让 1 号房间客人搬到 2 号，2 号房间客人搬到 4 号……，k 号房间客人搬到 2k 号，这样，1 号，3 号，5 号，……房间就都空出来了，代表团的代表都能住下了。” 第三天，这个代表团每位代表又出新花招，他们想每个人占可数无穷多间房来安排他们的亲戚朋友，这回不仅把老板难住了，连老板的女儿也被难住了。 (1) 现在您担任希尔伯特旅馆的客房经理，您准备采取什么方法解决当前的住宿问题？ (2) 后来老板的女儿进了大学数学系。有一天，康托尔教授来上课，他问老板的女儿：“要是区间[0，1]上每一点都占一个房间，是不是还能安排？”也请您回答康托尔教授的这一问题，并论证