树的定义如图, a b a b a b a b c d c d c d c d e f e f e f e f (a) G 1 (b) G 2 (c) G 3 (d) G 4 G 1 和 G 2 是树, 它们都是没有回路的简单图 G 3 不是树, 因为结点 a, b, e, d 构成回路 G 4

Size: px

Start display at page:

Download "树的定义如图, a b a b a b a b c d c d c d c d e f e f e f e f (a) G 1 (b) G 2 (c) G 3 (d) G 4 G 1 和 G 2 是树, 它们都是没有回路的简单图 G 3 不是树, 因为结点 a, b, e, d 构成回路 G 4"

苑靳
7 years ago
Views:

1 Chapter 7 树 Discrete Mathematics November 29, 2011 黄正华, 数学与统计学院, 武汉大学 71 Contents 1 树与生成树 1 2 根树及其应用树与生成树树与生成树 1 树的定义 2 生成树 3 最小生成树 4 Kruskal 算法树是图论中重要的概念之一, 在计算机科学中有广泛的运用 73 树的定义 Definition 1 一个连通且无回路的无向图称为树 (tree) 树中度数为 1 的结点叫树叶 (leave); 度数大于 1 的结点叫分枝点 (branched node) 或内点如果一个无向图的每个连通分支是树, 则称为森林 (forest) 74 1

2 树的定义如图, a b a b a b a b c d c d c d c d e f e f e f e f (a) G 1 (b) G 2 (c) G 3 (d) G 4 G 1 和 G 2 是树, 它们都是没有回路的简单图 G 3 不是树, 因为结点 a, b, e, d 构成回路 G 4 不是树, 因为它不连通 75 Theorem 2 给定图 T, 下列关于树的定义是等价的 : 1 无回路的连通图 2 无回路且 e = v 1 ( 其中 e 为边数, v 为结点数 ) 3 连通且 e = v 1 4 无回路, 但增加一条边, 得到且仅得到一个回路 5 连通, 但删除一条边则不连通 6 每对结点间有且仅有一条路 76 给定图 T, 下列关于树的定义是等价的 : 1 无回路的连通图 2 无回路且 e = v 1 ( 其中 e 为边数, v 为结点数 ) 证 : 由 (1) 证 (2) 归纳法证明当 v = 2 时, 因 T 无回路且连通, 则 e = 1, 所以 e = v 1 成立设 v = k 1 时命题成立当 v = k 时, 因 T 无回路且连通, 因而至少有一个度数为 1 的结点否则, 因各点皆连通且度数大于等于 2 从某结点 v i 出发, 可达另一个结点 v j, 再继续, 可经由一些结点后返回某结点 v i 这样就产生了回路与假设矛盾故至少有一个度数为 1 的结点删除该结点及其关联的一条边得 k 1 个结点的子图 T, 它仍是连通的, 且 e = v 1, 即 e 1 = (v 1) 1, 整理得 e = v

3 给定图 T, 下列关于树的定义是等价的 : 1 无回路的连通图 2 无回路且 e = v 1 ( 其中 e 为边数, v 为结点数 ) 3 连通且 e = v 1 4 无回路, 但增加一条边, 得到且仅得到一个回路 5 连通, 但删除一条边则不连通 6 每对结点间有且仅有一条路证 : 由 (6) 证 (1) 每对结点间有路, 则 T 连通因每对结点间仅有一条路, 则 T 无回路否则, 回路上的两点之间至少有两条道路, 与所设矛盾故 T 是无回路的连通图 78 树的概念是亚瑟凯莱 1 提出的饱和碳氢化合物与树英国数学家亚瑟凯莱在 1857 年发明了树, 当时他试图列举饱和碳氢化合物 C n H 2n+2 的同分异构体左图为什么是树? 结点数 : v = n + (2n + 2) = 3n + 2 结点度数之和 : 4 n + 1 (2n + 2) = 6n + 2 则边数 e = 3n + 1 因是连通图, 且 e = v 1, 所以是树 79 Theorem 3 任一棵树中至少有两片树叶证 : 设树 T = V, E, V = v 因 T 连通, 对任意 v i V, 有 deg(v i ) 1, 而 deg(vi ) = 2e = 2(v 1) (1) 如果 T 的每个结点的度数皆大于 2, 则 deg(vi ) 2v, 与 (1) 式矛盾如果 T 只有一个结点的度数等于 1, 则 deg(vi ) 2(v 1) + 1, 即 deg(vi ) 2v 1, 也与 (1) 式矛盾故 T 中至少有两个结点的度数等于 1, 即有两片树叶 Arthur Cayley ( ) 17 岁进入剑桥三一学院学习, 1849 年获律师资格, 在其律师生涯中写下了超过 300 篇的数学论文 1863 年返回剑桥任教职 3

