2 版权所有, 翻印必究

Size: px

Start display at page:

社兑傅
7 years ago
Views:

1 离散数学基础 : 图论 Fundamentals of Discrete Mathematics: Graph Theory 周晓聪 (isszxc@zsu.edu.cn) 中山大学计算机科学系, 广州年 10 月 27 日

3 第二章树的基本概念这一章我们考虑与树有关的基本概念, 包括无向树的定义及基本性质图的关联矩阵与生成树的计数有向树 ( 根树 ) 和二叉树的性质, 以及最优二叉树 (Huffman 树 ) 的构造及应用等 2.1 树的基本定义定义若简单连通图 G = (V, E) 没有回路, 则称 G 是 ( 无向 ) 树无向树中度数为 1 的顶点称为树叶, 度数大于等于 2 的顶点称为分支点只有一个顶点 ( 无边 ) 的简单图称为平凡树 ; 若 G 含有多个无回路的连通分支, 则称 G 是森林也就是说,( 无向 ) 树就是连通无回路的简单图后面在提到树时, 如果没有特别说明都是指无向树在证明树的性质之前, 先会议一下桥 ( 或说割边 ) 的定义, 我们将看到树的每一条边都是桥定义给定图 G = (V, E), 说边 e E 是 G 的桥 ( 割边 ), 如果 p(g e) > p(g), 即 G 中删除 e 之后会增加连通分支数显然, 如果 e 是 G 的桥, 则有 p(g e) = p(g) + 1, 即删除一条边, 最多增加一个连通分支另一方面, 若 e 是 G 的桥, 则 e 不属于 G 的任意回路根据这些基本常识, 下面证明树的基本性质定理给定简单图 G = (V, E), V = n, E = m, 下面各命题等价 : (1) G 是树 ( 即 G 连通且无回路 ); (2) G 的任意两个顶点存在惟一的道路 ; (3) G 连通且任意边都是桥 ; (4) G 无回路, 但在任何两个不相邻顶点之间加一条新边, 则得到惟一一个含新边的回路证明我们采用循环论证法, 即证明 (1) (2) (3) (4) (1) (1) (2): 由于 G 是连通的, 因此 G 的任意两个顶点之间都存在道路, 而若 G 的两个顶点之间存在两个不同的道路, 则这两个道路构成回路, 与 G 无回路矛盾, 因此 G 的任意两个顶点必存在惟一的道路 (2) (3): 当 G 的任意两个顶点存在惟一的道路时, 显然 G 是连通的对 G 的任意边 e = (u, v), 如果 e 不是 G 的桥, 则 G e 仍是连通的, 即存在以 u 和 v 为端点的道路 Γ, 那么 G 就存在以 u 和 v 的两条道路 Γ 和 Γ = uev, 矛盾, 因此 G 的任意边必是桥 (3) (4): 因为 G 的任意边都是桥, 因此 G 无回路, 因此 G 连通且无回路, 即 G 是树, 从而由 (1) (2) 得 G 的任意两个顶点之间只存在惟一的道路, 从而若在 G 的两个不相邻顶点之间加一条 1

4 2 第二章树的基本概念新边, 必得到含有该新边的回路, 且该回路是惟一的 ( 不然则这两个顶点之间原来就会有两条不同的道路, 矛盾!) (4) (1): 只要证明 G 是连通的, 对 G 的任意两个顶点 u, v, 如果 u 和 v 相邻, 则 u 和 v 是可达的 ; 如果 u 和 v 不相邻, 则在 u 和 v 之间增加一条新边可得到惟一一个含该新边的回路, 这表明在 G 中 u 和 v 也是可达的因此 G 的任意两个顶点都是可达的, 即 G 是连通的定理给定简单图 G = (V, E), V = n, E = m, 下面各命题等价 : (1) G 是树 ( 即 G 连通且无回路 ); (2) G 连通且任意边都是桥 ; (3) G 无回路且 m = n 1; (4) G 连通且 m = n 1; 证明由于 (1) 和 (2) 的等价性上面已经证明, 因此这里只要证明 (2) (3) (4) (2) 即可 (2) (3): 显然这时 G 没有回路, 我们使用归纳法证明 m = n 1 当 n = 1 时,G 为平凡图 ( 平凡树 ),m = 0, 显然 m = n 1 假定对任意少于 k 个顶点的连通图 G, 若 G 的任意边都是桥时,G 的边数等于顶点数减一考虑具有 k 个顶点的图, 对 G 的任意边 e, 因为 G 连通且 e 是桥, 因此 p(g e) = 2, 设 G 的两个连通分支分别是 G 1 和 G 2, 其顶点数分别是 n 1 和 n 2, 边数分别是 m 1 和 m 2, 则显然 G 1 和 G 2 的任意边仍然是桥, 且 n 1 < k 和 n 2 < k, 根据归纳假设有 m 1 = n 1 1 且 m 2 = n 2 1, 从而 G 共有 n n = n 1 + n 2 1 = k 1 条边, 命题成立因此当 G 连通且任意边是桥时,G 无回路且边数等于顶点数减 1 (3) (4): 这只要证明 G 是连通的, 用反证法, 设 G 有 k > 1 个连通分支, 每个连通分支的顶点数分别是 n 1,, n k, 则 G 的每个连通分支无回路, 即 G 的每个连通分支是树, 从而 G 的每个连通分支的边数分别是 n 1 1,, n k 1, 从而 G 的边数 m 为 n n n k 1 = n k, 当 k > 1 时与 m = n 1 矛盾! 因此必有 k = 1, 即 G 是连通图 (4) (2): 只要证明当 G 连通且 m = n 1 时,G 的任意边都是桥对 G 的任意边 e, 若 G e 是连通的, 则由于 G e 的顶点数仍然是 n, 而连通简单图的边数要大于顶点数减 1, 因此 G e 的边数要大于等于 n 1, 但 G 的边数 m = n 1, 从而 G e 的边数是 n 2, 因此必有 G e 是不连通的, 这就说明 e 是桥总的来说, 上面两个定理说明树具有这样的性质 :(i) 连通无回路 ;(ii) 边数等于顶点数减一 ;(iii) 每条边都是桥 ;(iv) 任意两个顶点之间有惟一的道路 ;(v) 任何两个不相邻顶点之间加新边得惟一的回路我们通常用 T = (V, E) 表示树例子若 T = (V, E) 是树, 且 V = n 2, 则 T 至少有两片树叶, 即至少有两个度数为 1 的顶点证明因为 T 是连通图, 所以对 T 的任意顶点 v 都有 d(v) 1, 如果 T 至少有 n 1 个顶点的度数大于等于 2, 设 T 的边数为 m, 则 2m = v V d(v) 2(n 1) + 1 即 m n, 这与 m = n 1 矛盾, 因此 T 至多只有 n 1 个顶点的度数大于等于 2, 也即至少有两个顶点的度数为 1

