9.1 平面图与欧拉公式 9.1 平面图与欧拉公式 ( 补充 ) 9.2 顶点着色 9.3 平面图的着色 9.4 边的着色 9.5 图着色的应用

Size: px

Start display at page:

Download "9.1 平面图与欧拉公式 9.1 平面图与欧拉公式 ( 补充 ) 9.2 顶点着色 9.3 平面图的着色 9.4 边的着色 9.5 图着色的应用"

勤树滑
5 years ago
Views:

1 第九章平面图与图的着色

2 9.1 平面图与欧拉公式 9.1 平面图与欧拉公式 ( 补充 ) 9.2 顶点着色 9.3 平面图的着色 9.4 边的着色 9.5 图着色的应用

3 平面图在现实生活中, 常常要画一些图形, 希望边与边之间尽量减少相交的情况, 例如印刷线路板上的布线, 交通道的设计等同构

4 9.1 平面图与欧拉公式一平面图定义 9.1( 平面图 ) 若一个图能画在平面上使它的边互不相交 ( 除在顶点处 ), 则称该图为平面图, 或称该图能嵌入平面的

5 图 9.1(a),(b) 图 9.1(a) 平面图 G, (b) 所示的 Ğ 是 G 的平面嵌入

6 图 9.2: 并不是所有的图都是平面图 (K 5 和 K 3,3 )

7 9.1 平面图与欧拉公式二欧拉公式 1 定义 9.2( 面 / 外部面 / 内部面 ) 平面图 G 嵌入平面后将 Ğ 分成若干个连通闭区域, 每一个连通闭区域称为 G 的一个面恰有一个无界的面, 称为外部面其余的面称为内部面

8 9.1 平面图与欧拉公式 2 欧拉公式 (1) 定理 9.1 若连通平面图 G 有 n 个顶点,e 条边和 f 个面, 则 n-e+f=2 称为欧拉公式证明方法 : 归纳法

9 证明 : (1) 归纳基础 : 一条边, 欧拉公式成立 ; (2) 归纳步骤 : 假设 m-1 条边, 欧拉公式成立 ; 考察 m 条边的连通平面图 : 1) 若有度数为 1 的顶点, 则删去该顶点及其关联边, 便得到连通平面图 G,G 满足欧拉公式, 再将删去的点和边加回 G 得到 G 也满足欧拉公式 ; 2) 若没有度数为 1 的顶点, 则删去有界面边界上的任一边, 便得到连通平面图 G, G 满足欧拉公式, 再将删去的边加回 G 得到 G 也满足欧拉公式

10 9.1 平面图与欧拉公式 (2) 推论 9.1 若 G 是 n 3 的平面简单图, 则 e 3n-6 证明 : 只证明连通的平面简单图的情况,G 是 n 3 的平面简单图, 每个面由 3 条或更多条边围成, 因此边的总数大于等于 3f, 因为每条边至多被计算两次, 所以 G 中至少有 3f/2 条边, 即 e 3f/2 根据欧拉公式, 有 n-e+2e/3 2 所以 3n-6 e

11 (3) 推论 9.2 若平面图的每个面由四条或更多条边围成, 则 e 2n-4 证明 : 类似推论 9.1 的证明 ( 由学生在课堂上当场进行推导 )

12 (4) 推论 9.3 K 5 和 K 3,3 是非平面图证明 : 反证法 : 若 K 5 是平面图, 由推论 9.1, 当 n=5, e=10 时,3n-6 e 不可能所以 K 5 是非平面图若 K 3,3 是平面图, 由推论 9.2, 当 n=6, e=9 时,2n-4 e 不可能所以 K 3,3 是非平面图

13 9.1 平面图与欧拉公式 (5) 定理 9.2 在平面简单图 G 中至少存在一个顶点 v 0, d(v 0 ) 5 证明方法 : 反证法, 假设所有顶点度数大于 5, 由推论 9.1, 导致矛盾

14 9.1 平面图与欧拉公式三平面图的特征 1 剖分在 G 的边上插入有限个点便得到 G 的一个剖分例 :