4 生成树 Definition 4 若图 G 的生成子图 T 是树, 则称 T 为 G 的生成树 T 中的边叫做树枝 (branch); G 中不属于 T 的边叫做弦 (chord); 所有弦的集合称为 T 的补 711 Example 5 如图, T 1 是 G 的一棵生成树, e 1, e 3, e 5, e 7, e 8 是 T 1 的树枝 ; e 2, e 4, e 6 是 T 1 的弦 ; {e 2, e 4, e 6 } 是 T 1 的补 T 2, T 3 也是 G 的生成树 712 Theorem 6 连通图至少有一棵生成树证 : 如果图 G 连通且无回路, 则 G 就是一棵生成树连通的如果图 G 连通且有一个回路, 则删去回路上的一条边得图 G 1, 显然 G 1 也是如果 G 1 无回路, 则 G 1 是生成树如果 G 1 仍有回路, 则重复上述步骤, 直到无回路为止, 可得一个与 G 有相同结点且无回路的连通图, 它是 G 的一棵生成树 713 连通图的秩连通图的秩设 G = V, E 是一个连通图, V = n, E = m, 则 G 的生成树有 n 1 条边因此, 为得出 G 的一棵生成树应删去 m (n 1) 条边数 m (n 1) 称为 G 的秩简言之 : 连通图 G 的秩是指产生 G 的一棵生成树应删去的边数 714 最小生成树问题设有 6 个村庄 v i, i = 1, 2,, 6, 欲修建道路使村村可通现已有修建方案如下带权无向图所示, 其中边表示道路, 边上的数字表示修建该道路所需费用, 问应选择修建哪些道路可使得任意两个村庄之间是可达的, 且总的修建费用最低? 4

5 6 1 v v 3 v v v v 最小生成树 Definition 7 设图 G = V, E, 对应于 G 的每一条边 e, 指定一个正数 C(e), 称为边 e 的权设 T 是 G 的生成树, T 的各边权数之和 C(ei ) 称为树 T 的树权, 记作 C(T ) G 的所有生成树中树权最小者, 叫最小生成树最小生成树在许多实际问题中, 如交通运输, 管道铺设等, 有广泛的应用 716 Kruskal 算法 2 Theorem 8 设图 G 有 n 个结点, 以下算法产生一棵最小生成树 : 1 取最小权边 e 1, 令 i := 1; 2 若 i = n 1, 则结束否则转 3 ; 3 设已选中的边为 e 1, e 2,, e i 在 G 中选不同于 e 1, e 2,, e i 的边 e i+1, 使 {e 1, e 2,, e i, e i+1 } 中无回路, 且 e i+1 是满足此条件的最小权边 ; 4 i := i + 1, 转 Kruskal 算法注 Kruskal 算法实际求解时的两种方式 : 1 逐步选取边权最小的边, 但始终保持已选取的边不构成回路, 直到边数达到 n 1 条为止 2 不断删除边权最大的边而保持图的连通性且无回路直到边数剩 n 1 条时停止 718 5