5 2.2 生成树生成树任何无向连通图都存在一棵树作为它的子图, 我们称这种树为无向连通图的树, 特别地, 若这种树是图的生成子图 ( 即顶点数一样的子图 ), 则称其为生成树 : 定义给定无向连通图 G = (V, E)( 不一定是简单图 ), 若 T = (V, E ) 是 G 的生成子图且是树, 则称 T 是 G 的生成树若 T 是 G 的生成树, 则对任意的边 e E, 若 e E, 则称 e 是 T 的树枝, 否则称 e 是 T 的弦, 并称由 G 的顶点和 T 的弦构成的 G 的子图 ( 即 G T) 称为 T 的余树, 记为 T 注意 G 的生成树 T 的余树 T 不一定连通, 也不一定不含有回路, 因此 T 不一定是树很容易证明 : 引理任意无向图 G = (V, E) 具有生成树当且仅当 G 是连通图证明显然当 G 具有生成树时,G 是连通图, 因此生成树本身是连通图反之, 当 G 是连通图时, 若 G 无回路, 则 G 就是自己的生成树 ; 若 G 含有回路, 任取一回路, 随意地删除回路上的一条边, 若再有回路则继续删除回路上的边, 直到不含有任意回路为止, 最后得到的图仍然是连通的 ( 因为删除回路上的边不会增加连通分支 ), 而且是无回路的, 也即就是 G 的生成树通常人们称这种产生生成树的方法为破圈法推论设图 G 是 n 个顶点 m 条边的无向连通简单图, 则 m n 1 推论设图 G 是 n 个顶点 m 条边的无向连通简单图,T 是 G 的生成树, 则 T 的余树 T 有 m n + 1 条边推论设 T 是连通图 G 的一棵生成树,T 是它的余树, 则 G 的任意回路 C 必含 T 中的边 ( 即 T 的弦 ) 证明因为否则的话, 回路 C 的边都在树 T 中, 这与 T 无回路矛盾更进一步可证明下面的定理 : 定理设 T 是连通图 G 的一棵生成树,e 为 T 的弦, 则 T {e} 必含有一个回路使得该回路除了含有弦 e 之外不再有 T 的其他弦证明设 e = (u, v), 则 T 中有 u 到 v 的惟一道路 Γ, 显然 Γ {e} 是含有弦 e 的回路显然不同的弦含的回路也不同, 我们有如下的定义 : 定义设 T 是 n 个顶点 m 条边的无向连通简单图 G 的一棵生成树, 设 e 1, e 2,, e m n+1 是 T 的弦, 设 C r 是 T 添加弦 e r 后产生的只含弦 e r, 其他边都是树枝的回路, 称 C r 是 G 的对应 T 的弦 e r 的基本回路, 称 {C 1, C 2,, C m n+1 } 是 G 对应 T 的基本回路系统注意, 不同生成树的基本回路系统可能不同, 但不同生成树的基本回路系统中回路数目是一样的, 即都是 m n + 1 从弦导出基本回路系统, 从树枝则可得到基本割集系统首先有如下定理 : 定理设 T 是连通图 G 的一棵生成树,e 是 T 的树枝, 则 G 存在只含树枝 e, 其他边都是弦的边割集, 且不同的树枝对应的边割集也不同

6 4 第二章树的基本概念证明根据树的基本性质,e 是 T 的桥, 因此 T e 有两个连通分支 T 1, T 2, 令 S e = {(u, v) u T 1 v T 2 } 即 S e 种是哪些两个端点分属于 T 1 和 T 2 的边构成的边集, 显然 S e 是边割集, 而且 e S e, 且 S e 中的其他边都是弦 ( 否则作为树 T 的连通分支 T 1 和 T 2 有边相连 ) 定义设 T 是有 n 个顶点的连通图 G 的一棵生成树 e 1, e 2,, e n 1 是 T 的树枝 S i 是 G 的只含树枝 e i 的边割集, 则称 S i 是 G 的对应 T 由树枝 e i 生成的基本割集, 称 {S 1, S 2,, S n 1 } 为 G 对应 T 的基本割集系统同样, 不同生成树的基本割集系统也可能不同, 但不同生成树的基本割集系统中的边割集数目都是一样的, 即 n 1 例子考虑下面的图 ( 参见耿素云屈婉玲教材 [4]p309 的图 16.3): e 1 e 2 e 7 e 4 e 5 e 10 e 8 e 9 e 6 e 3 e11 其中实线给出的边构成了上图的生成树, 它的弦包含 e 6, e 7, e 8, e 10, e 11, 对应的基本回路系统是 : C 6 = e 6 e 4 e 5 C 7 = e 7 e 2 e 1 C 8 = e 8 e 9 e 2 e 1 C 10 = e 10 e 3 e 5 e 2 C 11 = e 11 e 3 e 5 e 2 e 9 该生成树的树枝包括 e 1, e 2, e 3, e 4, e 5, e 9, 对应的基本割集系统是 : S 1 = {e 1, e 7, e 8 } S 2 = {e 2, e 7, e 9, e 10, e 11 } S 3 = {e 3, e 10, e 11 } S 4 = {e 4, e 6 } S 5 = {e 5, e 6, e 10, e 11 } S 6 = {e 9, e 8, e 11 } 为了得到连通图的所有生成树及其数目, 我们考虑图的关联矩阵 : 定义给定有向图 G = (V, E), 设 V = {v 1, v 2,, v n }, 而 E = {e 1, e 2,, e m }, 则 G 的关联矩阵 B = [b ij ] 是 n m 的矩阵, 对任意的 1 i n, 1 j m 有 : b ij = 1 1 若 v i 是 e j 的起点若 v i 是 e j 的终点 0 否则