15 2 定理 9.3( 库拉托斯基定理 ) 图 G 是平面图它的任何子图都不是 K 5 和 K 3,3 的剖分

16 9.1 平面图与欧拉公式四对偶图 1 定义 9.3( 几何对偶 ) 设 Ğ 是平面图 G 的平面嵌入, 则 G 的几何对偶 G* 构造如下 : (1) 在 Ğ 的每一个面 f 内恰放唯一的一个顶点 f*; (2) 对 Ğ 的两个面 f i, f j 的公共边 x k, 作边 x k *={f i *, f j *} 与相交 ; 得到图记为 G*, 即 G 的几何对偶 ( 简称 G 的对偶 ) 图 9.4

17 如下图中,G 的边和结点分别用黑线和表示而它的对偶图的边和结点分别用蓝线和表示请指出错误之处

18 若 G 是连通平面图, 则 G* 也是连通平面图 /* 由定义 */

19 9.1 平面图与欧拉公式 2 定理 9.4( G 和 G* 的顶点数, 面数和边数的关系 ) 设 G 是有 n 个顶点,e 条边,f 个面的连通平面图 ; 又设 G 的几何对偶 G* 有 n* 个顶点,e* 条边,f* 个面, 则 n*=f, e*=e, f*=n 证明方法 : 前两个关系式直接由 G* 的定义给出, 第 3 个关系式由欧拉公式推出

20 3 定理 9.5 G 是连通平面图 G** 同构于 G

21 6.1 平面图与欧拉公式 ( 补充 ) 一球面与平面 1. 嵌入曲面设 S 是一个给定的曲面, 比如平面, 球面等, 如果图 G 能画在曲面 S 上使得它的边仅在端点处相交, 则称 G 可嵌入曲面 (embeddable in the surface) S

22 2. 定理 6A. 图 G 可嵌入球面 S G 可嵌入平面 P /* 证明基于球极平面射影 */ /* 图嵌入平面与球面是一回事 */

23 二平面图 1 边界和度数 1) 定义 6A: 包围每个面的所有边组成的回路组称为该面的边界 (boundary), 边界的长度称为该面的度 (degree of a face) 面 R 的度记为 deg(r) 2) 定理 6B: 平面图 G 中所有面的度数之和等于边数 e 的 2 倍 : f deg( R i ) 2e i 其中 f 为 G 的面数 1

24 证明 :/* 正向推导 */ e G, e 为面 R i 和 R j (i j) 的公共边界上的边时, 在计算 R i 和 R j 的度数时各提供次数 1, 而当 e 只在某一个面 R 的边界上出现时, 它必出现两次, 所以在计算 R 的度数时 e 提出的次数为 2, 于是每条边在 deg(r i ) 中, 各提供度数 2, 所以命题成立

25 2 极大平面图极小非平面图 1) 定义 6B( 极大平面图极小非平面图 ) 设 G 为简单平面图, 若在 G 的任意不相邻 u, v 之间加边 (u, v), 所得图为非平面图, 则称 G 为极大平面图若在非平面图 G 中任意删除一条边, 所得图为平面图, 则称 G 为极小非平面图 K 5 -e 均为极大平面图 K 5, K 3,3 都是极小非平面图

26 2) 定理 6C G 为 n(n 3) 个顶点的简单的连通平面图,G 为极大平面图当且仅当 G 的每个面的度数均为 3 /* 极大平面图 G 的每个面都是三角形 */

27 3) 定理 6D 在 n(n 4) 个顶点的极大平面图 G 中, (G) 3 /* (G) 为 G 的最小度 */

28 定理 6E. G 为 n(n 3) 个顶点 e 条边的简单平面图, 则 G 为极大平面图当且仅当 e=3n-6

29 证明 : : 因为 G 是连通的, 由欧拉公式得 f=2+e-n 又因为 G 是极大平面图, 所以 2e=3f 所以 e=3n-6 : 如果 e=3n-6, 但 G 不是极大平面图, 则在 G 中可以继续加边, 产生的还是平面简单图 G,e >3n-6 因为由推论 6.1, 对 n 3 的平面简单图 G, 则 e 3n-6, 导致矛盾