6 (a) (a) (b) (b) 5 5 Example 9 (Kruskal 算法举例 ) 在下图中求最小生成树 ( 方法 1) 图中有 6 个结点, 所以要选取 5 条边 ( 注意 : 边权为 1, 2, 3 的边选取了之后, 边权为 6, 4 的边就不能选了否则构成回路 ) 719 Kruskal 算法举例 Example 10 在下图中求最小生成树 ( 方法 2) 720 Kruskal 算法举例 Example 11 用 Kruskal 算法给出最小生成树 a b c e f g h i j k l d 2 Joseph Bernard Kruskal (b 1929 in New York) is an American mathematician, statistician, and psychometrician 6

7 解 : 选择的步骤如下表步骤边权 1 {c, d} 1 2 {k, l} 1 3 {b, f} 1 4 {c, g} 2 5 {a, b} 2 6 {f, j} 2 7 {b, c} 3 8 {j, k} 3 9 {g, h} 3 10 {i, j} 3 11 {a, e} 3 总计 : 24 当然, 最小生成树不是惟一的, 除非图 G 中所有边的权值都不相同 721 Prim 算法另一种寻找最小生成树的算法叫做 Prim 算法, 该算法由一个权最小的边开始, 在所有相邻接的边中选择一个权值最小的边, 且不形成回路, 直到形成一个最小生成树注意 Prim 算法和 Kruskal 算法的区别 Prim 算法是在与已经选择的树相邻接的边中, 寻找最小权的边, 并且不构成回路 Kruskal 算法不要求下一个找到的边和已经找到的边相邻接, 只要求权最小而且不构成回路 722 Prim 算法举例 Example 12 用 Prim 算法给出其最小生成树 a b c e f g h d i j k l 解 : 选择的步骤如下表 7

8 步骤边权 1 {b, f} 1 2 {a, b} 2 3 {f, j} 2 4 {a, e} 3 5 {i, j} 3 6 {f, g} 3 7 {c, g} 2 8 {c, d} 1 9 {g, h} 3 10 {h, l} 3 11 {k, l} 1 总计 : 24 同样, 此问题答案不是惟一的 723 Prim 算法和 Kruskal 算法 Prim 算法和 Kruskal 算法都是一种贪婪算法所谓贪婪算法 (greedy algorithm), 是指一类采用局部最优方式的说法, 它在每次循环时都只考虑如何使本次选择做到最优, 而暂不考虑总体是否达到最优但是, 每一步最优并不一定能保证全局最优, 例如, 如果采用贪婪算法在下图中求解由 a 到 c 的最短路径, 若在每一步都选择到已选顶点最小权值的边, 将得到路径 (a, d, c), 但这并不是从 a 到 c 的最短路径 1 d a 8 c 6 2 b 4 Prim 算法和 Kruskal 算法这两个贪婪算法, 对最小生成树的结果都是最优的根树及其应用根树及其应用 1 有向树 2 m 叉树 3 有序树 4 最优树 5 前缀码 725 8

9 有向树 Definition 13 如果一个有向图在不考虑边的方向时是一棵树, 则这个有向图称为有向树 Example 14 如图为一棵有向树 : 726 有向树 Definition 15 一棵有向树, 如果恰有一个结点的入度为 0, 其余所有结点的入度都为 1, 则称为根树 (rooted tree) 1 入度为 0 的结点称为根 ; 2 出度为 0 的结点称为叶 ; 3 出度不为 0 的结点称为分枝点或内点 727 Example 16 如图为一棵根树 : v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 v 11 v 12 其中, v 1 为根, v 1, v 2, v 4, v 8, v 9 为分枝点, 其余结点为叶 728 有向树结点的层次在一棵根树中, 从根到某个结点的单向通路的长度 ( 即边数 ) 是固定的, 它叫做该结点的层次 Example 17 如图, 结点 v 2, v 3, v 4 的层次为 1 结点 v 10, v 11, v 12 的层次为 3 9

