参考书籍 References [] J A Bondy and U S R Murty Graph Theory with Applications The Macmillan Press Ltd, 976 [2] J A 邦迪 U S R 默蒂著吴望名, 李念祖, 吴兰芳, 谢伟如, 梁文沛译图

Transcription

1 Chapter 6 图 Discrete Mathematics November 29, 20 黄正华, 数学与统计学院, 武汉大学 6 Contents 图的基本概念 2 2 路与回路 2 3 图的矩阵表示 2 4 欧拉图与汉密尔顿图 3 5 平面图 4 6 对偶图与着色 图论起源图论的最早论文是欧拉 (Leonhard Euler) 在 736 年发表的 文章讨论了哥尼斯堡七桥问题 当时哥尼斯堡 (Königsberg, 今俄罗斯加里宁格勒 ) 市区跨普雷格尔河 (Pregel) 两岸, 河中心有两个小岛 小岛与河的两岸有七座桥连接 七桥问题是 : 在所有桥都只能走一遍的前提下, 如何才能把这七座桥都走遍而且能回到原地? Leonhard Euler 63

2 参考书籍 References [] J A Bondy and U S R Murty Graph Theory with Applications The Macmillan Press Ltd, 976 [2] J A 邦迪 U S R 默蒂著吴望名, 李念祖, 吴兰芳, 谢伟如, 梁文沛译图论及其应用 科学出版社, 图的基本概念 图的定义 c b d a 七桥问题可以简洁地由左图表示 这类图示包含三个组成部分 : 结点 边 结点与边的对应关系 抽象其特点, 我们得到图 (Graph) 的定义 Definition 一个图 G 是一个三元序组 V (G), E(G), φ G, 其中 V (G) 是一个非空的结点集合 (vertex set), E(G) 是边集合 (edge set), φ G 是从边集合 E(G) 到结点无序偶 ( 有序偶 ) 集合上的函数 Example 2 设 G = V (G), E(G), φ G, 其中 V (G) = {a, b, c, d}, E(G) = {e, e 2, e 3, e 4, e 5, e 6 }, 而 φ G 定义为 φ G (e ) = (a, b), φ G (e 2 ) = (a, c), 65 φ G (e 3 ) = (b, d), φ G (e 4 ) = (b, c), φ G (e 5 ) = (d, c), 图 G 可用图形表示为如下的图 (a) 或 (b): φ G (e 6 ) = (a, d) 66 与图相关的概念和约定 每条边都是无向边的图叫无向图 ; 每条边都是有向边的图叫有向图 ; 既有无向边又有有向边的图叫混合图 67 2

3 b e e2 a e 6 e 3 d e b e 4 e 3 a e 5 e 6 d e2 e 4 c e 5 c (a) (b) v v v 2 v 5 v 2 v 4 v 2 v 4 v 3 v 4 v 3 v 3 v (a) 无向图 (b) 有向图 (c) 混合图 与图相关的概念和约定 这些图可分别表示为 : {v } { G = V, E =, v 2, v 3, v 4, v 5, (v, v 2 ), (v 2, v 3 ), (v 3, v 4 ), (v 2, v 4 ) } {v G = V, E =, v 2, v 3, v 4 } {, v, v 2, v 2, v 3, v 3, v, v, v 4, v 4, v 2 } {v G = V, E =, v 2, v 3, v 4 } {, (v, v 4 ), (v 2, v 4 ), v, v 3, v 3, v 4 } 68 与图相关的概念和约定 若两个结点与同一条边相关联, 则称两个结点是邻接点 关联于同一结点的两条边叫邻接边 69 v v v 2 v 5 v 2 v 4 v 2 v 4 v 3 v 4 v 3 v 3 v (a) G ( 无向图 ) (b) G ( 有向图 ) (c) G ( 混合图 ) 3

4 v v v 2 v 5 v 2 v 4 v 4 v 3 v 3 (d) G (e) G Figure : 例如, v 3 与 v 4, v 与 v 3 是邻接点 v v v 2 e 23 v 3 e 34 v 5 v 4 v 2 e 23 v 3 e 3 v 4 (a) G (b) G Figure 2: 例如, e 23 与 e 34, e 3 与 e 23 是邻接边 与图相关的概念和约定 设图 G = V, E, e k = (v i, v j ), 则 v i, v j 叫 e k 的端点 ; 并称 e k 与 v i, v j 相关联 关联于同一结点的一条边, 称为自回路或环 环的方向没有意义 : 它即可作为有向边, 也可作无向边 e v v 2 v 3 e 34 v 4 60 与图相关的概念和约定 不与任何结点相邻接的结点, 称为孤立点 仅由孤立结点组成的图叫零图 ; 由一个孤立结点构成的图叫平凡图 6 4

5 v v v 2 v 5 v 2 v 4 v 4 v 3 v 3 (a) 孤立点 : v 5 (b) 零图 a b v v 2 c (a) v 3 (b) 与图相关的概念和约定 关联于同一对结点的多条边 ( 有向边应同向 ), 叫平行边 包含平行边的图, 叫多重图 不含平行边和环的图, 叫简单图 62 Definition 3 在图 G = V, E 中, 与结点 v 相关联的边数, 叫该结点的度数, 记 作 deg(v) 称 (G) = max { deg(v) } v V (G) 为图 G 的最大度 ; 称 δ(g) = min { deg(v) } v V (G) 为图 G 的最小度 约定 : 每个环在其对应的结点上, 度数增加 2 例如左图 G 中, 各结点度数为 : a deg(a) = 2; deg(b) = 3; b e deg(c) = 2; deg(d) = 2; deg(e) = 5 63 c d 最大度和最小度为 : (G) = 5; δ(g) = 2 Theorem 4 每个图中, 结点度数的总和等于边数的 2 倍 deg(v) = 2 E v V 5

6 证 : 因为每条边关联两个结点, 且一条边给予关联的每个结点的度数为, v v 2 v 3 v 5 v 4 从而一条边产生且仅产生两度, 故结点度数的总和是边数的 2 倍 一个图的结点度数是偶数 64 Example 5 设一个图具有 0 个结点, 而且每个结点的度数都为 6 问此图有多少条边? 解 : 结点度数的总和为 deg(v) = 0 6 = 60 v V 所以 2 E = 60 得 E = 30, 即此图有 30 条边 65 Theorem 6 任何图中, 度数为奇数的结点必为偶数个 证 : 设 V 和 V 2 分别是图 G 中奇数度数和偶数度数结点集 则 deg(v) + deg(v) = deg(v) = 2 E v V v V 2 v V 上式中 deg(v) 为偶数, 2 E 也是偶数 v V 2 故 deg(v) 必为偶数, 即 V 是偶数 66 v V Definition 7 在有向图 G 中, 射入一个结点的边数, 称为该结点的入度, 记为 deg (v); 2 由一个结点射出的边数, 称为该结点的出度, 记为 deg + (v); 3 结点入度与出度之和, 称为该结点的度数, 即 deg(v) = deg (v) + deg + (v) 67 6

7 Example 8 a b 左图中, 结点 a 的出度为 4, 入度为, 结点 a 的度数为 5 其余各结点的度数皆为 3: 结点 b 的出度为 0, 入度为 3; 结点 c 的出度为, 入度为 2; c d 结点 d 的出度为 2, 入度为 68 Theorem 9 在有向图中, 所有结点出度之和等于所有结点入度之和 即 deg (v) = deg + (v) = E v V v V 证 : 因每条有向边恰好产生一个出度和一个入度, v v 2 v 4 v 3 从而出度和入度是成对出现的, 所以出度之和等于入度之和 69 完全图 Definition 0 简单图 G = V, E 中, 若每对结点之间均有边相连, 则称该图为完全图 有 n 个结点的无向完全图记作 K n (a) K 4 (b) K 5 (c) K 6 (d) K Theorem 无向完全图 K n 的边数为 n(n ) 2 7