30 三欧拉公式应用欧拉公式及其推广形式得到平面图的另外一些性质

31 定理 6F 设 G 是连通平面图, 且 G 的各面的度数至少为 l(l 3), 则 G 的边数 e 与顶点数 n 有如下关系 : e l l 2 ( n 2)

32 证明 : 因为平面图 G 中所有面的次数之和等于边数 e 的 2 倍, 所以 f 2e deg( R ) l * f i 1 i 由欧拉公式 f=2+e-n, 代入 2e l(2+e-n), 所以 e l l 2 ( n 2)

33 推论 1 设 G 是具有 ( 2) 个连通分支的平面图, 且 G 的各面的次数至少为 l (l 3), 则 G 的边数 e 与顶点数 n 有如下关系 : e l ( n 1) l 2

34 定理 6G G 为 n(n 3) 个顶点 e 条边的简单平面图, 则 e=3n-6

35 证明 : 设 G 有 ( 1) 个连通分支若 G 是森林, 则 e=n- 3n-6(n 3) 若 G 不是森林, 则 G 中存在圈 ; 由于 G 是简单图, 所以圈的长度大于等于 3, 因而各面的次数至少为 l(l 3), l /(l-2) 在 l=3 时达到最大值, 因此 l e ( n 1 ) 3 ( n 1 ) l 2 3( n 2) 3n 6

36 四平面图的判断 1. 定义 6C( 插入 2 度顶点 / 消去 2 度顶点 ) 设 e=(u, v) 为图 G 中一条边, 在 G 中删除 e, 增加新的顶点 w, 使 u 与 v 均与 w 相邻, 即 G =(G-e) { (u, w), (w, v) }, 称为在 G 中插入 2 度顶点 w 设 w 为 G 中的一个 2 度顶点,w 与 u, v 相邻, 删除 w, 增加新边 (u, v), 即 G =(G-w) { (u, v) }, 称为在 G 中消去 2 度顶点 w

37 2. 定义 6D( 同胚 ) 若两个图 G 1 与 G 2 是同构的, 或通过反复插入或消去 2 度顶点后是同构的, 则称 G 1 与 G 2 是同胚的

38 3. 库拉托斯基定理的两种形式 1) 图 G 是平面图当且仅当 G 不含与 K 5 同胚子图, 也不含与 K 3,3 同胚子图 2) 图 G 是平面图当且仅当 G 中没有可以收缩到 K 5 的子图, 也没有可以收缩到 K 3,3 的子图

39 五平面图的应用正多面体 1. 每个凸多面体对应一个平面图 : 设 P 是凸多面体以 P 的顶点为顶点, P 的棱为边而得到的平面图 G(P) 称为对应于 P 的平面图则 G(P) 是连通的且 (G(P)) 3,P 的面就是 G(P) 的面, 而且 G(P) 的每条边正好在两个面的边界上

40 2. 欧拉凸多面体公式以 V, E, F 分别表示凸多面体 P 的顶点数棱数和面数, 则 V-E+F=2

41 3. 设 V n 和 F n 分别表示凸多面体 P 的 n 度点和 n 度面的数目, 当 n 3 时, 2E= nf n = nv n

42 4. 定理 6H. 每个凸多面体中都至少有一个 n 度面, 3 n 5 /* 证明方法 : 反证法 */

43 证明 : 设 F 3 =F 4 =F 5 =0 因为所有面的度数之和为 2E,2E= nf n 6F n =6 F n =6F, 其中 n 6, 则 2E 6F, F E/3 因 2E= nv n 3 V n =3V, 其中 n 3, 则 V 2E/3 由凸多面体公式 V-E+F=2, 得 E=V+F-2 2E/3+ E/3-2=E-2, 导致矛盾

44 5. 正多面体 (regular polyhedron, Plato 体 ) [1] 定义 ( 正多面体 ). 每个面并且每个多面角都相等的凸多面体称为正多面体. 对应的平面图称为 Plato 图. [2] Euclid( 约公元前 330 年 - 前 275 年 ) 几何原本 : 仅有 5 个正多面体 : 四面体立方体十二面体八面体二十面体