10 v 10 v 11 v 12 v 1 v 5 v 6 v 7 v 8 v 9 v 2 v 3 v 4 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 1 v 10 v 11 v 12 (a) (b) v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 v 11 v 根树的递归定义 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 v 11 v 12 根树中每一个结点都可以看作是原来树中某一棵子树的根从而, 根树可递归定义为 : Definition 18 根树包含一个或多个结点, 这些结点中某一个称为根, 其他所有结点被分成有限个子根树 730 根树的两种画法根树可以有树根在上或树根在下两种画法, 它们是同构的 Example 19 图 (a) 是根树的自然表示法 731 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 Example 20 v 10 v 11 v 12 10

11 图中, v 2 称为 v 1 的儿子, v 1 称为 v 2 的父亲 ; v 1 称为 v 5 的祖先, v 5 称为 v 1 的后裔 ; v 10, v 11, v 12 称为兄弟对其它的结点有类似的说法树的术语起源于植物学和族谱学 732 伯努利家族 3 的族谱图 Nikolaus ( ) Jacob I ( ) Nikolaus I ( ) Johann I ( ) Ṅikolaus II ( ) Nikolaus III ( ) Johann II ( ) Daniel ( ) Johann III ( ) Jacob II ( ) 733 m 叉树 Definition 21 1 在根树中, 若每个结点的出度小于等于 m, 则称该树为 m 叉树 2 如果每个结点的出度恰好等于 m 或 0, 则称该树为完全 m 叉树 3 如果完全 m 叉树所有树叶的层次都相同, 则称为正则 m 叉树 734 Example 用 m 叉树表示实际问题 Example 23 M 和 E 两人进行网球比赛, 如果一人连胜两局或一共胜三局, 则比赛结束, 试用二叉树表示比赛可能发生的各种情况解 : 用二叉树的分枝点表示每局赛事, 每局比赛的胜负标在其两个儿子结点的旁边从树根到树叶的每一条路对应比赛可能发生的一种情况 : EE, MM ; EMM, MEE ; 736 EMEE, MEMM; EMEME, EMEMM, MEMEE, MEMEM 3 著名的瑞士数学家家族见 : ET 贝尔数学精英 P152, 商务印书馆 11

12 (a) 三叉树 (b) 完全二叉树 (c) 正则二叉树 Theorem 24 设有完全 m 叉树, 其树叶数为 l, 分枝点数为 i, 则 (m 1)i = l 1 证 : 可将完全 m 叉树视为每局有 m 位选手参加比赛的单淘汰赛计划表树叶数 l 表示参加比赛的选手数, 分枝点表示比赛的局数因每局比赛将淘汰 (m 1) 位选手, 故比赛结果共要淘汰 (m 1)i 位选手, 最后得出一位冠军因此 (m 1)i + 1 = l, 即 (m 1)i = l 例如左图所示为 9 位选手参加比赛的情况 : l = 9, i = 4, m = 完全 m 叉树的性质事实上, 这个定理还有一个简单的证明对完全 m 叉树, 设其树叶数为 l, 分枝点数为 i, 则结点总数 n 为 n = l + i, 或 n = mi + 1 所以 l + i = mi + 1, 即 (m 1)i = l 1 其中 n = mi + 1 是因为每个分枝点都有 m 个儿子, 且全部结点中只有树根不是某个结点的儿子这个结论可以作为一个定理 Theorem 25 对完全 m 叉树, 若分枝点数为 i, 则结点总数为 n = mi 完全 m 叉树的性质从上面的讨论中, 我们还可以看到, 对完全 m 叉树, 知道 l, i, n 这三个中的一个, 则其它两个必定可求 12