7 2.2 生成树 5 显然, 任何一个有向图的关联矩阵具有如下特征 :(i) 孤立点对应的行向量为零向量 ;(ii) 每个列向量有且仅有两个非零元 1 和 1;(iii) 如果该有向图不连通, 则通过适当重排之后, 其关联矩阵可变成对角分块矩阵关联矩阵的秩与有向图的弱连通性有密切关系, 为方便起见, 我们将有向图不考虑边之后得到的无向图称为该有向图的基图我们不加证明地给出如下命题, 有关证明可参考耿素云教材 [1] 的 10.1 节 ( 定理 10.1) 命题弱连通有向图 G = (V, E) 的关联矩阵 B 的秩 r(b) = V 1 有向图的关联矩阵划去一行向量后得到的矩阵称为该有向图的基本关联矩阵定义给定有向图 G = (V, E), 设 V = {v 1, v 2,, v n }, 而 E = {e 1, e 2,, e m } 其关联矩阵 n m 矩阵 B, 称划去 B 中对应顶点 v k 对应的行向量得到的 (n 1) m 矩阵 B k 为 G 的对应 v k 的基本关联矩阵基本关联矩阵与有向图的基图中的回路有如下关系 : 命题给定有向图 G = (V, E), 设 V = {v 1, v 2,, v n }, 而 E = {e 1, e 2,, e m } B k 是 G 的基本关联矩阵设 Γ = v i1 e i1 v i2 e i2 e ij v i1 是 G 的基图的一个简单回路, 则 e i1,, e ij 对应的 B k 的各列向量线性相关证明参见戴一奇教材 [3]3.2 节定理根据这个性质可以证明 : 命题给定有向弱连通图 G = (V, E), V = n, 其基本关联矩阵 B k 的任一 (n 1) 阶子阵非零的充要条件是 : 该子阵各列对应的图 G 的边 ( 不考虑方向 ) 构成 G 的基图的一棵生成树证明参见戴一奇教材 [3]3.2 节定理 3.2.6, 或参考耿素云教材 [1] 的 10.1 节 ( 定理 10.3) 根据在矩阵理论中的 Binet-Cauchy 定理可以对图的生成树进行计数 : 命题设 B k 是有向弱连通图 G = (V, E) 的某一基本关联矩阵, 则 G 的不同树的生成树数目是 ( 下面的 B i 是 B k 的某一 n 1 阶子阵, 而下面的求和则取遍 B k 的所有可能 n 1 阶子式 ): B k B T k = i B i B T i = i B i 2 如果要给出图 G 的所有生成树, 则可在 B k 中用 E 中相应的元素标记, 得到矩阵 B e k = (be ij), 即令 : 则 B e k BT k 给出所有生成树的清单证明参见戴一奇教材 [3]3.3 节定理 e j 若 b ij = 1 b e ij = e j 若 b ij = 1 0 否则

8 6 第二章树的基本概念我们以一个比较简单的例子来说明上述定理的使用 : 例子求下图的生成树的数目 : v 1 e 1 v 2 e 4 e 3 e 2 v 4 e 5 v 3 解 : 任取该图的一个基本关联矩阵, 例如 B 4 : B 4 = 如果直接计算 B 4 B T 4 则有 : B 4 B4 T = = 如果利用 Binet-Cauchy 定理则共有 C 3 5 = 10 种可能, 从而有 : B 4 B4 T = 显然除了第一个和最后一个行列式为 0 之外, 其他的行列式的值都等于 1

9 2.2 生成树 7 为了给出所有生成树, 我们计算 : e 1 e B4B e 4 T e 1 + e 2 e 1 0 = e 1 0 e 3 e = e e 4 e 5 1 e 1 + e 3 + e 4 e e 4 e 4 + e = (e 1 + e 2 )((e 1 + e 3 + e 4 )(e 4 + e 5 ) e 2 4) e 2 1(e 4 + e 5 ) = (e 1 + e 2 )(e 1 e 4 + e 1 e 5 + e 3 e 4 + e 3 e 5 + e 4 e 5 ) e 2 1e 4 e 2 1e 5 = e 1 e 3 e 4 + e 1 e 3 e 5 + e 1 e 4 e 5 + e 2 e 1 e 4 + e 2 e 1 e 5 + e 2 e 3 e 4 + e 2 e 3 e 5 + e 2 e 4 e 5 这就得到了所有的生成树, 即由边 e 1, e 3, e 4 构成的生成树, 由 e 1, e 3, e 5 构成的生成树, 等等对于无向连通图, 我们可以将该无向图的每一条边随意地给一个方向, 然后利用上面的方法计算所得到的弱连通有向图的所有生成树, 去掉树边的方向, 则得到无向图的生成树我们也可使用另外一种方法得到无向连通图的所有生成树对于无向连通图 G, 由于环不会在生成树中出现, 因此我们将 G 中的环去掉, 或者不妨假设 G 不含环设 e 是 G 的一条边, 则 G 的含 e 的生成树则与图 G\e 的生成树一一对应, 这里 G\e 是图 G 对边 e 的收缩, 则将 e 的两个端点 u, v 缩成一个顶点 w, 原先与 u, v 关联的边都与 w 关联容易证明,G 中存在含 e 的回路当且仅当 G\e 中存在过 w 的回路, 因此 G 的含 e 的生成树 T 在不考虑边 e 的时候是 G\e 的生成树, 因为 T 显然是 G\e 的生成子图 ( 即是 G\e 的子图且有相同的顶点 ), 而且 T 连通 ( 因为在 G 中连通 ), 而且不含有回路, 因为在 G 中没有回路, 则在 G 中没有含边 e 的回路, 从而 T 在 G\e 中没有过 w 的回路, 而 T 作为 G 的生成树不可能在 G\e 中含不过 w 的回路类似地, 可证明 G\e 的生成树 T, 加上边 e 后是 G 的生成树, 即 G 的必含 e 的生成树与 G\e 的生成树一一对应另一方面,G 的不含 e 的生成树则显然与图 G e 的生成树一一对应注意, 若这是 e 是割边, 则 G e 是非连通图, 从而不存在生成树, 也即 G 的生成树必含有 e 这样我们证明了: 定理设 G 是无向连通图,e 是 G 的一条非环边, 则 G 的生成树数目等于图 G e 的生成树数目与图 G\e 的生成树数目之和注意, 在利用 G e 和 G\e 计算 G 的生成树时, 遇到环 ( 通常是图 G\e 产生环 ) 时, 应自动忽略它们下面以例子说明这种计算生成树的方法例子求下图的生成树的数目 : v 1 v2 e 1 e 2 e 4 e 3 v 4 e 5 v 3 根据上述定理, 该图不含 e 1 的生成树与下面左图 ( 即 G e 1 ) 的生成树一一对应, 而含 e 1 的生成树与下面右图 ( 即 G\e 1 ) 的生成树一一对应 ( 由于顶点在求生成树不起关键作用, 下面的图都不再标出顶点 ):