8 a a b e b e c d c d (a) G (b) G Figure 3: G 与 G 互为补图 a b a b a b a b c d c d c d c (a) G (b) G (c) G 2 (d) G 3 证 : 组合数为 K n 中任意两个结点有且仅有一条边相连, 那么 n 个结点中任取两个结点的 即 K n 的边数为 ( ) n = n(n ) 2 2 E = n(n ) 2 注意 完全图, 首先是简单图 ( 不含有平行边和环 ) 62 Definition 2 由图 G 的所有结 点 和所有能使图 G 成为完全图的添 加 边 组成的图, 称为图 G 相 对 于 完 全 图 的 补图, 或简称为 G 的补图, 记作 G 622 Definition 3 给定图 G = V, E 和 G = V, E, 如果 E E, V V, 则称 G 为 G 的子图 如果 V = V, 即 G 包含 G 的所有结点, 则称 G 为 G 的生成子图 Example 4 如图, G, G 2 是 G 的子图, 也是 G 的生成子图 G 3 仅为 G 的子图 623 8

9 a b a b a b a b a c d c d c d c c d (a) G (b) G (c) G 2 (d) G 3 (e) G 4 Definition 5 设图 G = V, E 是 G = V, E 的子图 令 G 2 = V 2, E 2, 如 果 E 2 = E E, 且 V 2 中仅包含 E 2 中的边所关联的结点, 则称 G 2 为子图 G 相 对 于 图 G 的补图 Example 6 图中 G 相对于 G 的补图是 G 2 ; 而 G 3 相对于 G 的补图是 G 4 问 : G 的补图是? 624 图的同构 Definition 7 给定图 G = V, E 和 G = V, E, 如果存在双射 g : V V, 且 e = (v i, v j ) 是 G 的一条边当且仅当 e = ( g(v i ), g(v j ) ) 是 G 的一条边, 则称 G 与 G 同构 记作 G G 从定义可得两图同构的几个必要条件 : 结点数相同 ; 2 边数相同 ; 3 对应结点的度数相等 注 简言之, 同构的两个图的顶点之间, 具有保 持 相 邻 关 系 的一一对应 625 Example 8 判断下列图是否同构 : v u, v 3 u 3, v 4 u 2, v 2 u 4, 容易判断是同构的 ( 把图 G 2 中的 u 4 上移就看得更清楚了 ) 626 Example 9 图中 G, G 2, G 3, G 4 是彼此同构的 事实上, 它们都是完全图 K

10 u 4 v v 2 u u 2 u u 2 u u 2 u 4 v 3 v 4 u 3 u 4 u 3 u 3 (a) G (b) G 2 b a b d a b c a d c d a b c c d (a) G (b) G 2 (c) G 3 (d) G 4 Example 20 下面的三个图是同构的 : 628 Example 2 图中 G, G 2 是彼此不同构的 如果两图同构, 则对应结点的度数应相同 度数为 3 的两个结点 v 与 u 相对应 但是, 与分别 v 和 u 相邻接的各三个结点, 度数不一致 : v 的三个邻接点中, 度数为 2 的有一个, 度数为 的有两个 ; u 的三个邻接点中, 度数为 2 的有两个, 度数为 的有一个 629 Example 22 判断下列图是否同构 : 注意 G 中有两个度数为 3 的结点 v 3, v 2 ; G 2 中度数为 3 的结点是 u 5, u 3 容易看到图形是同构的 把 u 6 上移可以看得更清楚 630 (a) (b) (c) 0

11 v 4 v 3 v 2 v v 6 u 6 v 5 u 4 u 2 u u 3 u 5 (a) G (b) G 2 v v 2 u u 3 u 6 u u 3 v 5 v 6 u 2 u 6 u 2 v 3 v 4 u 5 u 4 u 5 u 4 (a) G (b) G 2 练习 P279 (4) 下面两个图是同构的 根据点与边的关联关系, 在两图编号相同的结点间建立双射, 便可知这两个图同 构 63 判断下列图形是否同构 632 判断下列图形是否同构 633 判断下列图形是否同构 634 判断下列图形是否同构 635 彼得森图 彼得森 (Julius Peter Christian Peterson, ) 丹麦人 (a) G (b) G 2

12 (a) G (b) G 2 v u v 2 v 5 u 2 u 5 v 3 v 4 u 3 u 4 Figure 4: 判断同构性 u u 2 v v 2 v 5 u 5 u 4 u 3 v 4 v 3 Figure 5: 判断同构性 v v 2 u 2 u v 5 u 5 v 4 v 3 u 3 u 4 Figure 6: 判断同构性 v v 2 u u 2 v 6 v 3 u 6 u 3 v 5 v 4 u 5 u 4 Figure 7: 判断同构性 2 路与回路 路与回路 本节主要内容 : 2

13 u 5 u 6 v 5 v 6 u 0 u u 2 u 3 u 4 v 0 v v 2 v 3 v 4 u 7 u 8 u 9 v 7 v 8 v 9 Figure 8: 判断同构性 v u v 8 v 2 u 8 u 2 v 7 v 3 u 7 u 3 v 6 v 5 v 4 u 6 u 5 u 4 Figure 9: 判断同构性 路 2 连通的概念 3 删除结点和边与图的连通性 4 有向图的可达性 5 有向图的连通性 636 路图论中的一个常见问题是从给定的结点出发, 沿着边移动, 到达另一指定结点 所经过的点边序列就形成了路的概念 Definition 23 给定图 G = V, E, 设 v 0, v, v 2,, v n V, e, e 2,, e n E, 其中 e i 是关联结点 v i, v i 的边, 点边交替序列 称为联结 v 0 到 v n 的路 v 0 e v e 2 v 2 e n v n v 0 和 v n 分别称为该路的起点和终点 如果 v 0 = v n, 称该路为回路 637 路 若路中各边 均不相同, 则称为迹 ; 2 若路中各结 点 均不相同, 则称为通路 ; 3 若闭合通路中各结 点 均不相同, 则称为圈 638 3