13 Theorem 26 对完全 m 叉树, 1 若结点总数 n 为已知, 则分枝点数为 i = (n 1)/m, 树叶数为 l = n i = n (n 1)/m 2 若分支点数 i 为已知, 则结点总数为 n = mi + 1, 树叶数为 l = n i = (m 1)i 若树叶数 l 为已知, 则结点总数为 n = (ml 1)/(m 1), 分枝点数为 i = (l 1)/(m 1) 739 Example 27 假定我们开始一个发送手机短信的游戏, 要求每个收到短信的人把短信再转发给另外某 4 个人, 每人只能收到一次短信有些人收到短信后这样做了, 但是有些人收到短信后没有转发如果某个时刻已经有 100 人收到了短信而没有转发, 问有多少人发出过短信? 解 : 可以用一个完全 4 叉树表示这个过程每个人是一个结点, 收到了短信而没有转发的人是树叶, 转发了短信的人是分枝点, 则树叶总数是 l = 100 分枝点数为 i = l 1 m 1 = = 33, 所以一共有 33 人发出了短信 740 有序树在根树中, 一般将树根放在最上面, 但分枝点关联的各分枝的左中右按顺序却有种种不同的摆法所以, 标定根树中结点和边的次序在应用中是必要的标定了结点和边的次序的根树叫有序树任一有序树都可用二叉树来表示 741 有序树写为对应的二叉树任何一棵有序树都可以改写为一棵对应的二叉树, 方法如下 : 1 删除始于每个结点除最左边的一个分枝外的其余分枝 ; 在同一层次中的兄弟结点之间用自左到右的有向边连接 2 对某个结点, 直接位于该结点下面的结点作为左儿子位于同一水平线上与该结点右邻的结点作为右儿子 3 改写之后的树根仅有一个儿子, 规定是左儿子下页是一个例子

14 (a) (b) O O A D A D B C E F G B C E F G K H J K H J (a) (b) A O B K D C E H F (c) J G 14

15 通路长度 Definition 28 1 在根树中, 从树根到某结点的通路的边数叫该结点的通路长度 2 将分枝点的通路长度称为内部通路长度 ; 3 树叶的通路长度叫外部通路长度 O B A C E D F G 例如, 图中结点 K 的通路长度为 3; 结点 F 的通路长度为 2; 744 K H I J Theorem 29 设完全二叉树有 n 个分枝点 ( 含根结点 ), 且内部通路长度的总和为 I, 外部通路长度的总和为 E, 则 E = I + 2n 例如上图为一棵完全二叉树, 其中有 9 个结点, 分枝点 ( 即内点 ) 有 4 个, I = = 4, E = = 12 证 : 对分枝点数 n 进行归纳证明当 n = 1 时, E = 2, I = 0, 故公式成立续证 : 假设 n = k 1 时成立当 n = k 时, 若删去一个分枝点 v ( 即删除该分枝点的儿子 ) 设该分枝点的通路长度为 l, 且 v 的两个儿子是树叶, 得出的新树为 T 与原树相比, T 减少了两片通路长度为 l + 1 的树叶和一个通路长度为 l 的分枝点, 所以, E = E 2(l + 1) + l, 且 I = I l 又 T 有 k 1 个分枝点, 所以 E = I + 2(k 1) 代入前两式并整理得 E = I + 2k

16 (a) T (b) T a 2 d b 1 e f 1 c 5 h g 3 i Figure 1: 带权二叉树 T 最优树 Definition 30 设二叉树有 t 片树叶, 各片树叶分别带有权数 w 1, w 2,, w t, 则该二叉树称为带权二叉树设带权二叉树中权为 w i 的树叶的通路长度为 L(w i ), 将 t w(t ) = w i L(w i ) 称为带权二叉树的权在所有带权 w 1, w 2,, w t 的二叉树中, w(t ) 最小的树称为最优树 Example 31 t w(t ) = w i L(w i ) i=1 i=1 = = Theorem 32 设 T 为带权 w 1 w 2 w t 的最优树, 则 1 带权 w 1, w 2 的树叶 v w1, v w2 是兄弟 2 以树叶 v w1, v w2 为儿子的分枝点的通路最长简而言之 : 最优树中具有最小权的两片树叶是兄弟, 且其通路长度最大证 : 设带权 w 1, w 2,, w t 的最优树中, v 是通路最长的分枝点 v 的两个儿子分别带权 w x, w y 那么 L(w x ) L(w 1 ), L(w y ) L(w 2 ) 若 L(w x ) > L(w 1 ), 将 w x 与 w 1 对调得到新树 T, 则 w(t ) w(t ) = ( ) ( ) L(w x )w 1 + L(w 1 )w x L(wx )w x + L(w 1 )w 1 = L(w x )(w 1 w x ) + L(w 1 )(w x w 1 ) = (w x w 1 ) ( L(w 1 ) L(w x ) ) < 0 16