47 [3]. 定理 6I. 仅有 5 个正多面体

48 证明 : 设 P 是正多面体 G(P) 对应的平面图由 V-E+F=2, 得 -8=4E-4V-4F=2E+2E-4V- 4F= nf n + nv n -4 V n -4 F n = (n-4)f n + (n-4)v n,n 3 因为 P 是正多面体, 所以存在两个整数 h 和 k 使 F=F h 且 V=V k, 因此有 -8=(h-4)F h +(k-4)v k, 并且由 2E= nf n = nv n, 有 hf h =2E= kv k 由定理 6H,3 h 5, 分 3 种情况

49 情形 1. 当 h=3 时, 因为 -8=(h-4)F h +(k-4)v k, 且 hf h =2E= kv k, 所以 12=(6-k)V k 因此有 3 h 5 由-8=(h-4)F h +(k-4)v k 和 12=(6-k)V k, 得 : 当 k=3 时,V 3 =4,F 3 =4, 因此 P 是四面体 ; 当 k=4 时,V 4 =6,F 3 =8, 因此 P 是八面体 ; 当 k=5 时,V 5 =12,F 3 =20, 因此 P 是十二面体 ;

50 情形 2. 当 h=4 时, 因为 -8=(h-4)F h +(k- 4)V k, 所以 8=(4-k)V k, 则 k=3,v 3 =8, F 4 =6, 因此 P 是立方体情形 3. 当 h=5 时, 因为 -8=(h-4)F h +(k- 4)V k, 且 hf h =2E= kv k, 所以 20=(10-3k)V k 则 k=3,v 3 =20,F 5 =12, 因此 P 是立方体

51 图的着色

52 图的着色问题起源四色猜想 : 至多用 4 种颜色给平面或球面上的地图着色, 使得相邻的国家着不同的颜色

53 9.2 顶点着色一顶点着色定义 9.4 ( 顶点着色 ) 设 G 是一个没有自环的图, 对 G 的每个顶点着色, 使得没有两个相邻的顶点着上相同的颜色, 这种着色称为图的正常着色图 G 的顶点可用 k 种颜色正常着色, 称 G 为 k- 可着色的使 G 是 k- 可着色的数 k 的最小值称为 G 的色数, 记为 (G) 如果 (G)=k, 则称 G 是 k 色的图 9.6

54 9.2 顶点着色二性质 1. 定理 9.6 (1)G 是零图 (G)=1; (2) 对于完全图 K n, (K n )=n, 而 (ќ n )=1; (3) 对于 n 个顶点构成的回路 G n, 当 n 是偶数时, (G n )=2; 当 n 是奇数时, (G n )=3; (4)G 是二分图 (G)=2

55 证明方法 : 由定义

56 9.2 顶点着色 2. 定理 9.7 如果图 G 的顶点最大度数为 Δ(G), 则 (G) 1+Δ(G) /* 证明方法 : 对 G 的顶点数采用数学归纳法, 证明 G 是 1+Δ(G)- 可着色的 */ /* 对于 n 3 的 n 色图的特征至今没有得出, 然而可以给出色数上界 */

57 证明 : 1) 当 n=2 时,G 只有一条边, (G)=1,G 是 2- 可着色的所以 (G) 1+ (G) 2) 假设对于 n-1 个顶点的图, 结论成立现在设 G 有 n 个顶点, 顶点的最大度数是 (G), 如果删去任一点 v 及其相关联的边, 得到 n-1 个顶点的图 G, 它的最大顶点度数至多是 (G ), 且 (G ) (G) 根据归纳假设, 该图是 1+ (G)- 可着色的, 再将 v 及其相关联的边加回该图, 得到图 G, 顶点 v 的度数至多是 (G), v 的相邻顶点最多着上 (G) 种颜色, 然后 v 着上第 1+ (G) 种颜色因此,G 是 1+ (G)- 可着色的

58 3. Brooks 定理 1941 年, Brooks 证明 : 使 (G)=1+Δ(G) 的图只有两类 : 或者是奇回路, 或者是完全图

59 (1) 定理 9.8 (Brooks 定理 ) 如果连通图 G 的顶点的最大度数为 (G),G 不是奇回路, 又不是完全图, 则 (G) (G)