10 8 第二章树的基本概念 e 2 e 2 e 3 e 4 e 4 e 3 e 5 对于上面左图 ( 即图 G e 1 ), 由于 e 2 是割边, 因此它不存在不含 e 2 的生成树, 而它含 e 2 的生成树与下面左图 ( 即图 (G e 1 )\e 2 ) 一一对应 : e 3 e4 e 5 e 4 e 5 显然上面左图 ( 即图 (G e 1 )\e 2 ) 中不含 e 3 的生成树就是 e 4 e 5, 对应地, 原图 G 就有生成树 e 2 e 4 e 5, 而上面左图 ( 即图 (G e 1 )\e 2 ) 中含 e 3 的生成树与上面右图 ( 即图 ((G e 1 )\e 2 )\e 3 ) 的生成树一一对应, 显然这个图的生成树分别是 e 4 和 e 5, 对应地原图 G 就有生成树 e 2 e 3 e 4 和 e 2 e 3 e 5 类似地, 对于图 G\e 1, 其不含 e 2 的生成树与下面左图 ( 即图 (G\e 1 ) e 2 ) 的生成树一一对应, 而含 e 2 的生成树与下面右图 ( 即图 (G\e 1 )\e 2 ) 的生成树一一对应 : e 5 e 3 e 3 e4 e 5 e 4 e 5 注意, 在图 (G\e 1 )\e 2 中,e 3 收缩成了环, 我们将它忽略后, 上面两个图看似与前面的两个图一样, 但对于原图而言得到的生成树不同, 这时得到原图 G 的生成树分别是 e 1 e 4 e 5 ( 不含 e 3 的生成树 ),e 1 e 3 e 4 和 e 1 e 3 e 5 ( 两棵含 e 3 的生成树 ), 以及 e 1 e 2 e 4 和 e 1 e 2 e 5 ( 两棵含 e 2 但不含 e 3 的生成树 ) 综上我们得到 G 的所有生成树 : e 2 e 4 e 5 e 2 e 3 e 4 e 2 e 3 e 5 e 1 e 4 e 5 e 1 e 3 e 4 e 1 e 3 e 5 e 1 e 2 e 4 e 1 e 2 e 5 可以看出, 用这种方法计算生成树比用关联矩阵的计算更为繁琐, 程序实现起来也会更困难 2.3 根树定义如果一个弱连通有向图不考虑边的方向是树, 则称这个图是有向树若有向树 T 有且仅有一个顶点 v 的入度为 0, 则称 T 是以 v 为根的根树我们将根树中出度为 0 的顶点为叶子定义对于根树 T = (V, E),T 的两个顶点 u, v 若有有向边 e = u, v E, 则称 u 是 v 的父亲, 而 v 是 u 的儿子 ; 若存在 u 到 v 的一条有向道路, 则称 u 是 v 的祖先, 而 v 是 u 的后代定义对于根树 T = (V, E), 设其根为 v, 则对 T 的任意顶点 u, 从 v 到 u 的惟一道路的长度称为 u 的深度定义 T 的高度是从 v 到 T 的叶子最长道路的长度

11 2.3 根树 9 显然根节点的深度为 0, 我们称之为第 0 层节点 ; 深度同为 i 的节点称为第 i 层节点, 具有最大深度的节点的深度为树的深度 ( 高度 ) 对于根树, 如果将每个节点的儿子按照某种特定的次序 ( 例如在画的时候从左至右的次序 ) 排列, 则称该根树为有序根树, 如果有序根树的所有节点的出度不大于 m, 则称为 m 元树 ( 或说 m 叉树 ); 如果有序根树的所有节点的出度都是 0 或 m, 则称为 m 元正则树 ( 或说 m 叉正则树 ) 根树在计算机科学及实际生活中有许多应用, 例如语法树判定树 ( 决策树 ) 等都是根树的例子也许在计算机科学中用得最多的是二元 ( 叉 ) 树定义二叉树是二元有序树, 即每个节点的出度不大于 2, 且每个节点的儿子按一定顺序排列的根树每个节点的出度为 0 或 2 的二叉树称为正则二叉树通常我们将二叉树某个节点的两个儿子节点区分为左儿子和右儿子节点不难看出, 二叉树具有这样的特点 :(i) 第 k 层最多有 2 k 个节点 ;(ii) 高度为 k 的二叉树最多有 2 k+1 1 个节点进一步,m 元有序树都可转化为一棵二叉树 : 以某个结点的最左儿子作为该结点的左儿子, 而以该结点的右兄弟作为该结点的右儿子例子设 T 是二叉树, 其出度为 2 的节点数目是 n 2, 叶子结点的数目是 n 0, 证明 n 0 = n 证明对 T 的结点个数 n 进行归纳, 显然当 n = 1 时, 一个叶子结点, 零个出度为 2 的节点, 因此命题成立 ; 设对于任意小于 k 个结点的二叉树叶子数等于出度为 2 的节点数加 1 考虑有 k 个节点的任意二叉树 T, 若 T 的根 v 的出度为 1, 则 T 与 T v 的叶子数和出度为 2 的节点数都相同, 而根据归纳假设,T v 的叶子数等于出度为 2 的节点数加 1, 因此这时命题成立 ; 若 T 的根 v 的出度为 2, 则 v 的左子树 T 1 和 v 的右子树 T 2 都是结点数小于 k 的二叉树, 设其叶子数分别为 n 01 和 n 02, 出度为 2 的节点数为 n 21 和 n 22, 则根据归纳假设有 : n 01 = n n 02 = n 也即 n 01 + n 02 = n 21 + n , 注意到这时 T 恰好有 n 01 + n 02 个叶子节点, 而有 n 21 + n 个出度为 2 的结点 ( 比 T v 多 v 这个出度为 2 的节点 ), 因此这时命题也成立二叉树的遍历是程序设计中常常遇到的一个问题, 数据课程中也常常研究二叉树的各种遍历方法我们这里以一个简单的例子说明二叉树的中序前序和后序遍历方法例子考虑下面的二叉树 : + 3 /

