《集合论与图论》课堂练习3 (2007年6月18日8:009:40复旦大学计算机系06级) 判断下列命题是否正确,并说明理由。(括号内写“是”或“否”)(40分,每题8分, 是非判断4分,证明或反例4分) 1存在7个结点的自补图。 () 2设G是顶点数n≥3的连通图。则G没有割点当且仅当G的剖分也没有割点
1 《集合论与图论》课堂练习 3 （2007 年 6 月 18 日 8:00-9:40 复旦大学计算机系 06 级） 学号 姓名 一、判断下列命题是否正确，并说明理由。（括号内写“是”或“否” ）（40 分，每题 8 分， 是非判断 4 分，证明或反例 4 分） 1 存在 7 个结点的自补图。 （ ） 2 设 G 是顶点数 n 3 的连通图。则 G 没有割点当且仅当 G 的剖分也没有割点。 （ ）
3若G是简单连通图,边数为e,结点数为n。若e≥n,则G至少有3棵生成树。 4一个有向图D中仅有一个顶点的入度为0,其余顶点的入度均为1,则D是有根树。 5设C是简单连通图G的回路,若删去C中任一边后所得到的路C为G中的最长路,则 C是图G的哈密顿回路
2 3 若 G 是简单连通图，边数为 e，结点数为 n。若 en，则 G 至少有 3 棵生成树。 （ ） 4 一个有向图 D 中仅有一个顶点的入度为 0，其余顶点的入度均为 1，则 D 是有根树。 （ ） 5 设 C 是简单连通图 G 的回路，若删去 C 中任一边后所得到的路 C’为 G 中的最长路，则 C 是图 G 的哈密顿回路。 （ ）
二、综合题(60分) 1.证明:任何平面图是5-可着色的 2.如果在一个地图上任何两个地区都相邻,问在该地图上最多有几个地区?
3 二、综合题（60 分） 1．证明：任何平面图是 5-可着色的。 2．如果在一个地图上任何两个地区都相邻，问在该地图上最多有几个地区？
3.如果为一个无向图的每一条边确定一个方向,使得所得到的有向图是强连通的,称该无 向图是可定向的。证明:欧拉图和哈密顿图都是可定向。 4.设G为非平凡有向图,V为G的结点集合,若对V的任一非空子集S,G中起始结点在S 中,终止结点在V-S中的有向边至少有k条,则称G是k边连通的 证明:非平凡有向图是强连通的充要条件为它是一边连通的
4 3．如果为一个无向图的每一条边确定一个方向，使得所得到的有向图是强连通的，称该无 向图是可定向的。证明：欧拉图和哈密顿图都是可定向。 4．设 G 为非平凡有向图，V 为 G 的结点集合，若对 V 的任一非空子集 S，G 中起始结点在 S 中，终止结点在 V-S 中的有向边至少有 k 条，则称 G 是 k 边连通的。 证明：非平凡有向图是强连通的充要条件为它是一边连通的
5.证明:任何一个竞赛图是半哈密顿图。 6在2005年9月复旦大学百年校庆的庆典日,有4对毕业于复旦大学计算机系的新婚夫 妇在袁成瑛计算机楼“仰止”石前的草坪上举行集体婚礼,婚礼由从加拿大远道赶来的复旦 大学计算机系82级校友顾若平学长主持 在婚礼结束时,这4对夫妇互相握手,彼此祝愿对方新组成的家庭,因此,不会有自己和自 己握手,也不会有夫妻间的握手,并且没有两个人握手超过一次。握手之后,新郎计算机系 99级的陈宇阳校友问其他3对夫妇和他的新婚妻子:他或她握了多少次手?陈宇阳校友得 到的答案都不相同。陈宇阳校友想到在复旦求学时,计算机系的老教师多次向他们提及顾若 平学长,说他当年是“复旦第一聪明人”。于是一贯争强好胜的陈宇阳校友就去挑战前辈, 他将握手的情况告诉顾学长,然后问顾学长:“前辈,我握了几次手?”而顾若平学长则不 假思索地就给出了正确答案。 本题的正确答案是什么?请证明
5 5．证明：任何一个竞赛图是半哈密顿图。 6 在 2005 年 9 月复旦大学百年校庆的庆典日，有 4 对毕业于复旦大学计算机系的新婚夫 妇在袁成瑛计算机楼“仰止”石前的草坪上举行集体婚礼，婚礼由从加拿大远道赶来的复旦 大学计算机系 82 级校友顾若平学长主持。 在婚礼结束时，这 4 对夫妇互相握手，彼此祝愿对方新组成的家庭，因此，不会有自己和自 己握手，也不会有夫妻间的握手，并且没有两个人握手超过一次。握手之后，新郎计算机系 99 级的陈宇阳校友问其他 3 对夫妇和他的新婚妻子：他或她握了多少次手？陈宇阳校友得 到的答案都不相同。陈宇阳校友想到在复旦求学时，计算机系的老教师多次向他们提及顾若 平学长，说他当年是“复旦第一聪明人”。于是一贯争强好胜的陈宇阳校友就去挑战前辈， 他将握手的情况告诉顾学长，然后问顾学长：“前辈，我握了几次手？”而顾若平学长则不 假思索地就给出了正确答案。 本题的正确答案是什么？请证明