60 (2) 例 : 证明对于 Petersen 图 G, (G)=3

61 证明 : 由 Brooks 定理, 对于 Petersen 图 G, (G) (G)=3 又因为图中有奇回路, 奇回路图是 3 色图, 所以 (G) 3 所以 (G)=3

62 三着色与等价关系对图 G 进行 (G)- 着色, 设 R={(u, v) u, v V(G) 且 u, v 涂一样的颜色 }, 则 R 是 V(G) 上的等价关系

63 四色多项式 1. 定义 ( 色多项式 ) 设 G 是 n 个结点的无向图, 对 G 进行的两个 k- 可着色被认为是不同的, 是指至少有一个顶点在两个 k- 可着色中被涂不同颜色, 以 f(g, k) 表示 G 的不同 k- 可着色方式的总数, 称 f(g, k) 为 G 的色多项式

64 若 k< (G),f(G, k)=0; (G) 是使 f(g, k)>0 的最小整数 ;

65 2 定理 f(k n, k)=k(k-1) (k-n+1) f(n n, k)=k n 其中 K n,n n 分别 n 个顶点的完全图和零图

66 推论 f(k n, k)= f(k n-1, k)(k-n+1), n 2.

67 9.3 平面图的着色一地图的四色问题 1 历史与发展 1852 年, 英国青年 Guthrie 在画地图时发现 : 如果相邻两国着上不同的颜色, 那么画任何一张地图只需要四种颜色就够了 ( 地图的四色问题 ); 1976 年高速电子计算机证明地图的四色问题

68 2 定义 6.5( 地图 ) 一个没有桥的连通平面图称为地图 /* 桥 : 图 G 中的边 e 满足 (G-e)> (G), 称 e 为 G 的割边 ( 或桥 ) */ 地图可以有自环和多重边地图中的每一边是两个面的公共边两个面相邻是指两个面至少有一条公共边

69 3 定义 6.6( 地图的正常着色 ) 设 G 是一个地图, 对 G 的每个面着色, 使得没有两个相邻的面着上相同的颜色, 这种着色称为地图的正常面着色地图 G 可用 k 种颜色正常面着色, 称 G 是 k- 面可着色的使 G 的 k- 面可着色的数 k 的最小值称为 G 的面色数, 记为 x * (G) 若 x * (G)=k, 则称 G 是 k 面色的

70 地图的四色问题 : 任何地图是 4- 面可着色的

71 4 定理 9.9 设 G 是没有自环的平面图,G* 是 G 的对偶, 则 G 是 k- 可着色当且仅当 G* 是 k- 面可着色没有自环的平面图的对偶是没有桥的连通平面图 /* 证明方法 : 根据定义, 直接推导 */

72 证明 : : 设 G 是没有自环的平面图,G 的对偶 G* 是一个地图如果 G 是 k- 可着色的, 则由于 G* 的每个面恰含 G 中的一个顶点, 把 G* 的每个面着上它所包含的顶点的颜色因为 G 是 k- 可着色的,G 中的任何两个相邻的顶点有不同的颜色, 所以 G* 中任何两个相邻的面着上不同的颜色, 因此 G* 是 k- 面可着色的

73 : G* 是 k- 面可着色的, 由于 G 的每个顶点包含在 G* 的一个面中, 并且 G 的不同顶点包含在 G* 的不同面上, 把 G 中的每个顶点着上它所在面的颜色因为 G* 中没有两个相邻面着上相同的颜色, 所以 G 中没有两个相邻顶点着上相同的颜色, 因此 G 是 k- 可着色的

74 地图的四色问题 : 任何平面图是 4- 可着色的任何地图是 4- 面可着色的

75 6.3 平面图的着色二五色定理 (Heawood 1890) 任何平面图 G 是 5- 可着色的 /* 数学归纳法, 分治 */