12 10 第二章树的基本概念对上述二叉树进行中序遍历则得到 : 3 + 7/3 5 2 当然这不加上括号不会得到正确的算术表达式, 加上适当括号则得到 (3 + 7/3) (5 3) 对上述二叉树进行后序遍历则得到 373/ + 52 对这个串作一遍扫描即可计算表达式的值对上述二叉树进行前序遍历则得到 + 3/73 52 同样也可利用这个串计算该表达式的值, 但不常用实际上, 二叉树的中序遍历常用于说明表达式的语法, 而后序遍历常用于计算表达式的值至于 m 元树, 我们可以按照上述方法将 m 元树转换为 2 元树再进行遍历如果直接遍历 m 元树, 从根节点出发, 有两种策略 : 一是先深搜索 : 先不断地搜索结点的儿子, 直到叶子结点, 再回溯到父亲结点, 再从该父亲结点的另外儿子开始继续策略 ; 二是先广搜索 : 先搜索所有儿子结点, 然后再根据一定的顺序 ( 从左到右 ) 选择一个儿子节点再继续搜索实际上, 上面的中序遍历采用的就是先深搜索策略, 而前序遍历采用的就是先广搜索策略对于一般的图 ( 有向图或无向图 ) 的遍历也可采用这两种策略 : 先深搜索是从一个结点开始不断搜索其相邻结点, 直到没有还未搜索过的相邻结点, 则回溯到上一结点继续搜索, 而先广搜索是先搜索一个结点的所有相邻结点, 然后选一个结点再继续搜索例子考虑下图的顶点遍历 ( 边的遍历与顶点遍历类似 ), 也即按照某种策略访问下图的所有顶点 : v 1 v 4 v 2 v5 v 3 v v 6 7 我们分别使用先深搜索策略和先广搜索策略从 v 1 开始遍历上图的所有顶点在遍历时, 我们总是使用序列 T 表示哪些顶点已经被遍历, 并假定我们用某种方式记住了顶点与顶点之间的相邻关系 ( 例如使用邻接矩阵 ), 因此我们总可很容易地得到某个顶点的相邻顶点读者可将序列 T 理解为一些元素的集合, 但这些元素有顺序以便给出我们遍历顶点的顺序

13 2.3 根树 11 为了使用先深策略, 我们还需要用一个栈 S 保存刚遍历过但还有相邻节点没有遍历的节点, 这里大家无需深究栈到底是什么东西, 你可将它理解为也是一个序列, 即其中元素有顺序的集合, 而且我们按照所谓的先进后出的策略访问其中的元素即可, 下面的遍历过程将展示我们如何使用和访问栈我们从 v 1 开始遍历, 因此开始时 T = v 1,S =, 这里用表示空序列下一步找到 v 1 的某个相邻顶点, 比如说 v 2 ( 当然 v 3 也可, 但那将得到一个不同的遍历顺序 ), 将 v 2 加入 T, 而因为 v 1 有相邻结点, 从而也将其加入 S( 按栈的术语称为压入栈 ), 得到 : T = v 1, v 2 S = v 1 再找 v 2 的相邻顶点 ( 当然是除 T 中顶点之外的相邻顶点 ), 比如说 v 4, 将 v 4 加入 T, 而将 v 2 压入栈 S, 得到 : T = v 1, v 2, v 4 S = v 1, v 2 再找 v 4 的除在 T 中顶点之外的相邻顶点, 上图只有 v 5, 加入 v 5 到 T, 而加入 v 4 压入栈 S 得到 : T = v 1, v 2, v 4, v 5 S = v 1, v 2, v 4 类似地, 下一步 v 5 在 T 中顶点之外的相邻顶点只有 v 6, 将 v 6 加入到 T, 而将 v 5 加入压入栈 S 得到 : T = v 1, v 2, v 4, v 5, v 6 S = v 1, v 2, v 4, v 5 好了, 对于 v 6, 它的所有相邻顶点都已经在 T 中 ( 也即 v 6 没有尚未访问的相邻顶点 ), 这时就需要回溯, 也即要返回到上一个我们访问过的节点, 这里就体现了栈的作用, 我们上一个访问的节点现在在 S 的最后 ( 按栈的术语就是在栈顶 ), 也即这时返回到 v 5 注意,v 5 是最后入栈的顶点, 而弹出的时候最先弹出, 这就是栈的所谓的后进先出的访问策略现在考虑 v 5, 注意到它也没有不在 T 中的相邻顶点, 那么它留在 S 中已经没有用了, 将其删除 ( 按栈的术语称为弹出 v 5 ), 则得到 : T = v 1, v 2, v 4, v 5, v 6 S = v 1, v 2, v 4 现在再考虑在栈顶的顶点 (S 的最后 )v 4, 同样它也没有不在 T 中的相邻顶点, 继续弹出 v 4, 得到 : T = v 1, v 2, v 4, v 5, v 6 S = v 1, v 2 现在再考虑在栈顶的顶点 v 2, 它还存在不在 T 中的相邻顶点 v 3, 因此得到 : T = v 1, v 2, v 4, v 5, v 6 S = v 1 现在再考虑刚弹出的 v 2, 它还存在不在 T 中的相邻顶点 v 3, 因此将 v 3 加入 T, 得到 : T = v 1, v 2, v 4, v 5, v 6, v 3 S = v 1 现在考虑 v 3, 由于它有不在 T 中的相邻顶点 v 7, 因此将 v 7 加入 T, 而将 v 3 压入栈 S, 得到 : T = v 1, v 2, v 4, v 5, v 6, v 3, v 7 S = v 1, v 3