17 d w 3 h i a b c w 4 w 5 e g f w 6 w 1 w 2 j k (a) T d w 3 h i a b c w 4 w 5 w 1 + w 2 e g f w 6 (b) T 所以 w(t ) < w(t ), 与 T 是最优树的假设矛盾, 故 L(w x ) = L(w 1 ) 同理可证 L(w x ) = L(w 2 ) 所以 L(w 1 ) = L(w 2 ) = L(w x ) = L(w y ) 分别将 w 1, w 2 与 w x, w y 对调, 得出最优树, 带权 w 1, w 2 的树叶是兄弟 748 Theorem 33 设 T 为带权 w 1 w 2 w t 的最优树, 若将以带权 w 1, w 2 的树叶为儿子的分枝点改为带权 w 1 + w 2 的树叶, 得到一棵新树 T, 则 T 也是最优树注意 : w(t ) = w(t ) + w 1 + w 2 简而言之 : 求带 t 个权的最优树, 可简化为求带 t 1 个权的最优树证 : 由题设可知 : w(t ) = w(t ) + w 1 + w 2 (2) 若 T 不是最优树, 则必有另一棵带权 w 1 + w 2, w 3,, w t 的最优树 T 将 T 中带权 w 1 + w 2 的树叶 v w1 +w 2 生成两个儿子 ( 带权 w 1, w 2 的树叶 ), 得到新树 T, 则 w( T ) = w(t ) + w 1 + w 2 (3) 由假设, w(t ) w(t ) 如果 w(t ) < w(t ), 比较 (2), (3) 式可知 w( T ) < w(t ), 与 T 是带权 w 1, w 2,, w t 的最优树相矛盾因此, w(t ) = w(t ) 即 T 是带权 w 1 + w 2, w 3,, w t 的最优树 749 前缀码 Definition 34 给定一个序列的集合, 如果不存在一个序列是另一个序列的前缀, 则该序列的集合称为前缀码例如, {100, 101, 00, 01, 11} 是前缀码, 而 {001, 010, 00, 01, 10} 就不是前缀码 750 Theorem 35 任意一棵二叉树对应一个前缀码 17

18 Figure 2: 带权二叉树 T 证 : 给定一棵二叉树, 从每个分枝点出发, 将左枝标为 0, 右枝标为 1, 则每片树叶对应一个 0 和 1 组成的序列, 该序列是从树根到该树叶的通路上各边标号组成的显然, 没有一片树叶对应的序列, 是另一片树叶对应序列的前缀所以任意一棵二叉树对应一个前缀码 751 Theorem 36 任意一个前缀码对应一棵二叉树证 : 设 h 是某个前缀码中最长序列的长度作一棵高为 h 的正则二叉树, 将每个分枝点的左右枝分别标以 0 和 1, 则每片树叶对应一个 0 和 1 组成的序列, 该序列是从树根到该树叶的通路上各边标号组成的因此, 长度不超过 h 的每个 0 和 1 组成的序列必对应一个结点将对应于前缀码中的每个序列的结点给予一个标记, 并删去标记结点的后裔及由它们射出的边再删去未加标记的树叶, 得到一棵新的二叉树, 其树叶就对应给定的前缀码 Example 37 给定前缀码 {000, 001, 01, 1}, 求对应的二叉树解 : 裔作一棵高为 3 的正则二叉树 ; 标记对应前缀码的结点, 并删去标记结点的后

