《集合论与图论》课堂练习3 (2013年12月18日13:20-15:00复旦大学计算机学院2012级) 判断下列命题是否正确,并说明理由。(括号内写“是”或“否”)(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 （2013 年 12 月 18 日 13:20-15:00 复旦大学计算机学院 2012 级） 学号 姓名 一、判断下列命题是否正确，并说明理由。（括号内写“是”或“否” ）（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 的哈密顿回路。 （ 是 ） /*复旦大学 1999*/ /*反证法证明*/ 令 C 的长度为 m。若 C 不是哈密顿回路，则圈外必存在一点 u，它与圈上一点 v 邻接（因 为 G 是连通图）。圈上与 v 关联的一边为 e，则 C-e 的长度为 m-1；而 C-e+uv 的长度为 m； 得 C-e 不是最长路。矛盾