14 12 第二章树的基本概念现在对于 v 7 也没有不在 T 中的相邻顶点, 因此再回溯到 v 3, 由于 v 3 已经没有不在 T 中的相邻顶点, 将 v 3 弹出 : T = v 1, v 2, v 4, v 5, v 6, v 3, v 7 S = v 1 这时栈顶的顶点 v 1 也没有不在 T 中的相邻顶点, 再将 v 1 弹出好了, 现在栈空了, 表明我们整个遍历的过程就结束了, 而顶点的访问顺序就在 T 中若使用先广策略, 则除了用 T 记住遍历结点的顺序之外, 这回使用队列 Q 来帮助我们, 实际上队列也是一个序列, 只是我们采用与栈不同的访问策略访问其中的元素, 即使用先进先出的策略访问队列从 v 1 开始遍历, 同样将 v 1 加入到 T, 同样将 v 1 加入到 Q, 得到 : T = v 1 Q = v 1 下一步我们考虑 Q 的最前面顶点 v 1, 将 v 1 的所有 ( 不在 T 中的 ) 相邻顶点 v 2, v 3 加入到 T( 即表示 v 1 的所有相邻顶点都已经访问 ), 同时在 Q 中删除 v 1 (v 1 出队列 ), 而将 v 2, v 3 加入到 Q( 入队列 ), 得到 : T = v 1, v 2, v 3 Q = v 2, v 3 继续考虑 Q 的最前面顶点 v 2, 将 v 2 的所有 ( 不在 T 中的 ) 相邻顶点 v 4, v 6 加入到 T 和 Q, 同时删除 v 2, 得到 : T = v 1, v 2, v 3, v 4, v 6 Q = v 3, v 4, v 6 注意将 v 4 和 v 6 加入 Q 时是加入 ( 入队列 ) 到 Q 的尾部, 而删除 ( 出队列 ) 的 v 2 是在 Q 的最前面顶点, 这就是队列的所谓先进先出访问策略 (v 2 是先入队列的顶点, 因此也是最先出队列的顶点 ) 继续考虑 Q 的最前面顶点 v 3, 将 v 3 的所有不在 T 中的相邻顶点 v 7 加入 T 和 Q, 并在 Q 中删除 v 3, 得到 : T = v 1, v 2, v 3, v 4, v 6, v 7 Q = v 4, v 6, v 7 继续考虑 Q 的最前面顶点 v 4, 将 v 4 的所有不在 T 中的相邻顶点 v 5 加入 T 和 Q, 并在 Q 中删除 v 4, 得到 : T = v 1, v 2, v 3, v 4, v 6, v 7, v 5 Q = v 6, v 7, v 5 继续考虑 RQ 的最前面顶点 v 6, 它没有不在 T 中的相邻顶点, 直接在 Q 中删除, 得到 : T = v 1, v 2, v 3, v 4, v 6, v 5 Q = v 7, v 5 继续考虑 RQ 的最前面顶点 v 7, 它也没有不在 T 中的相邻顶点, 直接在 Q 中删除, 得到 : T = v 1, v 2, v 3, v 4, v 6, v 5 Q = v 5 继续考虑 RQ 的最前面顶点 v 5, 它也没有不在 T 中的相邻顶点, 直接在 Q 中删除, 得到了空队列, 这表明所有的顶点已经访问到, 遍历过程结束, 而节点的遍历顺序也在 T 中练习读者应通过上述例子理解先深搜索和先广搜索的区别, 并将上述例子中描述的方法提炼为一般的方法, 并自己画一个图进行先深搜索和先广搜索进一步, 读者可通过这里例子, 理解栈和队列的区别, 为以后的数据课程学习打下基础

15 2.4 哈夫曼树哈夫曼树这一章的最后, 我们利用一种特殊的根树, 即所谓的哈夫曼 (Huffman) 树考虑一类实际问题的解决假定现在要在网络传送许多英文文件, 需要对文件的内容进行编码我们知道, 对于英文而言, 不是每个字母都是等概率出现的, 例如 c, e 这些字母通常出现得最多, 而 z, x 这些字母则出现得很少, 所以如果我们都用同样长的二进制编码所有的英文字母, 那么对文件编码得到二进制文件长度就不是最优的为简单起见, 假设我们要传送的文件中只含有 a, b, c, d, e, f, g, h 等八个字母, 每个字母在文件中出现的概率分别为 : a : 15% b : 12% c : 25% d : 8% e : 20% f : 6% g : 8% h : 6% 如果我们使用相同长度的二进制对这八个字母进行编码, 那么每个字母需要三位二进制, 从而若要传送长度为 1 万个字母的英文文件, 那么总共要传送 3 万个二进制数下面我们利用 Huffman 树对这八个字母做一种不等长的编码, 使得当要传送 1 万个字母时, 传送的二进制数可以少于 3 万, 从而节省了网络传送的费用为此, 我们先引入有关概念定义给定有 k 个叶子节点的二元树 T = (V, E), 若 k 个叶子分别赋以非负实数权 w 1, w 2,, w k, 并设这 k 个叶子对应的高度分别是 l 1, l 2,, l k, 则称 w(t ) = k l i w i i=1 为二元树 T 的带权外部通路总长称在有 k 个叶子节点并分别赋以非负实数权的二元树中, 具有最小的带权外部通路总长的二元数为最优二元树回到前面的问题, 我们将要编码的字母看作二元树的叶子, 字母在文件中出现的概率作为赋予叶子的权, 通过构造一个最优二元树可以确定这些字母的一个比较节省网络传送费用的二进制编码方案 Huffman 给出了一个构造最优二元树的算法, 从而我们将利用 Huffman 算法构造出来的最优二元树称为 Huffman 树例子我们利用上面的例子来说明 Huffman 算法的基本思想首先将字母的权从小到大排序 ( 省略百分比, 实际上,Huffman 算法对于权也没有特别的要求, 只要非负即可 ): 6(f) 6(h) 8(g) 8(d) 12(b) 15(a) 20(e) 25(c) 然后我们开始构造二元树取所有权中最小的两个权, 以这两个权所对应的字母作为儿子, 新添加一个节点 t 1 作为根, 得到一个子树 ( 注意, 我们特意用方框表示叶子节点, 而用园框表示分支节点 ): f t 1 h

16 14 第二章树的基本概念为了便于后面的构造, 我们令 t 1 的赋为它的两个儿子节点的权的和, 即为 12, 而且在上面的权序列中, 将 f 和 g 的权删除, 而将 t 1 的权加入, 并仍保持从小到大排序, 即得到如下的权序列 : 8(g) 8(d) 12(t 1 ) 12(b) 15(a) 20(e) 25(c) 下一步跟前面类似, 我们再选两个权最小的字母 g 和 d 作为儿子, 并新添加一个节点 t 2 作为根, 得到一个子树 ( 为清楚起见, 我们将先前构造的树 t 1 也画在下面 ): t 1 t 2 f h g d 同样地, 在权序列中删除 g 和 d 的权, 并令 t 2 的权为它们的和 ( 即 16), 并加入到权序列, 保持从小到大的序, 即得到 : 12(t 1 ) 12(b) 15(a) 16(t 2 ) 20(e) 25(c) 这时权最小的是 t 1 和 b 的权, 也没有关系, 我们将 t 1 看作一个单独的字母好了, 取这两个权对应的节点 ( 这时称节点更为恰当了 ) 作为儿子, 添加一个新节点 t 3 作为根, 也就是说, 现在我们得到如下的树 ( 准确地说, 是森林 ) 注意, 以 t 3 是以 t 1 作为左儿子还是以 b 作为左儿子没有什么关系, 随便选择即可, 下面为了画图的方便, 选择 t 1 作为左儿子 : t 3 t 1 b t 2 f h g d 同样地, 在权序列中删除 t 1 和 b 的权, 并令 t 3 的权为它们的和 ( 即 24), 并加入到权序列, 保持从小到大的序, 即得到 : 15(a) 16(t 2 ) 20(e) 24(t 3 ) 25(c) 继续选择两个最小的权对应的节点 ( 即 a 和 t 2 ) 作为儿子, 添加一个新节点 t 4 作为根, 也就是说, 得到如下的森林 : t 3 t 4 t 1 b t 2 a f h g d

