《集合论与图论》课堂练习2 -1

《《集合论与图论》课堂练习2 -1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《集合论与图论》课堂练习3学号姓名一、判断下列命题是否正确，并说明理由。（括号内写“是”或“否”）（40分，每题8分，是非判断4分，证明或反例4分）1存在7个结点的自补图。（否）/*西安交通大学1999*/自补图对应的完全图的边数必须是偶数，而7个结点的完全图的边数为21。2设G是顶点数的连通图。则G没有割点当且仅当G的剖分也没有割点。（真）如果G的剖分有割点，则G有割点，矛盾；所以G没有割点，则G的剖分也没有割点。如果G有割点，则该割点为G的剖分的割点，所以G的剖分有割点，矛盾；所以G的剖分也没有割点则G没有割点。3若

2、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的哈密顿回路。（是）/*复旦

3、大学1999*//*反证法证明*/令C的长度为m。若C不是哈密顿回路，则圈外必存在一点u，它与圈上一点v邻接（因为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个人，两人认

4、识时，在对应的两点连一条绿边，否则连一条红边。根据鸽笼原理，与v1相连的5条边中，必有3条同色。不访设v1v2，v1v3和v1v4是3条绿边。如果三角形v2,v3,v4上有一条绿边，则此绿边与v1构成一个绿色三角形，于是有3人彼此认识，否则v2,v3,v4构成红色三角形，有3人彼此不认识。则r(3,3)£6。5个点构成的完全图中，可以既无绿色三角形也无红色三角形，则r(3,3)>5。则r(3,3)=6。3．如果为一个无向图的每一条边确定一个方向，使得所得到的有向图是强连通的，称该无向图是可定向的。证明：欧拉图和哈密顿图都

5、是可定向。解：构造性证明，沿欧拉/哈密顿回路。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为一边连通的，对任

6、意的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’有哈密顿有

7、向路(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对毕业于复旦大学计算机系的

8、新婚夫妇在袁成瑛计算机楼“仰止”石前的草坪上举行集体婚礼，婚礼由从加拿大远道赶来的复旦大学计算机系82级校友顾若平学长主持。在婚礼结束时，这4对夫妇互相握手，彼此祝愿对方新组成的家庭，因此，不会有自己和自己握手，也不会有夫妻间的握手，并且没有两个人握手超过一次。握手之后，新郎计算机系99级的陈宇阳校友问其他3对夫妇和