《集合论与图论》课堂练习3 (2011年12月复旦大学计算机学院10级) 学号 姓名 1.证明:任何平面图是5可着色的。 证明: 2.证明:n个顶点的简单图G的边数超过(n1)n-2y2条边,则G是连通的。 证明:
《集合论与图论》课堂练习 3 （2011 年 12 月 复旦大学计算机学院 10 级） 学号 姓名 1．证明：任何平面图是 5-可着色的。 证明： 2．证明：n 个顶点的简单图 G 的边数超过(n-1)(n-2)/2 条边，则 G 是连通的。 证明：
3.证明:马在国际象棋3×4的棋盘上可以遍历。 证明: 4.如果一个带有e条边和n个顶点的连通简单平面图不包含长度为4或更短的 回路。证明:若n≥4,则≤(5/3)m(10/3)
3．证明：马在国际象棋 34 的棋盘上可以遍历。 证明： 4．如果一个带有 e 条边和 n 个顶点的连通简单平面图不包含长度为 4 或更短的 回路。证明：若 n4，则 e（5/3）n-（10/3）
5用下述算法为简单图着色: (1)以度数递减的顺序给出顶点的列表v,2,…,w,使得d(v)≥d(v2≥.d(vn) (2)把颜色1着色给顶点v和在列表中不与顶点η相邻的下一个顶点(若存 在一个这样的顶点),并且继续给列表中每一个不与着颜色1的顶点相邻 的顶点着颜色1;然后,把颜色2着色给列表中还没有着色的第一个顶点 并继续按上述步骤对列表中的顶点着颜色2;然后,以此类推,直到所有 的顶点都被着色。 举例说明这一算法不是最优的,也就是说,这个算法所产生的着色所需的颜色数 可能比某个图的色数大。 6简单图的定向就是指定它的各边的方向,使得所得的图是强连通图。证明 若一个图有割边,则它不是可定向的
5 用下述算法为简单图着色： （1） 以度数递减的顺序给出顶点的列表 v1, v2, …, vn，使得 d(v1)d(v2) …d(vn)； （2） 把颜色 1 着色给顶点 v1 和在列表中不与顶点 v1 相邻的下一个顶点（若存 在一个这样的顶点），并且继续给列表中每一个不与着颜色 1 的顶点相邻 的顶点着颜色 1；然后，把颜色 2 着色给列表中还没有着色的第一个顶点， 并继续按上述步骤对列表中的顶点着颜色 2；然后，以此类推，直到所有 的顶点都被着色。 举例说明这一算法不是最优的，也就是说，这个算法所产生的着色所需的颜色数 可能比某个图的色数大。 6 简单图的定向就是指定它的各边的方向，使得所得的图是强连通图。证明： 若一个图有割边，则它不是可定向的
7三对夫妇到达一条河流的岸边,每个妻子都是妒忌的,当她的丈夫与其他人 的妻子在一起而她不在场时,她就无法忍受。只用一条只能运载两个人的船,如 何能使三对夫妇到达河的另一边,且没有一个丈夫在他妻子不在场时与他的妻子 之外的女人相处?使用图论模型解答
7 三对夫妇到达一条河流的岸边，每个妻子都是妒忌的，当她的丈夫与其他人 的妻子在一起而她不在场时，她就无法忍受。只用一条只能运载两个人的船，如 何能使三对夫妇到达河的另一边，且没有一个丈夫在他妻子不在场时与他的妻子 之外的女人相处？使用图论模型解答