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

《集合论与图论》课堂练习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 用下述算法为简单图着色：

（1） 以度数递减的顺序给出顶点的列表v1, v2, …, vn，使得d(v1)?d(v2)? …d(vn)； （2） 把颜色1着色给顶点v1和在列表中不与顶点v1相邻的下一个顶点（若存

在一个这样的顶点），并且继续给列表中每一个不与着颜色1 的顶点相邻的顶点着颜色1；然后，把颜色2 着色给列表中还没有着色的第一个顶点，并继续按上述步骤对列表中的顶点着颜色2；然后，以此类推，直到所有的顶点都被着色。

举例说明这一算法不是最优的，也就是说，这个算法所产生的着色所需的颜色数可能比某个图的色数大。

6 简单图的定向就是指定它的各边的方向，使得所得的图是强连通图。证明：若一个图有割边，则它不是可定向的。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《集合论与图论》课堂练习2在线全文阅读。