76 证明 : 不妨设 G 是平面简单图. 对 G 的顶点数采用数学归纳法. 当 n 5 时结论成立. 假设对 n-1 个顶点的所有平面简单图 G 是 5- 可着色的. 考虑 n 个顶点的平面简单图 G, 由定理 6.2, 在 G 中存在顶点 v 0, 使 d(v 0 ) 5. 由归纳假设, G-v 0 是 5- 可着色的, 在给定 G -v 0 的一种着色之后, 将 v 0 及其关联边加回到原图中, 得到 G, 分两种情况 :

77 (1) 如果 d(v 0 )<5, 则 v 0 的相邻点已着上颜色小于等于 4 种, 所以 v 0 可以着另一颜色, 使 G 是 5- 可着色的. (2) 如果 d(v 0 )=5, 则将 v 0 的相邻点依次记为 v 1, v 2,, v 5, 并且对应的 v i 点着上第 i 色设 H 13 为 G-v 0 的一个子图, 它是由色 1 和色 3 的顶点集导出的子图如果 v 1 和 v 3 属于 H 13 的不同分支, 将 v 1 所在分支中着色 1 的顶点和着色 3 的顶点进行颜色对换, 这时 v 1 着色 3, 并不影响 G-v 0 的正常着色然后在 v 0 着色 1, 因此 G 是 5- 可着色的如果 v 1 和 v 3 属于 H 13 的同一分支中, 则在 G 中存在一条从 v 1 到 v 3 的路, 它的所有顶点着色 1 或 3, 这条路与 (v 1,v 0,v 3 ) 一起构成一条回路它或者将 v 2 围在里面, 或者把 v 4 和 v 5 一同围在它里面因为 G 是平面图, 在任何一种情况下, 都不存在连接 v 2 和 v 4 并且顶点着色 2 或 4 的一条路现在设 H 24 为 G-v 0 的另一个子图, 它是由着色 2 和 4 的顶点集导出的子图, 则 v 2 和 v 4 属于 H 24 的不同的分支中, 所以在 v 2 所在分支中将着色 2 的顶点和着色 4 的顶点进行颜色对换,v 2 着色 4, 这样导出了 G-v 0 的另一种正常着色然后在 v 0 着色 2, 同样得到 G 是 5- 可着色的

78 6.3 平面图的着色三二色定理地图 G 是 2- 面可着色的它是一个欧拉图

79 证明 : /* 地图 G 是 2- 面可着色的它是一个欧拉图 */ 设地图 G 是 2- 面可着色的, 对于 G 中任一个顶点 v, 围绕顶点 v 的面必为偶数个, 于是可推出 v 是偶顶点, 由定理 5.8, 可知 G 是欧拉图

80 /* 地图 G 是 2- 面可着色的它是一个欧拉图 */ /* 归纳证明设 G 是欧拉图, 则 G 可分解成若干个边不相重的回路的并对图的回路数采用数 p 采用数学归纳法 */

81 归纳基础 : 当 p=1 时, G 是 2- 面可着色的归纳步骤 : 假设回路为 p-1 的地图 G 是 2- 面可着色的对于由 p 条回路构成的地图 G, 由于 G 的每个顶点都是偶顶点, 在 G 中删去一条回路, 得到图 G,G 的每个顶点的度数也是偶数根据归纳假设,G 是 2- 面可着色的再把删去的回路加回到 G 中得到 G, 并且使这条回路外的所有面的颜色保持不变, 而回路所围的各面已着两种颜色, 将这两种颜色对换, 得到 G 是 2- 面可着色的

82 6.4 边的着色一定义定义 6.7( 边的着色 ) 设图 G 是没有自环的, 若对 G 的边着色, 使得没有两条相邻的边着上相同的颜色, 称此种着色为正常边着色 G 的边可用 k 种颜色正常边着色称 G 是 k- 边可着色使 G 是 k- 边可着色的数 k 的最小值称为 G 的边色数, 记为 x (G) 若 x (G)=k, 则称 G 是 k 边色的

83 二性质因为任何一个正常边着色中, 每一个顶点关联的边着色不同, 所以 x (G) (G)

84 1 定理 6.12(1964 年,Vizing) 设 G 是一个简单图, 它的顶点最大度数是 (G), 则 x (G)= (G) 或者 x (G)= (G)+1