17 2.4 哈夫曼树 15 删除 a 和 t 2 对应的权, 加入 t 4 对应的权 ( 即 a 和 t 2 的权之和 31), 并保持权序列的从小到大顺序得到 : 20(e) 24(t 3 ) 25(c) 31(t 4 ) 继续选择两个最小的权对应的节点 ( 即 e 和 t 3 ) 作为儿子, 添加新节点 t 5 作为根, 得到如下森林 : t 5 t 3 e t 4 t 1 b t 2 a f h g d 删除 e 和 t 3 对应的权, 加入 t 5 对应的权 ( 即 e 和 t 3 的权之和 44), 保持权序列的从小到大顺序得到 : 25(c) 31(t 4 ) 44(t 5 ) 构造一个新的节点 t 6, 以 c 和 t 4 对应的节点作为儿子, 得到 : t 5 t 6 t 3 e c t 4 t 1 b t 2 a f h g d 删除 c 和 t 4 对应的权, 加入 t 6 对应的权 ( 即 c 和 t 4 对应的权之和 56), 保持权序列的从小到大顺序得到 : 44(t 5 ) 56(t 6 ) 构造一个新的节点 t 7, 以 t 5 和 t 6 对应的节点作为儿子, 得到 :

18 16 第二章树的基本概念 t 7 t 5 t 6 t 3 e c t 4 t 1 b t 2 a f h g d 在权序列中删除 t 5 和 t 6 对应的权之后, 再加入 t 7 对应的权 ( 即 t 5 和 t 6 的权之和 100) 后得到的权序列中只有一个节点 ( 即 t 7 ), 这表明我们的最优二元树的构造已经完成但要注意, 这个最优二元树 T 的外部通路总长并不是 t 7 的权, 而是 : w(t ) = = 283 练习根据上述例子的描述, 抽象出 Huffman 算法的一般描述 ( 或者说, 根据这个例子, 理解戴一奇教材 p57 页对 Huffman 算法的描述 ) 定理由 Huffman 算法得到的二元树是最优二元树证明参见戴一奇教材 [3]p58 页的定理例子继续上面的例子, 根据上面构造得到的 Huffman 树, 我们可以对要传送的字母 a, b, c, d, e, f, g, h 进行编码编码方法很简单, 对树的每一条边赋一个二进制数 : 如果某条边是从父亲节点连向左儿子节点, 则赋二进制数 0; 如果是从父亲节点连向右儿子节点, 则赋二进制数 1 对于上面的 Huffman 树, 我们得到 : t t 5 t t 3 e c t t 1 b t a 0 f h g d

19 2.4 哈夫曼树 17 我们令每个叶子节点对应的字母的编码就是从根节点到该叶子节点所经过的边上的二进制数构成的串, 也即得到 : a 的编码是 : 111 b 的编码是 : 001 c 的编码是 : 10 d 的编码是 : 1101 e 的编码是 : 01 f 的编码是 : 0000 g 的编码是 : 1100 h 的编码是 : 0001 与前面所给出的每个字母的出现频率相比较, 不难发现, 出现频率越高的字母的编码越短因此, 如果传送具有 1 万个字母的英文文件, 该文件只出现这 8 个字母, 而且每个字母出现的概率正如上面所给出的那样, 也就是说, 在 1 万个字母中,a 大概出现 15%, 也即 1500 个,b 大概出现 12%, 也即 1200 个等等, 那么传送这 1 万个字母英文文件需要传送的二进制编码数目是 : W = = w(t ) 10000/100 = 比使用等长的三位编码要传送的二进制数 3 万要少 1700 个要使用不等长的二进制编码进行传输, 我们还需要解决一个问题, 即传送信息的分割, 也即那几个二进制位是代表一个字符很显然如果使用等长编码的话, 例如 3 位编码, 那么文件接受方在接受到数据之后, 每三位三位进行译码即可, 但如果是使用不等长的编码进行传送, 那么接受方接收到数据之后该如何译码呢? 也就是说, 我们需要一个能够正确分割接收到的信息并进行译码的方法解决这个问题的方法就是让对要传送的字符的编码满足前缀码的要求定义设 a 1 a 2 a n 是长度为 n 的串, 我们称其子串 a 1, a 1 a 2, a 1 a 2 a 3,, a 1 a 2 a n 1 分别为该符号串长度为 1, 2, 3,, n 1 的前缀也就是说, 符号串 β 是符号串 α 的前缀, 当且仅当 β 是 α 的从第一个字符开始的子符号串定义设 A = {β 1, β 2,, β n } 是一些符号串构成的集合, 如果 A 满足, 对任意的 i j, 1 i, j n, 都有 β i 不是 β j 的前缀, 也即 A 中的任意两个符号串都不互为前缀, 则称 A 是前缀码进一步, 若前缀码 A 中任意的串 β i 都只有两种符号构成, 则称 A 是二元前缀码例子对于串 , 其前缀有 1, 11, 110, 1100, 等等, 而虽然是它的子串, 但不是它的前缀下面的符号串集合不是前缀码 : A = {11, 100, 1101, 001, 0100, 0111, 0011} 因为其中 11 是 1101 的前缀,001 是 0011 的前缀而我们前面根据 Huffman 树得到的编码集 ( 符号串集 ) H = {111(a), 001(b), 10(c), 1101(d), 01(e), 0000(f), 1100(g), 0001(h)} 就是前缀码一般地, 如果按照上面的编码方法, 即将连向左儿子的边编码为 0, 右儿子的边编码为 0, 叶子结点的编码为根到该叶子结点的路径上的二进制串, 那么任意一棵二元树的叶子结点的编码构成的集合一定是前缀码, 因为根到任何叶子结点的路径都是惟一的, 绝不会是根到另外一个叶子结点的一部分

