1、集合论与图论课堂练习3集合论与图论课堂练习3学号 姓名 一、判断下列命题是否正确，并说明理由。（括号内写“是”或“否” ）（40分，每题8分，是非判断4分，证明或反例4分）1 存在7个结点的自补图。（ 否 ）/*西安交通大学1999*/自补图对应的完全图的边数必须是偶数，而7个结点的完全图的边数为21。2 设G是顶点数的连通图。则G没有割点当且仅当G的剖分也没有割点。（真）如果G的剖分有割点，则G有割点，矛盾；所以G没有割点，则G的剖分也没有割点。如果G有割点，则该割点为G的剖分的割点，所以G的剖分有割点，矛盾；所以G的剖分也没有割点则G没有割点。3 若G是简单连通图，边数为e，结点数为n。若
2、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邻
3、接（因为G是连通图）。圈上与v关联的一边为e，则C-e的长度为m-1；而C-e+uv的长度为m；得C-e不是最长路。矛盾。二、综合题（60分）1证明：任何平面图是5-可着色的。证明：p125-1262如果有一群人，其中有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, v
4、3, 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边连通的。证明：非平凡有向图是强连通的充要条件为它
5、是一边连通的。证明：/*中国科学院计算所1999考研*/*必要性证明*/因为设G为强连通的，假设从S到V-S没有有向边，则S中的任一顶点u到V-S中的任一顶点v均没有有向道路，从而与G为强连通的相矛盾。所以从S到V-S至少有一条有向边，即G为一边连通的。/*充分性证明*/设G为一边连通的，对任意的u, vV, 则u到V(G-u)至少有一条边，设为(u, u1)，而u, u1到V-u, u1至少有一条有向边(u, u2)或(u1, u2)。无论哪种情况都有从u到u2的有向道路，因为G中结点数有限，所以通过如上递归地求解，一定有从u到v的有向道路。所以G为强连通的。5证明：任何一个竞赛图是半哈密顿
6、图。证明：归纳基础：若竞赛图的顶点数小于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)，而对所有v
7、i，均有弧(vi, v)，i=1, 2, , n，则得一条哈密顿有向路(v1, v2, , vn, v)。6 在2005年9月复旦大学百年校庆的庆典日，有4对毕业于复旦大学计算机系的新婚夫妇在袁成瑛计算机楼“仰止”石前的草坪上举行集体婚礼，婚礼由从加拿大远道赶来的复旦大学计算机系82级校友顾若平学长主持。在婚礼结束时，这4对夫妇互相握手，彼此祝愿对方新组成的家庭，因此，不会有自己和自己握手，也不会有夫妻间的握手，并且没有两个人握手超过一次。握手之后，新郎计算机系99级的陈宇阳校友问其他3对夫妇和他的新婚妻子：他或她握了多少次手？陈宇阳校友得到的答案都不相同。陈宇阳校友想到在复旦求学时，计算机系的老教师多次向他们提及顾若平学长，说他是“复旦第一聪明人”。于是一贯争强好胜的陈宇阳校友就挑战前辈，他将握手的情况告诉顾学长，然后问顾学长：“前辈，我握了几次手？”而顾若平学长则不假思索地就给出了正确答案。本题的问题是：顾若平学长给出的正确答案是什么？并请证明。37 如果在一个地图上任何两个地区都相邻，问在该地图上最多有几个地区？43 / 3