85 x (G) 的上界和下界 : (G) x (G) (G)+1 n 个点构成的回路, (G)=2, 当 n 为偶数时, x (G)=2; 当 n 为奇数时,x (G)=3

86 2 定理 6.13 如果 G 是二分图, 则 x (G)= (G) /* 证明方法类似于定理 6.10, 对边数进行数学归纳 */

87 证明 : 归纳基础 : 边数为 1 的二分图 G 中 (G)=1, 显然 x (G)= (G)=1 归纳步骤 : 假设对任何 e-1 条边的二分图, 命题成立对于 e 条边的二分图 G, 从 G 中删去任一边 {u, v}, 得 G 根据归纳假设 G 的顶点的最大度数是 (G ), (G ) (G), 那么 G 是 (G )- 边可着色, 显然也是 (G)- 边可着色, 并且在 u 点和 v 点的度数 < (G), 在 u 点至少缺少一种颜色, 在 v 点也缺少一种颜色

88 将边 {u, v} 加回得图 G, 这时 G 中边 {u, v} 尚未着色如果 u 点和 v 点缺少的颜色相同, 边 {u, v} 着上这种颜色 ; 如果 u 点和 v 点缺少的颜色不同, 设 u 点缺少色 1,v 点缺少色 2, 则可以作一个连通子图 H, 它由 v 点出发的色 1 和色 2 交替边构成的路因为 G 是二分图, 并且子图 H 不包含 u, 所以可在 H 上对换色 1 和色 2, 这样并不影响 u 点已经着上的颜色于是边 {u, v} 着上色 1 因此图 G 是 (G)- 边可着色的, 并且 x (G)= (G)

89 定理 6.14 设 K n 是完全图, 当 n 为奇数 (n 1) 时, x (K n )=n, 当 n 为偶数时,x (K n )=n-1

90 6.5 图着色的应用例 1( 课程表问题 ). 某学校有 m 位教师 x 1, x 2,, x m 和 n 个班级 y 1, y 2,, y n, 要求教师 x i 每周给班级 y j 上 p ij 节课, 问如何安排一张周课程表, 使所排课时数目尽可能地少? /* 对任何一个课时, 一个教师最多只能给一个班级上课, 并且每个班级最多只能由一位教师上课 */

91 解题思想 : 利用边的着色理论作二分图 G(V 1, V 2 ),V 1 ={x 1, x 2,, x m }, V 2 ={y 1, y 2,, y n },x i 与 y j 有边相连当且仅当教师 x i 给班级 y j 上了一个课时的课, x i 与 y j 间有 p ij 条边根据定理 6.13, 如果 G 的顶点最大度数是 (G), 则 x (G)= (G) 因此, 如果每位教师至多上 (G) 个课时, 并且每个班级至多有 (G) 个课时, 则一定可以安排一张 (G) 个课时的课程表在二分图中, 同一颜色的边对应于同一课时中教师安排班级上课的情况

92 例 2. 色数 1. 储藏问题 (Storage Problem). 某公司生产 n 种化学制品 C 1, C 2,, C n, 其中某些制品是互不相容的若它们互相接触, 就会引起爆炸作为一种预防措施, 该公司希望把仓库分成若干隔间, 以便把不相容的化学制品储藏在不同的隔间里问 : 这个仓库至少应该分成几个隔间?

93 构造无向图 G(V, E), V={x 1,, x n }, {x i, x j } E 化学制品 C i 和 C j 互不相容仓库的最小隔间数等于 G 的色数 x(g)

94 2. 电视频道分配问题某地区有 n 家电视发射台 T 1, T 2,, T n 主管部门对每家电视发射台分配一个频道为了排除干扰, 使用同一频道的发射台之间相距必须大于指定的正数 d 问 : 该地区至少需要多少频道?

95 构造无向图 G(V, E), V={x 1,, x n }, {x i, x j } E T i 和 T j 之间距离 d 需要的最小频道数等于 G 的色数 x(g)

96 3. 考试安排问题某学校有门选修课程需要进行期末考试同一个学生不能在同一天里参加两门课程的考试问 : 该校的期末考试至少要几天?

