集合论与图论课堂练习2.DOCVIP

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