《集合论与图论》课堂练习3 (2007年6月18日8:009:40复旦大学计算机系06级) 判断下列命题是否正确,并说明理由。(括号内写“是”或“否”)(40分,每题8分, 是非判断4分,证明或反例4分) 1存在7个结点的自补图。 (否) 西安交通大学1999*/ 自补图对应的完全图的边数必须是偶数,而7个结点的完全图的边数为21。 2设G是顶点数n≥3的连通图。则G没有割点当且仅当G的剖分也没有割点 (真) 如果G的剖分有割点,则G有割点,矛盾;所以G没有割点,则G的剖分也没有割点 如果G有割点,则该割点为G的剖分的割点,所以G的剖分有割点,矛盾:所以G的剖分 也没有割点则G没有割点 3若G是简单连通图,边数为e,结点数为n。若e≥n,则G至少有3棵生成树。 (是 /*复旦大学1998*/ /*只需证明e=n时,命题成立* 若e=n-1,因为G是连通的,所以为一棵树;再添加一边时,因为G是简单图,所以图中必 存在一个长度大于等于3的回路,则在这个回路上任意删除一条边就得到一棵树。 4一个有向图D中仅有一个顶点的入度为0,其余顶点的入度均为1,则D是 有根树 (否) 一个自环和孤立点 /*北京大学1991*/ 5设C是简单连通图G的回路,若删去C中任一边后所得到的路C为G中的最长路,则 C是图G的哈密顿回 (是) /*复旦大学1990/ /*反证法证明* 令C的长度为m。若C不是哈密顿回路,则圈外必存在一点u,它与圈上一点ⅴ邻接(因 为G是连通图)。圈上与ⅴ关联的一边为e,则C-e的长度为m-1:而Ce+w的长度为m; 得C-e不是最长路。矛盾
《集合论与图论》课堂练习 3 （2007 年 6 月 18 日 8:00-9:40 复旦大学计算机系 06 级） 学号 姓名 一、判断下列命题是否正确，并说明理由。（括号内写“是”或“否” ）（40 分，每题 8 分， 是非判断 4 分，证明或反例 4 分） 1 存在 7 个结点的自补图。 （ 否 ） /*西安交通大学 1999*/ 自补图对应的完全图的边数必须是偶数，而 7 个结点的完全图的边数为 21。 2 设 G 是顶点数 n 3 的连通图。则 G 没有割点当且仅当 G 的剖分也没有割点。 （真） 如果 G 的剖分有割点，则 G 有割点，矛盾；所以 G 没有割点，则 G 的剖分也没有割点。 如果 G 有割点，则该割点为 G 的剖分的割点，所以 G 的剖分有割点，矛盾；所以 G 的剖分 也没有割点则 G 没有割点。 3 若 G 是简单连通图，边数为 e，结点数为 n。若 en，则 G 至少有 3 棵生成树。 （ 是 ） /*复旦大学 1998*/ /*只需证明 e=n 时，命题成立*/ 若 e=n-1，因为 G 是连通的，所以为一棵树；再添加一边时，因为 G 是简单图，所以图中必 存在一个长度大于等于 3 的回路，则在这个回路上任意删除一条边就得到一棵树。 4 一个有向图 D 中仅有一个顶点的入度为 0，其余顶点的入度均为 1，则 D 是 有根树。 （ 否 ） 一个自环和孤立点 /*北京大学 1991*/ 5 设 C 是简单连通图 G 的回路，若删去 C 中任一边后所得到的路 C’为 G 中的最长路，则 C 是图 G 的哈密顿回路。 （ 是 ） /*复旦大学 1999*/ /*反证法证明*/ 令 C 的长度为 m。若 C 不是哈密顿回路，则圈外必存在一点 u，它与圈上一点 v 邻接（因 为 G 是连通图）。圈上与 v 关联的一边为 e，则 C-e 的长度为 m-1；而 C-e+uv 的长度为 m； 得 C-e 不是最长路。矛盾
、综合题(60分) 1.证明:任何平面图是5-可着色的。 证明:pl25-126 2.如果有一群人,其中有k个人彼此认识或者有/个人彼此不认识。我们用rkD表示这群 人至少是有几个人的人数,称为 Ramsey数。证明:r(3.3)=6 证明:6个点V,,wBW表示6个人,两人认识时,在对应的两点连一条绿边,否则 连一条红边。根据鸽笼原理,与v相连的5条边中,必有3条同色。不访设wv2,vw3和 vv是3条绿边。如果三角形v,w上有一条绿边,则此绿边与v构成一个绿色三角形, 于是有3人彼此认识,否则v,V,构成红色三角形,有3人彼此不认识。则r(3,3≤6。5 个点构成的完全图中,可以既无绿色三角形也无红色三角形,则r(3,3)>5。则r(3,3)=6 3.如果为一个无向图的每一条边确定一个方向,使得所得到的有向图是强连通 的,称该无向图是可定向的。证明:欧拉图和哈密顿图都是可定向 解:构造性证明,沿欧拉哈密顿回路。 4.设G为非平凡有向图,V为G的结点集合,若对V的任一非空子集S,G中起始结点在S 中,终止结点在V-S中的有向边至少有k条,则称G是k边连通的。 证明:非平凡有向图是强连通的充要条件为它是一边连通的。 证明: /*中国科学院计算所1999考研* /*必要性证明* 因为设G为强连通的,假设从S到V-S没有有向边,则S中的任一顶点u到V-S中的任一顶 点v均没有有向道路,从而与G为强连通的相矛盾。所以从S到VS至少有一条有向边,即 G为一边连通的 /*充分性证明*/ 设G为一边连通的,对任意的u,vV,则{u到V(G-u)至少有一条边,设为(u,u1),而{u, ul}到V-{u,ul}至少有一条有向边(u,u2)或(u1,u2)。无论哪种情况都有从u到u2的有 向道路,因为G中结点数有限,所以通过如上递归地求解,一定有从u到v的有向道路。所 以G为强连通的。 5.证明:任何一个竞赛图是半哈密顿图。 证明: 归纳基础:若竞赛图的顶点数小于4,显然有一条哈密顿有向图。 归纳步骤:假设n个顶点的任一竞赛图是半哈密顿有向图。设G是n+1个顶点的竞赛图 从G中删去顶点v及其关联边,得到有向图G,由归纳假设,G有哈密顿有向路1v2 vn,G有3种情况: 1)在G中有一条弧vD),则有哈密顿有向路(v,v2…,wmn; 2)在G中没有弧vD,则必有弧v以。若存在v,是v之后第一个碰到并且有弧 v的顶点,则显然得到一条哈密顿有向路/v1,v2.…v-1.vv…m/; 3)在G中没有弧代v,而对所有v,均有弧v,l=l,2,…,n,则得一条哈密顿有向 路(v1,v2…,vnv
二、综合题（60 分） 1．证明：任何平面图是 5-可着色的。 证明：p125-126 2．如果有一群人，其中有 k 个人彼此认识或者有 l 个人彼此不认识。我们用 r(k, l)表示这群 人至少是有几个人的人数，称为 Ramsey 数。证明：r(3, 3)=6。 证明：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。 3．如果为一个无向图的每一条边确定一个方向，使得所得到的有向图是强连通 的，称该无向图是可定向的。证明：欧拉图和哈密顿图都是可定向。 解：构造性证明，沿欧拉/哈密顿回路。 4．设 G 为非平凡有向图，V 为 G 的结点集合，若对 V 的任一非空子集 S，G 中起始结点在 S 中，终止结点在 V-S 中的有向边至少有 k 条，则称 G 是 k 边连通的。 证明：非平凡有向图是强连通的充要条件为它是一边连通的。 证明： /*中国科学院计算所 1999 考研*/ /*必要性证明*/ 因为设 G 为强连通的，假设从 S 到 V-S 没有有向边，则 S 中的任一顶点 u 到 V-S 中的任一顶 点 v 均没有有向道路，从而与 G 为强连通的相矛盾。所以从 S 到 V-S 至少有一条有向边，即 G 为一边连通的。 /*充分性证明*/ 设 G 为一边连通的，对任意的 u, v V, 则{u}到 V(G-u)至少有一条边，设为(u, u1)，而{u, u1}到 V-{u, u1}至少有一条有向边(u, u2)或(u1, u2)。无论哪种情况都有从 u 到 u2 的有 向道路，因为 G 中结点数有限，所以通过如上递归地求解，一定有从 u 到 v 的有向道路。所 以 G 为强连通的。 5．证明：任何一个竞赛图是半哈密顿图。 证明： 归纳基础：若竞赛图的顶点数小于 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)
6在2005年9月复旦大学百年校庆的庆典日,有4对毕业于复旦大学计算机系 的新婚夫妇在袁成瑛计算杋楼“仰止”石前的草坪上举行集体婚礼,婚礼由从加 拿大远道赶来的复旦大学计算机系82级校友顾若平学长主持。在婚礼结束时 这4对夫妇互相握手,彼此祝愿对方新组成的家庭,因此,不会有自己和自己握 手,也不会有夫妻间的握手,并且没有两个人握手超过一次。握手之后,新郎计 算机系99级的陈宇阳校友问其他3对夫妇和他的新婚妻子:他或她握了多少次 手?陈宇阳校友得到的答案都不相同。陈宇阳校友想到在复旦求学时,计算机系 的老教师多次向他们提及顾若平学长,说他是“复旦第一聪明人”。于是一贯争 强好胜的陈宇阳校友就挑战前辈,他将握手的情况告诉顾学长,然后问顾学长: 前辈,我握了几次手?”而顾若平学长则不假思索地就给出了正确答案 本题的问题是:顾若平学长给出的正确答案是什么?并请证明。 7如果在一个地图上任何两个地区都相邻,问在该地图上最多有几个地区?
6 在 2005 年 9 月复旦大学百年校庆的庆典日，有 4 对毕业于复旦大学计算机系 的新婚夫妇在袁成瑛计算机楼“仰止”石前的草坪上举行集体婚礼，婚礼由从加 拿大远道赶来的复旦大学计算机系 82 级校友顾若平学长主持。在婚礼结束时， 这 4 对夫妇互相握手，彼此祝愿对方新组成的家庭，因此，不会有自己和自己握 手，也不会有夫妻间的握手，并且没有两个人握手超过一次。握手之后，新郎计 算机系 99 级的陈宇阳校友问其他 3 对夫妇和他的新婚妻子：他或她握了多少次 手？陈宇阳校友得到的答案都不相同。陈宇阳校友想到在复旦求学时，计算机系 的老教师多次向他们提及顾若平学长，说他是“复旦第一聪明人”。于是一贯争 强好胜的陈宇阳校友就挑战前辈，他将握手的情况告诉顾学长，然后问顾学长： “前辈，我握了几次手？”而顾若平学长则不假思索地就给出了正确答案。 本题的问题是：顾若平学长给出的正确答案是什么？并请证明。 3 7 如果在一个地图上任何两个地区都相邻，问在该地图上最多有几个地区？ 4