20 18 第二章树的基本概念对于二元前缀码, 由于任何一个码都不是另外一个码的前缀, 从而对于一些字母的编码, 如果传送正确的话, 那么在接收方都能正确地译码, 例如我们要传送的字符串是 faceaddheadgeaf, 根据上面的编码我们要传送如下的二进制串 : 接收方只要知道每个字母的编码, 就能正确地将上述二进制串翻译回英文字符串例如, 看到第一个二进制 0 时, 那么可能的字符是 b, e, f, h, 再看到下一个 0 时, 可能的字符只有 b, f, h, 再看到一个 0, 可能的字符剩下 f, h, 再看到一个 0, 就只有 f 了, 而且由于 0000 不会是任何其他字符编码的前缀, 因此 0000 只可能译码成 f 如果用于编码字符的不是前缀码, 那么就无法正确分割信息并进行译码, 例如, 若利用上述编码集 A 进行编码, 传送如下的二进制串 : 那么当接收方接收到 11 时, 它不知道是将分割成呢, 还是分割成 , 而使用前缀码进行编码则只可能存在惟一的一种分割方式作业作业 2.1 设无向简单图 G 是由 k(k 2) 棵树构成的森林, 已知 G 有 n 个顶点,m 条边, 证明 m = n k 作业 2.2 设无向简单图 G 有 n 个顶点,n 1 条边, 则 G 为树这个命题正确吗? 为什么? 作业 2.3 设无向简单图 G 有 n 个顶点,n 1 条边, 则 G 是连通当且仅当 G 无回路作业 2.4 已知无向树 T 有三个 3 度顶点, 一个 2 度顶点, 其余都是 1 度顶点 (1) T 有几个叶子节点?(2) 画出两棵满足上述度数要求的非同构的无向树作业 2.5 一棵无向树有 n i 个顶点的度数为 i,i = 1, 2,, k 如果已知 n 2, n 3,, n k, 试问 n 1 应为多少? 作业 2.6 设 T 是一棵非平凡的无向树, (T ) k, 证明 :T 至少含有 k 片树叶作业 2.7 设 d 1, d 2,, d n 是 n 个正整数,n 2, 若 n i=1 d i = 2n 2, 证明存在一棵顶点度数分别为 d 1, d 2,, d n 的无向树作业 2.8 给出下面无向图 G 和有向图 D 的关联矩阵 : e 1 v 1 v 2 v 1 e 1 v 2 e 4 e 6 e 3 e 2 e 4 e 3 e 2 v 4 v v 4 e 5 3 e 5 v 3

21 2.4 哈夫曼树 19 作业 2.9 求下面两个图的所有生成树, 它们各有几棵非同构的生成树? v 1 v 2 v 1 v3 v 5 v 2 v 4 v 3 v 4 作业 2.10 求下图的所有生成树 a b c d 作业 2.11 求下面有向图的所有生成树 : e 2 e 1 e3 e 4 e 5 e 6 作业 2.12 下图实线给出了它的一棵生成树, 请给出该图关于此生成树的基本割集系统和基本回路系统 e 1 e 4 e 6 e 5 e 3 e 2 作业 2.13 下图实线给出了它的一棵生成树, 请给出该图关于此生成树的基本割集系统和基本回路系统 a b e i c d h f j d

22 20 第二章树的基本概念作业 2.14 有向图 D 仅有一个顶点入度为 0, 其余顶点的入度都是 1,D 一定是有向树吗? 作业 2.15 对于下面根树 T: A B C D E F G H I J K L M (1) 给出它所有的根节点树叶节点分支节点内点 ; (2) 给出每个节点的父节点子节点 ; (3) 给出每个节点的层 ; (4) 给出树高和最大出度 ; (5) 给出所有子 ( 根 ) 树 ; (6) 给出它的中序前序和后序遍历结果作业 2.16 设 T 是一棵二元正则树,m 是其边数,t 是树叶数且 t 2, 证明 :m = 2t 2 作业 2.17 设 T 是一棵 r 元正则树,i 是 T 的分支点数,t 是树叶数, 证明 :(r 1)i = t 1 作业 2.18 设 T 是一棵高为 h 的 r 元正则树,t 是树叶数, 证明 :r + (r 1)(h 1) t r h 作业 2.19 请给出下面二叉树的中序前序和后序遍历结果 v 0 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9

23 2.4 哈夫曼树 21 作业 2.20 给出表达式 : 的波兰符号法和逆波兰符号法表示 ((a + (b c) d) e) (f + g) + (h i) j 作业 2.21 下面给出的三个符号串集中, 哪些是前缀码, 哪些不是? 为什么? (1) B 1 = {0, 10, 110, 1111} (2) B 2 = {1, 01, 001, 000} (3) B 3 = {1, 11, 101, 0001, 0011} 作业 2.22 求带权为 2, 3, 5, 7, 8 的最优二叉树, 并写出其对应的二元前缀码作业 2.23 在通信中要传输八进制数字 0, 1, 2, 3, 4, 5, 6, 7, 这些数字出现的频率分别是 : 0 : 30% 1 : 20% 2 : 15% 3 : 10% 4 : 10% 5 : 6% 6 : 5% 7 : 4% 编一个最佳前缀码, 使通信中出现的二进制数字尽可能少 : (1) 画出相应的二叉树 ; (2) 写出每个数字对应的前缀码 ; (3) 传输按上述比例出现的数字个时, 至少要用多少个二进制数字?

24 22 第二章树的基本概念

25 参考文献 [1] 耿素云. 集合论与图论离散数学第二分册. 北京大学出版社, 1998 年 2 月. [2] G. Chartrand and Zhang Ping. Introduction to Graph Theory. McGraw-Hill Companies, Inc., 图论导引 ( 英文影印版 ), 人民邮电出版社,2006 年 6 月第一版. [3] 戴一奇, 胡冠章, 陈卫. 图论与代数结构. 清华大学出版社, [4] 耿素云屈婉玲. 离散数学 ( 修订版 ). 高等教育出版社, 2004 年 1 月. 23

Microsoft Word - 专升本练习5：图.doc

Microsoft Word - 专升本练习5：图.doc 第五章图一选择题 1. 关键路径是事件结点网络中的 ( ) A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路 2. 一个具有 n 个顶点和 e 条边的无向图, 采用邻接表表示, 表向量的大小为 ( 1 ), 所有顶点邻接表的结点总数为 ( 2 ) 1A. n B. n+1 C. n-1 D. n+e 2A. e/2 B. e C. 2e D. n+e