是有几个人的人数,称为 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]上每一点都占一个房间，是不是还能安排？”也请您回答康托尔教授的 这一问题，并论证