97 构造无向图 G(V, E), V={x 1,, x n }, {x i, x j } E L i 和 L j 被同一位学生选修考试需要的最少天数等于 G 的色数 x(g)

98 4 目前还没有一个有效算法来确定色数

99 习题解析 1 是非题 (1) 设 G 1 与 G 2 是两个平面图, 若 G 1 G 2, 则它们的对偶图 G 1 * G 2 * 假存在反例

100 (2) 任何平面图 G 的对偶图 G* 的对偶图 G** 与 G 同构假任何平面图的对偶图都是连通图, 如果 G 是非连通的平面图, 显然命题不成立

101 (3) 任何平面图 G 的对偶图 G* 的面数 r* 都等于 G 的顶点数 n 假如果 G 是非连通的平面图,r*=nk+1, 其中 k 为 G 的连通分支数

102 习题解析 2 证明题 (1) 欧拉公式的推广设 G 是具有 k(k 2) 个连通分支的平面图, 则 n - e + f = k + 1 其中 n, e, f 分别是 G 的顶点数, 边数和面数 /* 证明方法 : 分而治之 */

103 证明 : 设 G 的 k 个连通分支分别为 G 1, G 2,, G k, n i, e i, f i 分别是 G i 的顶点数, 边数和面数, i=1, 2,, k 由欧拉公式, n i -e i + f i =2, i=1, 2,, k 求和得 k k k 而 i i i i 1 i 1 i 1 所以 n - e + f = k + 1 n e f 2 k k k k n n, e e, f f k 1 i i i i 1 i 1 i 1

104 (2) 设简单平面图 G 中顶点数 n=7, 边数 e=15, 证明 G 是连通的证明 : 反证法设 G 是非连通的, 连通分支为 G 1, G 2,, G k,n i, e i 分别是 G i 的顶点数, 边数, i=1, 2,, k 若 n i =1, 则 k=2 此时 G 是一个平凡图并上一个 K 6 才能使边数为 15, 而 K 6 不是平面图 ( K 5 也不是平面图 ) 若 n i =2, 则 G 至多含一条边, 另外 5 个结点构成 K 5 时边数最多, 但只有 10 条边所以 n i 3, e i 3n i -6, 求和得 e 3n-6k, 代入 n=7, e=15, 得 k, 则 k 1, 导致矛盾

105 (3) 证明 : 在 6 个结点 12 条边的连通平面简单图中, 每个面用 3 条边围成证明方法 : 利用欧拉公式进行推导证明 :n-e+f=2, n=6, e=12, f=2-6+12=8; 8 因为 deg ( f ) 2 e 2 4 i 1 而 deg(f i ) 3, 所以 deg(f i )=3, 即每个面用 3 条边围成 i

106 (4) 设 G 有 11 个结点或更多结点的图, 证明 G 或 G 的补图是非平面图证明方法 : 反证法

107 证明 : 假设 G 和 G 的补图都是平面图设 G 的结点数为 v, 边数为 e,g 的补图结点数为 v, 边数为 e ; 则 v=v,e+e =v(v- 1)/2 因为 e 3v-6,e 3v -6; 所以 e+e = v(v- 1)/2 6v-12; 则 v 2-13v+24 0, v<11, 与假设矛盾

108 (5) 证明 : 小于 30 条边的平面简单图有一个结点度数小于等于 4 证明方法 : 反证法和欧拉公式的推论

109 证明 : 假设每个结点的度数大于 4 因为 2e= deg(v ) 5v, 即 v 2e/5, 因为 e 3v- 6, 代入后得 e 6e/5-6, 即有 e 30, 与小于 30 条边矛盾

110

111

课件23.doc

课件23.doc 6.3 平面图与图的着色一平面图 : 定义 3: 设无向图 G=, 如果能把 G 的所有结点和边画在平面上, 使任何两边除公共结点外没有其它交叉点, 则称 G 为可嵌入平面图, 或称 G 是可平面图, 可平面图在平面上的一个嵌入称为平面图, 如果 G 不是可平面图, 则称 G 为非平面图例 : K 4 故 K 4 是可平面图例 : K 5 少一条边故 K 5 少一条边的图是可平面图