14 e 2 e 2 e 2 e 2 例如下图中 : v v v v e e e e e 3 e 3 e 3 e 3 v 2 v 3 v 2 v 3 v 2 v 3 v 2 v 3 e 4 e 4 e 4 e 4 e 5 e 6 e 7 e 5 e 6 e 7 e 5 e 6 e 7 e 5 e 6 e 7 v 4 e 8 v 5 v 4 e 8 v 5 v 4 e 8 v 5 v 4 e 8 v 5 v e v 2 e 5 v 4 e 8 v 5 e 7 v 3 是迹 ( 无重复的边 ), 也是通路 ( 无重复结点 ); v 2 e 3 v 3 e 4 v 2 e 6 v 5 e 8 v 4 e 5 v 2 是回路 ( 起点与终点重合 ), 但不是圈 ; v 2 e 3 v 3 e 7 v 5 e 6 v 2 是圈 ( 是回路, 但没有重复的结点 ) 639 Theorem 24 在具有 n 个结点的图中, 如果从结点 v j 到 v k 存在一条路, 则从 结点 v j 到 v k 必存在一条不多于 n 边的路 证 : 设从结点 v j 到 v k 存在一条路, 该路的结点序列为 v j v i v k 如果该路有 m 条边, 则该路的结点序列中有 m + 个结点 若 m > n, 则必存在结点 v s, 它在该路中不止出现一次, 可设该路的结点序列为 去掉 v s 到 v s 之间这段路 : v j v s v s v k v j v s v s }{{} v k v j v s v k 则 v j v s v k 仍然是 v j 到 v k 的路, 但此时路中边数已减少 如果所得的这条路中的边仍然大于 n, 重复上述步骤, 最终可得一条 v j 到 v k 且 路中边数不多于 n 条边的路 640 条边 例如下图有 5 个结点, v e v 2 e 3 v 3 e 4 v 2 e 6 v 5 e 8 v 4 是图中从 v 到 v 4 路, 它有 5 4

15 e 2 Figure 0: 非连通图 G v e e 3 v 2 e 4 v 3 e 5 e 6 e 7 v 4 e 8 v 5 去掉 v 2 到 v 2 之间的路 e 3 v 3 e 4 v 2, 所得的路 v e v 2 e 6 v 5 e 8 v 4 仍然是从 v 到 v 4 路, 其边数小于 5 64 连通 Definition 25 在无向图 G 中, 如果从结点 u 到 v 存在一条路, 则称结点 u 和 结点 v 是连通的 Definition 26 对无向图 G = V, E 而言, 结点集合 V 上的连通关系是等价关系 该连通关系将结点集合作出一个划分, 每个划分块连同它们所关联的边称为图 G 的一个连通分支 把图 G 的连通分支数记为 W (G) 642 Example 27 如图, 图 G 是具有三个连通分支的非连通图 G 的连通分支数为 W (G) = 3 Definition 28 若图 G 只有一个连通分支, 则称图 G 是连通图 643 连通性 & 结点和边的删除连通图中, 删除某些点或者边, 将使图变得不连通 结点和边的删除 : 在图中删除结点 v, 就是将结点 v 及 v 所关联的边都删除 在图中删除某边, 则只须删除该边, 而保留边所关联的结点 644 5

16 a c a c s s b d b d (a) (b) Definition 29 设无向图 G = V, E 中, 若有结点集 V V, 使图 G 删除了 V 的所有结点后所得的子图是不连通的, 而删除了 V 的任一真子集后所得的子图仍是连通的, 则称 V 是图 G 的点割集 如果某一个结点构成一个点割集, 则称该结点为割点 Example 30 如图, (a) 中删除割点 s, 成为有两个连通分支的非连通图 (b) 645 Definition 3 非 完 全 图 G 的点连通度 ( 简称连通度 ) 定义为 : k(g) = min { V i } Vi 是点割集 由定义可知, 连通度是为了产生一个不连通图所要删除结点的最少数目 那么, 非连通图的连通度为 0; 存在割点的连通图的连通度为 ; 完全图 K n 删除 m (m < n ) 个结点后仍是连通的, 删除 n 个结点后成为仅有一个孤立结点的平凡图, 故定义 k(k n ) = n Example 32 例如, 完全图 K 5 的删除 : 646 所以, k(k 5 ) = Definition 33 设无向图 G = V, E 为连通图, 若有边集 E E, 使图 G 删除了 E 中的所有边后所得的子图是不连通的, 而删除了 E 的任一真子集后所得的子图仍是连通的, 则称 E 是图 G 的边割集 如果某一条边构成一个边割集, 则称该边为割边 ( 或桥 ) Example 34 求下图所示的图 G 的割点和割边 6

17 (a) (b) (c) (d) (e) a d f g b c e h 割点 : b, c, e 割边 : e ab, e ce 648 Definition 35 非平凡图 G 的边连通度定义为 : λ(g) = min { E E 是边割集 } 由定义可知, 边连通度是为了产生一个不连通图所要删除边的最少数目 若 G 为平凡图 2, 定义 λ(g) = 0; G 为非连通图时 λ(g) 亦为 Example 36 求下图所示的图 G 的边连通度 c d a b 删除边 e cd 就会产生不连通图, 所以 λ(g) = 平凡图 : 由一个孤立结点构成的图 7

18 Theorem 37 设 G 为无向图, 则 k(g) λ(g) δ(g) 分析 : k(g) 是点连通度 ; λ(g) 是边连通度 ; δ(g) 是图 G 的最小度 证 : 若 G 不连通, 则 k(g) = λ(g) = 0, 而 δ(g) 0, 故上式成立 若 G 连通, 分两部分证明 证明 λ(g) δ(g) 如果 G 是平凡图 ( 只有一个孤立点构成的图 ), 则 λ(g) = 0 δ(g) 如果 G 不是平凡图, 则因每一个结点所有关联的边必含有一个边割集, 故 λ(g) δ(g) ( 因删去某结点关联的所有边, 该结点将成为孤立结点, 使原图变成不连通, 故被删去的边中必含有边割集 ) b d f a c e 续证 : 若 G 连通, 2 证 k(g) λ(g) 若 λ(g) =, 则 G 有一条割边, 从而 k(g) = 若 λ(g) 2, 因删去 λ(g) 条边可使 G 不连通, 但删去 λ(g) 条边 G 仍是连通的, 且此时出现有一条桥 e = (u, v) 对这 λ(g) 条边中的每条边, 都选一个与 u 或 v 不同的端点, 删去这些端点, 则至少删去 λ(g) 条边 如果这时产生的图是不连通的, 则 k(g) λ(g) < λ(g); 如果这时产生的图是连通的, 则 e 仍是桥, 此时再删去 u 或 v, 必产生一个非连通图, 故 k(g) λ(g) 由上述, 定理得证 这个定理的证明可以用下图的例子予以说明 这里 k(g) = 2, λ(g) = 3, δ(g) = 4 v u 65 8

19 Theorem 38 一个连通无向图 G 中的结点 v 是割点的充分必要条件是, 存在两个结点 u 和 w, 使连接结点 u 和 w 的 [ ] 每一条路都通过 v 证 : 若结点 v 是连通无向图 G = V, E 的割点, 删去 v 得子图 G, 则 G 至少包含两个连通分支 : G = V, E, G 2 = V 2, E 2 取 u V, w V 2, 因 G 连通, 故 G 必有一条连结 u 和 w 的路 c 但 u 和 w 在 G 不连通, 因此路 c 必须经过点 v, 这说明连接结点 u 和 w 的每条路都通过 v 2 反之, 若连接任意结点 v i 和 v j 的每条路都通过 v, 删去 v 得子图 G, 则在 G 中, 此二结点必不连通的, 故 v 是图 G 的割点 定理得证 652 有向图的连通性 无向图的连通概念不能直接推广到有向图 在有向图 G = V, E 中, 如果从结点 u 到 v 有一条路, 则称从 u 可达 v 如果 u 可达 v, 则 u, v 之间的最短路的长度, 称为结点 u, v 之间的距离, 记作 d u, v, 它满足性质 : d u, v 0 () d u, u = 0 (2) d u, v + d v, w d u, w (3) 653 有向图的连通性 如果从 u 到 v 不可达, 则记 d u, v = 距离的概念也适用于无向图 注意, 对有向图, d u, v 一般不等于 d v, u 将 D = max { d u, v } u, v V 称为图 G 的直径 可达性是有向图结点集上的二元关系, 它是自反的和传递的, 但一般不是对称的 所以可达性不是等价关系 654 有向图的连通性 Definition 39 在简单有向图 G 中, 任何一对结点间, 如果至少从一个结点到另一个结点可达, 则称该图是单侧连通的 如果图 G 中任何一对结点之间相互可达, 则称图 G 是强连通的 如果在图 G 中略去边的方向, 视为无向图是连通的, 则称图 G 是弱连通的 655 9

20 a b a b a b e c d c d c d (a) G (b) G 2 (c) G 3 Example 40 下列各有向图的连通性 : G 是强连通的 ( 任何一对结点之间相互可达 ); G 2 是单侧连通的 ( 任何一对结点间, 至少从一个结点到另一个结点可达 ); G 3 是弱连通的 ( 略去边的方向, 视为无向图是连通的 ) 656 Theorem 4 一个有向图是强连通的, 当且仅当 G 中有一个回路, 它至少包含每个结点一次 证 : 充分性 如果图 G 中有一个回路, 它至少包含每个结点一次, 则 G 中任何两个结点相互可达, 故图 G 是强连通的 必要性 如果有向图 G 是强连通的, 则 G 中任何两个结点相互可达, 故可从图中任一结点 v 出发, 经由图中所有的结点, 再返回 v, 从而形成一个回路 657 Definition 42 在简单有向图 G 中, 具有强连通性的极大子图, 称为强分图 ( 或者说, 一个子图 G 是强分图, 如果 G 具备强连通性, 且任何包含 G 的子图都不再具备强连通性 ) 具有单侧连通性的极大子图, 称为单侧分图 具有弱连通性的极大子图, 称为弱分图 658 Example 43 例如下图中, 包含结点 {v, v 2, v 3, v 4 } 的子图是强分图 ( 因为它具备强连通性, 而且再添加结点就不再具备强连通性 ) 仅包含一个孤立结点 v 5 的子图也是强分图 ( 再添加任意结点都不再具备强连通性 ) 包含结点 {v, v 2, v 4 } 的子图是强连通图, 但不是强分图 ( 因为添加结点 v 3 可以得到更大的强连通图 ) 20

21 v v 4 v 5 v 2 v Theorem 44 在有向图 G = V, E 中, 它的每一个结点位于且只位于一个强分图中 证 : 设任意 v V, 令 S 是图 G 中所有与 v 相互可达的结点集合, 当然 v S 则 S 是 G 的一个强分图 因此, G 的每个结点必位于一个强分图中 2 假设 v 位于两个强分图 S 和 S 2 中, 因 S 中每个结点与 v 相互可达, 而 v 与 S 2 中每个结点也相互可达, 故 S 和 S 2 中任何一对结点通过 v 都是相互可达的 这与 S 和 S 2 为强分图矛盾 故 G 的每个结点位于且只位于一个强分图中 660 练习若无向图 G 中恰有两个奇数度结点 u 和 v, 则 u, v 之间必有一条路 解 : 由结论 任何图中奇数度结点为偶数个, 所以 u, v 必位于 G 的同一连通分支中 则 u, v 之间必有一条路 66 3 图的矩阵表示 图的矩阵表示 本节主要内容 : 邻接矩阵 2 可达性矩阵和连通矩阵 3 关联矩阵 662 邻接矩阵 Definition 45 设 G = V, E 是一个简单图, 它有 n 个结点 V = { v, v 2, v n }, 则 n 阶方阵 A(G) = (a ij ) 称为 G 的邻接矩阵, 其中, v i 与 v j 相邻接 ; a ij = 0, 其它 663 2

22 v v 4 v 2 v 4 v 2 v 3 v v 3 (a) G (b) G Example 46 v 2 v 3 v v 4 v 5 左图的邻接矩阵为 : A (G) = 当给定的简单图是无向图时, 邻接矩阵是对称的 ; 当给定的图是有向图时, 邻接矩阵并不一定对称 Example 47 例如, 664 v v 4 v 2 v 3 上图的邻接矩阵列为 : v v 2 v 3 v 4 v v A(G) = v 3 0 v 有 v i 到 v j 的有向连线, 则 a ij = ; 否则, a ij = 图的邻接矩阵显然与 n 个结点的标定次序有关, 因而同一个图可得出不同的邻接矩阵 例如, 在下图 G 中将结点 v 与 v 2 的次序交换, 得到 G : 上两图的邻接矩阵分别为 : A(G) = , A(G ) = 注意到, 矩阵 A(G) 和 A(G ) 可以通过交换行和列而相互得出

23 置换等价 一般地, 如果两个矩阵可以通过交换行和列而相互得出, 则称它们置换等价 置换等价是 n 阶布尔矩阵集合上的一个等价关系 忽略这种元素次序的任意性, 可取图 G 的任一邻接矩阵视为该图的邻接矩 阵 667 v v 4 Example 48 例如, 上图的两个置换等价邻接矩阵 : v A(G) =, A(G) = v 3 v 2 v 3 v v 4 v v 3 0 v v 简单有向图 G 的邻接矩阵 A(G) = ( a ij 中, )n n 第 i 行元素之和等于 v i 的出度 2 第 j 列元素之和等于 v j 的入度 例如, 如图有向图中, Example 49 v 3 的出度 = = 3, v 3 的入度 = = v v 4 A(G) = v v 2 v 3 v 4 v v v 3 0 v v 2 v 邻接矩阵的应用问题 : 设图 G = V, E 的邻接矩阵为 A(G), V = {v, v 2,, v n } 如何计算连结 v i 与 v j 长度为 2 的路的数目? 分析 : 注意从 v i 到 v j 长度为 2 的路中间必经由某个结点 v k, 即 v i v k v j, 而且 a ik = a kj =, 那么 a ik a kj = 反之, 如果不存在路径 v i v k v j, 则 a ik = 0 或 a kj = 0, 从而 a ik a kj = 0 23

24 所以从 v i 到 v j 长度为 2 的路径的数目等于 n a i a j + a i2 a 2j + + a in a nj = a ik a kj }{{}}{{}}{{}}{{} v i v v j v i v 2 v j v i v n v k= j v i v k v j ( ) 2 按矩阵的乘法法则, 此和式恰好是 A(G) 中第 i 行第 j 列元素 a (2) ij a a 2 a n a a 2 a n ( ) a (2) ij = ( A (G) ) 2 a 2 a 22 a 2n a 2 a 22 a 2n = n n a n a n2 a nn a n a n2 a nn 670 v v 4 例如, 如左有向图, ( A(G) ) 2 中的 第 2 行第 列元素等于 2, 说明连 Example 50 v 2 v A(G) = ( ) A(G) = 结 v 2 与 v 长度为 2 的路的有两条 : v 2 v 4 v, v 2 v 3 v 分析 : a (2) 2 = a 2a + a 22 a 2 + a 23 a 3 + a 24 a 4 = = 2 注意从 v 2 到 v 长度为 2 的路中间 必经由一个结点 v k, 即 v 2 v k v 比如, k = 3 时, a 23 a 3 = 表示 从 v 2 到 v 3, 再 v 3 到 v 有路 67 还可以进一步计算从 v i 到 v j 长度为 3 的路的数目 注意从 v i 到 v j 长度为 3 的路径可视为从 v i 到中间结点 v k 长度为 的路 径, 再连接从 v k 到 v j 长度为 2 的路径 即 所以从 v i 到 v j 长度为 3 的路径的数目等于 n a (3) ij = a ik a (2) kj, 一般地有 : ( a (l) ij k= ( (3)) a ij n n = ( A(G) ) 3 ( ) ( ) 2 = A(G) A(G) ) A (G) ) a a n a a n l = n n } a n a nn {{ a n a nn } l a (l) ij 表示从 v i 到 v j 长度为 l 的路的数目

25 v v 4 ( A(G) ) 3 = A(G) ( A(G) ) 2 Example 5 v 2 v A(G) = ( ) A(G) = = 比如, ( A(G) ) 3 中的第 2 行第 列元素等于, 说明连结 v 2 与 v 长度为 3 的路的有一条 ( 即 v 2 v 3 v 4 v ) 673 前述的结论对无向图也是成立的 Theorem 52 设图 G = V, E 的邻接矩阵为 A(G), 则矩阵行第 j 列元素等于 G 中连结 v i 与 v j 长度为 l 的路的数目 证 : 对 l 用数学归纳法 当 l = 2 时, 由前述讨论可知成立 设命题对 l 成立, 由 ( ) l+ ( ) l, A(G) = A(G) A(G) ( A(G) ) l 中的第 i 故 a (l+) ij = n k= a ik a (l) kj, 上式右边的每一项表示由 v i 经过一条边到 v k, 再由 v k 经过一条长度为 l 的路 到 v j 的总长度为 l + 的路的数目 对所有 k 求和, 即得 a (l+) ij 是所有从 v i 到 v j 的长度为 l + 的路的数目, 故命题对 l + 成立 674 可达性矩阵 对一个有 n 个结点的有向图, 要判断一个结点 v i 到 v j 是否存在路, 可以计算 A, A 2, A 3,, A n 当有某个 A l 的 a (l) ij, 就表明结点 v i 到 v j 可达 ( 这里最多计算到 A n 就可以了 : 具有 n 个结点的有向图, 若结点 v i 到 v j 有 一条路, 则必然有一条长度不超过 n 的通路 ) 有向图 G 中从 v i 到 v j 是否有路可达, 可用矩阵表达 Definition 53 设 G = V, E 为简单有向图, V = {v, v 2, v n }, 定义一个 n n 矩阵 P = (p ij ), 其中, 从 v i 到 v j 至少存在一条路, p ij = 0, 从 v i 到 v j 不存在路 25

26 称 P 为图 G 的可达性矩阵 675 邻接矩阵 & 可达性矩阵 由图 G 的邻接矩阵 A, 可以得到可达性矩阵 P : 令 B n = A + A A n, 将 B n 中不为零的元素全部换成, 而等于零的元素不变, 即得可达性矩阵 P Example 54 设图 G 的邻接矩阵为 A =, 求可达性矩阵 解 : A =, A 3 2 =, A =, B 4 = A + A 2 + A 3 + A =, P = 我们只关心矩阵里的元是否非零, 所以可以进行矩阵的布尔运算 677 布尔矩阵的和 积设 A = (a ij ) n n, B = (b ij ) n n 是布尔矩阵, 令 C = A B = (c ij ) n n, 称为布尔矩阵求 和, 其中 c ij = a ij b ij 2 令 D = A B = (d ij ) n n, 称为布尔矩阵求 积, 其中 n ( ) d ij = aik b kj Example 55 k= = 可达性矩阵的计算求可达性矩阵可简化为 : 由图 G 的邻接矩阵 A 求可达性矩阵 P : P = A () A (2) A (n), 其中的元素 A (i) 表示 A i 对应的布尔矩阵 26

27 2 用 Warshall 算法计算 : 因为有向简单图的邻接矩阵 A 可视为 : 具有 n 个结点的集合 V 上 的邻接关系 的关系矩阵 ; R 而可达性矩阵可视为 : 邻接关系 R 的传递闭包所对应的矩阵 679 计算可达性矩阵举例 A= A2 = 2 0 A3 = A4 = 方法 先由邻接矩阵 A 求 B 4, B 4 = A + A 2 + A 3 + A 4, 然后写出可达性矩阵 P B 4 = , P = 计算可达性矩阵举例 方法 2 将 A, A 2, A 3, A 4 转换为布尔矩阵 A (), A (2), A (3), A (4), 则 P = A () A (2) A (3) A (4) P = = 68 计算可达性矩阵举例 方法 3 用 Warshall 算法计算, 逐列进行 : 在第 i 列中若有 a ji =, 则把第 i 行 叠加到第 j 行 27

28 M := := }{{}}{{} i= i=2 := := = P } {{ } } {{ } i=3 i=4 682 关联矩阵 Definition 56 设 G = V, E 为无向图, V = {v, v 2, v p }, E = {e, e 2, e q }, 定义矩阵 M(G) = ( m ij )p q, 其中, 若 v i 关联 e j, m ij = 0, 若 v i 不关联 e j 称 M(G) 为图 G 的完全关联矩阵 683 Example 57 例如, 写出下图的关联矩阵 e v e 2 v 2 e 5 e 6 e 3 v 5 v 4 e 4 v 3 M(G) = e e 2 e 3 e 4 e 5 e 6 v 0 0 v v v v 从完全关联矩阵可得出图的有关信息 : 因每边只关联两个结点, 故每列有且只有两个, 其余为 0 2 每行各元素之和即相应结点的度数 3 若某行各元素皆为 0, 则相应结点为孤立结点 4 平行边所对应的列完全相同 28

29 5 同一个图当结点或边的编序不同时, 其对应的关联矩阵仅有行序和列序的 差异 v e 5 e 6 e e 2 v 2 e 3 v 4 e 4 v 3 v 5 M(G) = e e 2 e 3 e 4 e 5 e 6 v 0 0 v v v v 完全关联矩阵 Definition 58 设 G = V, E 为简单有向图, V = {v, v 2, v p }, E = {e, e 2, e q }, 定义矩阵 M(G) = ( m ij )p q, 其中, 若在 G 中 v i 是 e j 的起点, m ij =, 若在 G 中 v i 是 e j 的终点, 0, 若 v i 与 e j 不关联 M(G) 称为有向图 G 的完全关联矩阵 686 Example 59 例如, 写出如下简单有向图的关联矩阵 v e7 e 5 e 4 v 5 e e 6 v 4 v 2 e 2 v 3 e 3 M(G) = e e 2 e 3 e 4 e 5 e 6 e 7 v v v v v 从有向图的完全关联矩阵可得出图的有关信息 : 每边关联一个始点, 一个终点 故每列只有一个元素为, 一个元素为, 其余为 0 2 每行的 之和即相应结点的出度, 之和即相应结点的入度 3 若某行各元素皆为 0, 则相应结点为孤立结点 4 平行边所对应的列完全相同 29

30 e v 2 v e 2 e 6 e7 v 3 e 5 e 3 e 4 v 4 v 5 M(G) = e e 2 e 3 e 4 e 5 e 6 e 7 v v v v v 结点的合并 在关联矩阵里, 记 v i 对应的行为 vi, 规定运算 : vi v j 其中 对有向图, 是普通的加法 ; 2 对无向图, 是对应分量的模 2 加法运算 运算的目的是把 v i 与 v j 合并, 而且要达到一个要求 : 合并若得到了自回路, 要删 去 合并图中结点 v 4 与 v 5, 反映在矩阵 M(G) 上 v 4 v Example 60 M(G) = e e 2 e 3 e 4 e 5 e 6 e 7 v v v v v M(G ) = e e 2 e 3 e 4 e 5 e 6 e 7 v v v v 4, 两个关于关联矩阵的秩的结论 : Theorem 6 设连通图 G 有 r 个结点, 则其完全关联矩阵的秩为 r 即 rank M(G) = r ( 证明略 ) 推论 设图 G 有 r 个结点, w 个最大连通子图, 则图 G 的完全关联矩阵的秩为 r w 69 30

31 小结 图的矩阵表示所用到的几种不同的矩阵 邻接矩阵 : 点与点之间的邻接关系 A l 的作用? 2 可达性矩阵 ( 和连通矩阵 ): 路的存在性 可达性矩阵的三种求法? 3 完全关联矩阵 : 结点与边的关系 运算 vi v j 的作用? 692 练习 求如下有向图的邻接矩阵 A, 指出从 v 到 v 4 且长度为 2 和 4 的路 并计算 A 2, A 4 来验证 v v 2 v 4 v 3 解 : 从 v 到 v 4 长度为 2 的路有 条 : v v 2 v 4 从 v 到 v 4 长度为 4 的路有 3 条 : v v 2 v 4 v 2 v 4, v v 2 v 3 v 2 v 4, v v 4 v 2 v 3 v A =, A =, A =, A = 欧拉图与汉密尔顿图 欧拉图与汉密尔顿图本节主要内容 : 欧拉图 2 有向图中的欧拉路 3 周游世界问题 4 汉密尔顿图 5 标识法 694 3

32 欧拉图 Definition 62 设图 G 无孤立结点 若存在一条路, 经过图中每边一次且仅一次, 称该路为欧拉路 若存在一条回路, 经过图中每边一次且仅一次, 则称该回路为欧拉回路 具有欧拉回路的图叫欧拉图 695 Example 63 例如, 下图具有欧拉路, 而没有欧拉回路 v v 2 v 3 v 4 v 5 从图中 v 2 出发, 经过图中每边一次且仅一次到 v 3, 可得欧拉路 : v 2 v v 3 v 5 v 4 v 2 v 3 但此图不可能有欧拉回路, 因而不是欧拉图 696 Theorem 64 无向图 G 有一条欧拉路, 当且仅当 G 连通, 且有零个或两个奇数度结点 证 : 必要性 设图 G 有欧拉路 v 0 e v e 2 v 2 e i v i e i+ e k v k, 其中结点可重复出现, 但边不重复, 且每条边都经历一次, 因此, 欧拉路遍历 G 中所有结点, 所以 G 是连通的 若 v i 不是端点, 则 deg(v i ) 必为偶数 ; ( 因 v i 在欧拉路中每出现一次必关联两条边 ) 而对端点 v 0 和 v k, 如果 v 0 = v k, 则 deg(v 0 ) 为偶数, 即 G 中无奇数度结点 ; 32

33 C A B D 如果 v 0 v k, 则 deg(v 0 ) 和 deg(v k ) 必为奇数, 故 G 中有两个奇数度结点 证 : 充分性 当 G 连通, 且有零个或两个奇数度结点 可按如下方法构造一条欧拉路 () 若 G 有两个奇数度结点 v 0 和 v k, 因 G 连通, 可构造一条迹 ( 无重复边的路 ) L : v 0 e v e 2 v k ; 若 G 无奇数度结点, 则可从任何结点 v i 出发构造一条闭迹 L : v i e v e 2 v i (2) 如果 L 遍历 G 的所有边, 则 L 就是一条欧拉路 (3) 如果 L 未遍历 G 的所有边, 则删除 L 后得子图 G, G 中每个结点的 度数为偶数 因 G 连通, 所以 L 与 G 至少有一个结点 v j 重合, 在 G 中从结 点 v j 出发可构造闭 迹 L 2 (4) 如果 L 和 L 2 组合在一起恰为 G, 则得一条欧拉路, 否则重复第 3 步, 如此下去, 必可得到一条经过图 G 所有边的欧拉路 697 推论无向图 G 具有一条欧拉回路, 当且仅当 G 连通, 且所有结点度数皆为偶数 由推论可知, 七桥问题无解 : deg(a) = 5, deg(b) = deg(c) = deg(d) = 3 故欧拉回路必不存在 698 一笔画问题 Example 65 一笔画问题 即欧拉路的存在性问题 例如下图中 deg(v 2 ) = deg(v 3 ) = 3, deg(v ) = deg(v 4 ) = deg(v 5 ) = 2 故必有从 v 2 到 v 3 的一笔画 ( 或 v 3 到 v 2 ) 699 欧拉路可推广到有向图 Definition 66 经过有向图中每边一次且仅一次的单向路 ( 回路 ), 称为单向欧拉路 ( 回路 ) 33

34 v v 2 v 3 v 4 v 5 Theorem 67 有向图 G 具有一条单向欧拉回路, 当且仅当 G 连通, 且每个结点的入度等于出度 有向图 G 具有一条单向欧拉路, 当且仅当 G 连通, 且除两个结点之外, 每个结点的入度等于出度 而这两个结点, 一个结点的入度比出度大, 另一个结点的入度比出度小 ( 证明与前述定理类似 ) 600 William Rowan Hamilton 3 哈密顿 (William Rowan Hamilton, ), 爱尔兰数学家 物理学家 823 年到爱尔兰的三一学院学习 827 年获爱尔兰皇家天文学家的称号 835 年获封为爵士 837 年当选爱尔兰皇家科学院院长 60 哈密顿在数学上的最主要贡献是发现了 四元 数 (quaternions), 建立了向量代数和向量分析 的基础 William Rowan Hamilton 4 On October 6, 843, while out walking in Dublin, Hamilton formed a new set of numbers called the quaternions in which there are four key ingredient numbers, namely, i, j, and k, satisfying the following multipicative rules: i 2 = j 2 = k 2 =, ij = k, jk = i, ki = j, ji = k, kj = i, ik = j Hamilton was so pleased with his discovery that he stopped on his walk to carve these equations with a knife into the sandstone of Brougham Bridge (see Irish stamp above) 602 周游世界问题 3 Available at wwwhkameorghk/bookmark Available at 34

35 NOVEMBRE JUILLET M M L J V S D AOUT L M M J V S D DECEMBRE L M M J V S D L M M J V S D SEPTEMBRE L M M J V S D OCTOBRE L M M J V S D 十二面体的 20 个顶点用不同的城市作标记 智力题的目标是在一个城市开始, 延十二面体的边旅行, 访问其他 9 个城市每个恰好一次, 回到第一个城市结束 ( 旅行经过的回路可以用钉子和细线来标记 ) 603 正十二面体 604 一个展开了的正十二面体 605 汉密尔顿图 Definition 68 给定图 G, 经过图中每个结点一次且仅一次的路, 称为汉密尔顿路 经过图中每个结点一次且仅一次的回路, 称为汉密尔顿回路 具有汉密尔顿回路的图, 叫汉密尔顿图 Example 69 例如, 判断下面各图是否为汉密尔顿图 606 图 (a) 中有汉密尔顿路, 但不存在汉密尔顿回路, 所以它不是汉密尔顿图 ; 图 (b) 中有汉密尔顿回路, 它是汉密尔顿图 ; 图 (c) 中既无汉密尔顿回路, 也不存在汉密尔顿路

36 JUILLET M M L J V S D DECEMBRE L M M J V S D AOUT L M M J V S D SEPTEMBRE L M M J V S D DECEMBRE L M M J V S D JUILLET L M M J V S D NOVEMBRE L M M J V S D OCTOBRE L M M J V S D AVRIL L M M J V S D AOUT L M M J V S D MARS L M M J V S D SEPTEMBRE L M M J V S D March December November October February January 202 April June May August July September (a) (b) (c) 36

37 Theorem 70 若无向图 G = V, E 是汉密尔顿图, 任意 S V, 则 W (G S) S, 其中 W (G S) 表示 G 中删除 S 后所得子图 G S 的连通分支数 证 : 设 C 是 G 中的一条汉密尔顿回路 如果 S 中的结点在 C 上两两相邻, 则 W (C S) = S 2 如果 S 中的结点在 C 上存在 r (2 r S ) 个互不相邻的部分, 则 W (C S) = r S 一般说来, S 中的结点在 C 上既有相邻的, 又有不相邻的, 所以总有 W (C S) S 注意到 C S 是 G S 的生成子图, 故 W (G S) W (C S) S 定理只是汉密尔顿图的必要条件 如果图 G 不满足这个条件, 则 G 肯定不是汉密尔顿图 定理的用途 : 判断一个图不是汉密尔顿图 608 a a f l o g p m h b f l o g p m h b e k n j i c e k n j i c 因为 Example 7 所以图 G 不是汉密尔顿图 d W ( G {a, b, c, d, e, f, g} ) = 9 {a, b, c, d, e, f, g} = 7 d 609 件, 也不能肯定 G 是汉密尔顿图 如彼得森图, 它满足定理的条件, 但它不是汉密尔顿图 即使图 G 满足定理的条 删除 个或 2 个结点仍是连通图 2 删除 3 个结点, 最多得 2 个连通分支的子图 3 删除 4 个结点, 最多得 3 个连通分支的子图 4 删除 5 个或 5 个结点, 则所得子图的结点数已不大于 5, 从而排除了出现 5 个以上连通分支的可能性 37

38 所以该图满足 W (G S) S, 但可以证明它是非汉密尔顿图 到目前为止, 判断一个图是否为汉密尔顿图还只能依据定义 只有部分满足 特定条件的图才能用判别法 ( 充分条件 ) 60 Theorem 72 设 G 是具有 n 个结点的简单图, 如果图中每对结点度数之和大于或等于 n, 则 G 中存在一条汉密尔顿路 证 : 先证 G 连通, 用反证法 假设 G 不连通, 则至少有两个连通分支 G 和 G 2 又设 G 有 n 个结点, G 2 有 n 2 个结点 任取 v G, v 2 G 2, 则 deg(v ) n, deg(v 2 ) n 2 ( 因图 G 是简单图 ) 从而有 deg(v ) + deg(v 2 ) n + n 2 2 < n 与题设矛盾 2 在 G 中构造一条汉密尔顿回路 设 G 中有 p 条边的路 v v 2 v p (p < n), 且路中各结点均不同 6 证明 ( 续 ): 设 G 中有 p 条边的路 v v 2 v p, 且路中各结点均不同 若 v 或 v p 有邻接于不在该路上的结点, 则可将该路扩展为包含该邻接结 点的有 p 条边的路 反之, 若 v 或 v p 与该路外的结点都不邻接, 则存在包含结点序列 v v 2 v p 的回路 事实上 若 v 邻接 v p, 则 v v 2 v p v 即是所求的回路 ; 2 若 v 与 v p 不邻接, 假设 v 与路内的 k 个结点 v s, v m,, v j,, v t 相邻接, 2 s, m,, j,, t p 如果 v p 与 v s, v m,, v j,, v t 中之一邻接, 比如说 v j, 则 v v 2 v j v p v p v j v 即是所求的回路 ( 如图 ); 62 38

39 v j v v 2 v 3 v j v p v v 2 v k v x v j v j v p 证明 ( 续 ): 如果 v p 与 v s, v m,, v j,, v t ( 共 k 个 ) 都不邻接, 则 v p 至多邻接于 p k 个结点 ( 路 v v 2 v p 内除 v p 外共 p 个结点 ) 从而 deg(v p ) p k 又 deg(v ) = k, 故 deg(v p ) + deg(v ) p < n 这与题设矛盾 以上已经证明, 存在包含所有结点 v, v 2, v p 的回路 63 证明 ( 续 ): 因 G 连通, 故 G 中必有不属于该回路的结点 v x, 它与 v, v 2,, v p 中的某 结点 v k 邻接, 这样就得出包含 p 条 边的路 : v x v k v j v p v j v v 2 v k 对得到的 p 条边的路重复前述方法, 可得 p + 条边的路 如此继续, 可得有 n 条边的路, 它是汉密顿路 64 Theorem 73 (Ore 定理 ) 设 G 是具有 n 个结点的无向简单图, n 3 如果 G 中任一对结点度数之和都大于等于 n, 则在 G 中存在一条汉密尔顿回路 ( 即 G 是汉密尔顿图 ) 证 : 由前述的定理知, 在 G 中存在一条汉密尔顿路, 设为 v v 2 v n 若 v 与 v n 邻接, 则得到一条汉密尔顿回路 定理得证 2 若 v 与 v n 不邻接, 假设 v 邻接于 v i, v i2,, v ik, (2 i j n ) 可以证明 v n 邻接于 v i, v i2,, v ik 中之一 如果 v n 不邻接于 v i, v i2,, v ik 中任一结点, 则 v n 至多邻接于 n k 个结点 从而 deg(v n ) n k 又 deg(v ) = k, 故 deg(v n ) + deg(v ) n k + k = n 这与题设矛盾 所以必有汉密尔顿回路 v v 2 v j v n v n v j v 注意 : 本定理只不过是充分条件, 而非必要条件 不满足定理中条件的图, 也可能是汉密尔顿图 39

40 Example 74 例如, 左图是具有 6 个结点的无向简单图, 它 显然是汉密尔顿图, 但该图中任一对结点度数 之和等于 4, 并不大于等于图中结点总数 6 65 标识法判断图 G 中是否存在汉密尔顿路或汉密尔顿回路, 除按定义来判断之外, 没有一个充分必要条件可以作为判断方法 下面的标识法是一个可作参照的方法 ( 但这不是一个 充要条件 ) 标识法的步骤如下 : 先用字母 A 标识图中任一结点, 接着用 B 标识图中与 A 邻接的结点 然后再用字母 A 标识图中与 B 邻接的结点, 如此下去, 直到图中所有结点标识完毕 2 在标识过程中, 遇到相邻结点出现相同标记时, 可在此边上增加一个结点, 并标上相异标识 3 标识完毕后, 如果若 A, B 数目差一个以上, 则该图不存在汉密尔顿回路 66 标识法用标识法说明彼得森图不是汉密尔顿图 A B B B A A A A A A 先用字母 A 标识图中任一结点 ; 接着用 B 标识图中与 A 邻接的结点 ; 然后再用字母 A 标识图中与 B 邻接的结点 A, B 数目差一个以上, 所以彼得森图不存在汉密尔顿回路 67 Example 75 本学期某个班的学生共计选修了 A, B, C, D, E, F 六门课 其中一部分人同时选修 A, C, D, 一部分选修 B, C, F, 一部分选修 B, E, 还有一部分选修 A, B 期末考试要求每天考一门课, 六天内考完 为了减轻学生负担, 要求每个人都不会连续参加考试 试设计一个考试日程表 解 : 以每门课为一个结点, 共同选修的课程之间用边相连, 得到图 (a) 由题意, 相邻结点对应的课程不能连续考试, 而不相邻的结点所对应的课程允许连续考试 因此作图 (a) 的补图 (b) 40

41 F A F A E B E B D C D C (a) (b) a b b c d b c d b c d c d a e a e a e (a) G (b) G 2 (c) G 3 (d) G 4 a c b d b a c e d b a c e d b a c e d (a) G (b) G 2 (c) G 3 (d) G 4 问题归结为在图 (b) 中找一条哈密尔顿路 如依次按顺序 C, E, A, F, D, B 进行考试, 就是一个符合要求的考试安排 68 5 平面图 平面图 本节主要内容 : 平面图的概念 2 欧拉公式 3 库拉托夫斯基定理 69 平面图的概念 Definition 76 能画在一个平面上且任何两边除端点外互不相交的图, 称为平面图 这里说的是 能画在, 有些图形从表面看有几条边是相交的, 但是不能就此肯定它不是平面图 620 Example 77 判断下面各图是否为平面图 G, G 2, G 3 是平面图, G 4 不是平面图 62 4

42 r 4 a r r 3 b b r a r 2 e d r 3 c r 2 d c (a) (b) r 4 a r r 3 b b r a r 2 e d r 3 c r 2 d c (a) (b) 示 将平面图 G 的每个边不交叉的图画在一个平面上, 称为图 G 的一个平面表 Definition 78 平面图 G 的某个平面表示, 将 G 所在的平面划分成若干区域, 每个区域叫图 G 的一个面 ; 包围每个面的边, 称为该面的边界 ; 边界上边的条数, 叫该面的次数, 面 r 的次数记作 deg(r) Example 79 图 (a) 有 4 个面 ; 图 (b) 有 3 个面 图 (b) 中 : deg(r ) = 3, deg(r 2 ) = 5, deg(r 3 ) = Theorem 80 一个有限平面图, 面的次数之和等于其边数的两倍 证 : 因一条边或是两个面的公共边, 或在一个面中作为该面的边界被计算过两次, 所以各面次数之和等于边数的两倍 Example 8 图 (a) 有 6 条边 ; 4 个面, 每面次数皆为 3 图 (b) 中 deg(r ) = 3, deg(r 2 ) = 5, deg(r 3 ) = 4 图 (b) 有 6 条边 ; 有 3 个面, 各面次数之和为 Theorem 82 ( 欧拉公式 ) 设 G 是连通平面图, 有 v 个结点, e 条边, r 个面, 则 v e + r = 2 42

43 证 : 对边数用归纳法证明 若 G 为平凡图 ( 孤立结点 ), 则 v =, e = 0, r = 公式成立 若 G 仅有一条边, 则 v = 2, e =, r = 公式成立 ; 或 v =, e =, r = 2 公式仍然成立 设 G 有 k 条边时, 欧拉公式成立 当 G 有 k + 条边时, 设其结点数为 v, 面数为 r, 可分两种情况讨论 : 如 G 中有度数为 的结点, 删除该结点及其关联的一条边得图 G 显然, G 也是连通平面图, 设 G 的结点数, 边数和面数依次为 v, e = k, r, 按归纳假设应满足欧拉公式, 即 v e + r = 2, 亦即 (v ) (e ) + r = 2, 从而有 v e + r = 2 如 G 中没有度数为 的结点, 则在有限面的边界中删除一条边得图 G G 也是连通平面图且边数等于 k, 按归纳假设应满足欧拉公式, 即 v e + r = 2, 亦即 v (e ) + (r ) = 2, 从而有 v e + r = 2 综上所述, 当边数为 k + 时公式成立 定理得证 624 Theorem 83 设 G 是有 v 个结点, e 条边的连通简单平面图, 且 v 3, 则 e 3v 6 证 : 设 G 的面数为 r, 当 v = 3, e = 2 时, 公式成立 当 e 3 时, 因 G 为简单图, 每面的次数不小于 3( 否则意味着有平行边或环, 就不是简单图了 ) 又由各面次数之和为 2e, 因此 2e 3r, 再由欧拉公式 v e + r = 2, 有 r = 2 + e v, 带入上式得 : 2e 3(2 + e v), 即 e 3v

44 A A 2 A 3 B B 2 B 3 Figure : K 3,3 定理给出了结点数大于等于 3 的连通简单平面图应满足的必要条件, 可用来 判断某些图不是平面图 Example 84 例如, 应用定理可知 K 5 不是平面图 c b d a e 因 K 5 是连通简单图, 不满足定理给出的条件 e 3v 6 v = 5, 3v 6 = 9, 而 e = 0, 626 推论设 G 是 v 个结点, e 条边的连通平面图, 且 G 的各面的次数大于等于 4, 则 e 2v 4 证 : 由所设, G 的各面次数之和大于等于 4r, 这里 r 为 G 的面数 所以 2e 4r, 即 e 2r 再由欧拉公式 v e + r = 2, 有 r = 2 + e v, 带入上式得 : e 2(2 + e v), 得 e 2v 4 推论给出了各面次数大于等于 4 的连通平面图应满足的必要条件, 所以可用 来判断某些图不是平面图 627 Example 85 例如, 应用推论可知 K 3,3 不是平面图 如果 K 3,3 是连通平面图, 由每个面的次数都不小于 4 ( 因为在 K 3,3 中任取三个结点, 其中必有两个结点不相邻 ) 又 v = 6, 2v 4 = 8, 且 e = 9, 不满足推论给出的条件 e 2v

45 v 2 v 2 v 2 v 2 v 0 v 0 v v v v (a) 插入结点 (b) 删除结点 (a) K 3,3 (b) K 5 Kuratowski 定理欧拉公式可用来判断某些图不是平面图 但不能用来判断某图是平面图 Kuratowski 5 2> 库拉托夫斯基 (Kazimierz Kuratowski, ) 波兰人, 华沙大学教授 给出了一个判断平面图的充分必要条件 为此, 先介绍 在二度结点内同构 的定义 629 Kuratowski 定理 Definition 86 给定图 G, G 2, 如果它们同构, 或通过反复插入或删除度数为 2 的结点之后它们同构, 则称 G 与 G 2 在二度结点内同构 插入或删除 2 度结点示意图 : 630 Kuratowski 定理 Theorem 87 一个图是平面图, 当且仅当它不包含与 K 3,3 或 K 5 在二度结点内 同构的子图 (K 3,3 和 K 5 常称为库拉托夫斯基图 ) ( 证明略 ) 63 Kuratowski 定理 注意 K 3,3 的不同表示, 下面两个图都是 K 3,3 : 5 <

46 A B B 2 A A 2 A 3 A 3 A 2 B 3 B B 2 B 3 (a) K 3,3 (b) K 3,3 A A B G F J E B G F J E H I H I C D C D (a) Petersen 图 (b) 取 Petersen 图子图 A A A B G F J E B G J E B E C H I D C H F I D H F I (c) 子图的变形 (d) 删除二度结 点 C, D, G, J 得 K 3,3 Kuratowski 定理 注意 K 3,3 的不同表示, 下面两个图都是 K 3,3 : B 2 A A A 2 A 3 B B B 2 B 3 A 证明 Petersen 图不是平面图 634 练习 46

47 假定连通平面性简单图有 20 个结点, 每个结点的度数都是 3 这个平面图有多少 个区域? 解 : 由题知, v = 20 则所有结点的度数之和为 20 3 = 60 而 deg(v) = 2e, v V 所以 e = 30 由欧拉公式得 r = e v + 2 = = 练习 应用欧拉公式证明 Petersen 图不是平面图 a b c g h f i j d e 证 : Petersen 图中, v = 0, e = 5, 从图上可以看出, 每个面由 5 条边围成 根据定理 7-5, 如果 Petersen 图是平面图, 则 2e = 5r 所以 r = 2 5 e = 6 v e + r = = 2 这说明 Petersen 图不满足欧拉公式, 故它不是平面图 对偶图与着色 对偶图与着色 本节主要内容 : 着色问题 2 对偶图的概念 3 正常着色 4 Welch Powell 着色法 5 四色定理 (The Four-Color Theorem)

48 Four Color Conjecture 6 The concept of the Four Coloring Theorem was born in 852 when Francis Guthrie noticed that he only needed four different colors to color in a map of England Through his brother, Frederick, Francis communicated his discovery to De Morgan Francis wondered if De Morgan would be able to tell him if it was true or not De Morgan was unsure, so he asked the same question to Hamilton in Dublin Hamilton was unable to help, so De Morgan continued to ask other prominent mathematicians 638 Four Color Conjecture In the US, Charles Peirce attempted to prove the Four Color Conjecture in the 860 s and continued to for the remainder of his life In 879, Cayley wrote a paper to the Royal Geographical Society explaining the difficulties in attempting to prove the Conjecture On July 7, 879, a mathematician by the name of Kempe announced a proof for the Four Color Conjecture However, eleven years later Heawood, a lecturer at Durham England, pointed out that Kempe s proof was incorrect Along with proving Kempe wrong, Heawood was able to prove that every planar map is five colorable In 898, Heawood also proved that if the number of edges around a region is divisible by three then the region is four colorable 639 Four Color Conjecture In 880 a man by the name of Tait came up with his own proof for the Four Color Conjecture Once again the proof was proved false, this time by Petersen in 89 In the midst of these two failed attempts at finding a proof for the Four Color Conjecture, Kempe and Tait both made other major contributions to the world of mathematics Kempe discovered what would later become known as Kempe chains and Tait devised a equivalent form of the Four Color Theorem for three-edge-coloring The next major contribution was the concept of reducibility by Birkoff Using Birkoff s work, Franklin proved that any map with up to 25 regions can be four colorable in Four Color Conjecture In 926 Reynolds increased the number of regions to 27 Winn increased it to 35 in 940, Ore and Stemple to 39 in 970, and Mayer to 95 in 976 Heesch 6 Available at: 48

49 later developed the two main concepts that eventually led to the final proof They were reducibility and discharging Finally, in 976, Kenneth Appel and Wolfgang Haken at the University of Illinois with the aid of a computer program that was thousands of lines long and took over 200 hours to run, basing their methods on reducibility using Kempe chains The Four Color Theorem was the first major theorem to be proved using a computer 64 对偶图的概念 Definition 88 给定平面图 G = V, E, 设它有 n 个面 F, F 2,, F n 图 G = V, E 满足下列条件 : 若 对图 G 的任意一个面 F i, 其内部有且仅有一个结点 vi 属于 V ; 2 对图 G 的任意两个面 F i, F j 的公共边界 e k 有且仅有一条边 e k 属于 E, 使 e k = (v i, v j ), 且 e k 与 e k 相交 ; 3 当且仅当 e k 只是一个面 F i 的边界时, vi 有一个环 e k 与 e k 相交 则称图 G 是图 G 的对偶图 对偶图显然是相互的 G 是 G 的对偶图, 则 G 也是 G 的对偶图 特别是连通平面图的对偶图也是平面图 642 Definition 89 图 G 的对偶图 G 同构于 G, 则称图 G 是自对偶图 Example 90 自对偶图的例子 : 面 演化为 点 ; 面的公共边界 演化为 点的邻接边 643 正常着色 由对偶图的概念, 可以将 地图的着色 转化为对 平面图结点的着色 因而四色问题归结为 : 证明对任何一个平面图, 可用四种颜色对其结点实施 着色, 使邻接的结点有不同的颜色 49

50 3 a c 2 4 b d 5 (a) (b) 着色图 G 的正常着色 ( 简称 着色 ) 指对 G 的每 个 结 点 指定一种颜色, 使邻接的结点具有不同的颜色 如果图 G 着色用了 n 种颜色, 则称图 G 是 n- 色的 图 G 着色所需的最少颜色数称为 G 的着色数, 记作 χ(g) 644 正常着色 Example 9 下图中, 图 (a) 着色所需的最少颜色数为 4, 因此它是 4- 色的 图 (b) 着色所需的最少颜色数为 5, 因此它是 5- 色的 645 Welch Powell 着色法 用 Welch Powell 方法对图 G 实施着色, 可以确定某个图 G 是否是 n- 色的 步骤如下 : 将图 G 的所有结点按度数递减的次序排列 ( 度数相同的结点次序随意 ); 2 用第一种颜色对度数最大的结点着色, 并按排列次序, 依次对与前面已着色 点不相邻的结点着上同样的颜色 ; 3 用第二种颜色对未着色结点按步骤 (2) 着色 ; 用第三种颜色继续如法着色,, 直到所有结点全部着色为止 646 Example 92 对下图着色 A B C D E F G H 50

51 解 : 各结点度数为 : E 度数为 6; C, G 度数为 5; A, B, D 度数为 4; F, H 度数 为 3 结点递减排序 : E, C, G, A, B, D, F, H 用红色对 E 及不相邻的结点 A 着色 ; 用蓝色对 C 及不相邻的结点 D, H 着色 ; 用黄色对 G 及不相邻的结点 B, F 着色 647 四色定理 Theorem 93 χ(k n ) = n, K n 是有 n 个结点的完全图 证 : 因完全图 K n 的每个结点与其它的 n 个结点都邻接, 所以每个结点必须着不同的颜色, 才能使邻接结点有不同的颜色, 故 K n 的着色数不少于 n 又因 n 个结点的着色数至多为 n, 因而 χ(k n ) = n Theorem 94 ( 四色定理 ) 任意平面图最多是 4- 色的 ( 证明略 ) 648 练习 六人在一起, 或者三人互相认识, 或者三人彼此不认识 解 : 将 6 个人分别用平面上 a, b, c, d, e, f 六点表示 从任一人出发, 该人与其 它五人或认识, 或不认识 如两人认识, 则相应两点用红线相连, 否则, 用蓝线相连 不失一般性, 考虑从 a 开始, 与其它五点可以有五条线相连 必有 3 条会着上相同的颜色 [ex] 假定 ab, ac, ad 为蓝色, a 如果此时 bc, cd, bd 中有一条边为蓝色 ( 比 e f 如 bd 边为蓝色 ), 则可构成一个蓝色三角形, 因而六人中有三人不认识 ; b c d 2 如果此时 bc, cd, bd 全为红色, 则 b, c, d 彼 此认识, 因而六人中有三人认识 那么五条线中 649 Example 95 如何安排大学的期末考试, 使得没有学生在同一时间有两门考试? 解 : 用结点表示课程, 若在两个结点所表示的课程里有公共的学生, 则在这两个结点之间有边 用不同颜色来表示期末考试的不同时间段 考试的安排就对应于所关联的图的着色 例如, 假定要安排七门课的期末考试, 这七门课程的编号为 到 7 不妨设下列成对的课程有公共的学生 : 和 2, 和 3, 和 4, 和 7, 2 和 3, 2 和 4, 2 和 5, 2 和 7, 3 和 4, 3 和 6, 3 和 7, 4 和 5, 4 和 6, 5 和 6, 5 和 7, 以及 6 和 7 因为这个图的色数为 4, 所以需要 4 个时间段 650 5

52 (a) (b) 52