19 (a) T (b) T 由前缀码和二叉树的对应关系可知, 如果给定的前缀码对应的二叉树是完全二叉树, 则根据此前缀码可对任意二进制序列译码例如, 由前例中的前缀码 {000, 001, 01, 1} 可对任意二进制序列译码随意写一个由 0 和 1 组成的字符串, 例如 : 它可译为且只能译为 : 000, 1, 001, 1, 01, 1, 1, 01, 001 如果被译的序列的最后部分不能构成前缀码中的序列, 可约定添加 0 或 1, 直到能译出为止如果前缀码对应的二叉树不是完全二叉树, 例如 {000, 001, 1} 也是前缀码, 但它不能对任意二进制序列译码上述二进制序列, 用这组编码就无法译出 754 练习 ( ) ( ) 用根树表示 P ( P Q) ( P Q) R 解 : P Q Q R P P 755 Example 38 试用有向图描述下列问题的解 : 某人 m 带一条狗 d, 一只猫 c 和一只兔子 r 过河 m 每次游过河时只能带一只动物, 而没人管理时, 狗与兔子不能共处, 猫和兔子也不能共处问 m 怎样把三个动物带过河去? 19

20 分析 : 用结点代表状态, 状态用序偶 S 1, S 2 来表示, 这里 S 1, S 2 分别是左岸右岸的人和动物的集合例如初始状态为 {m, d, c, r},, 最终的目的即是, {m, d, c, r} 注意不能出现集合 {d, r}, {c, r} 当出现集合 {d, r} 或 {c, r} 时, 方案终止如果出现之前已有的状态, 方案也终止, 如下一页图中第 4 层出现的 {d, m, c}, {r} 和 {c, m, d}, {r}, 都是返回到了第 2 层的状态 {m, d, c}, {r}, 从而方案终止 756 解 : 注意到不能出现集合 {d, r} 或 {c, r}, 描述上述问题的有向图如下 {m, d, c, r}, {c, r}, {m, d} {d, c}, {m, r} {d, r}, {m, c} {m, d, c}, {r} {d}, {m, r, c} {c}, {m, r, d} {d, m}, {r, c} {d, m, r}, {c} {d, m, c}, {r} {c, m}, {r, d} {c, m, r}, {d} {c, m, d}, {r} {r}, {c, d, m} {r}, {c, d, m} {r, m}, {c, d} {r, m}, {c, d}, {m, d, c, r}, {m, d, c, r}

第三章树 3.1 树的有关定义

第三章树 3.1 树的有关定义第三章树 3. 树的有关定义给定一个图 G=(V,E), 如果它不含任何回路, 我们就叫它是林, 如果 G 又是连通的, 即这个林只有一个连通支, 就称它是树. 定义 3.. 一个不含任何回路的连通图称为树, 用 T 表示. T 中的边称为树枝, 度为的节点称为树叶. 有关度的若干术语孤立点 : 度为 0 的顶点悬点 : 度为的顶点悬边 : 与悬点关联的边奇点 : 度为奇数的顶点偶点

树的定义 如图, a b a b a b a b c d c d c d c d e f e f e f e f (a) G 1 (b) G 2 (c) G 3 (d) G 4 G 1 和 G 2 是树, 它们都是没有回路的简单图 G 3 不是树, 因为结点 a, b, e, d 构成回路 G 4

树的定义如图, a b a b a b a b c d c d c d c d e f e f e f e f (a) G 1 (b) G 2 (c) G 3 (d) G 4 G 1 和 G 2 是树, 它们都是没有回路的简单图 G 3 不是树, 因为结点 a, b, e, d 构成回路 G 4