WonderU
离散数学

10.树

1.树

无向树

  • 无向树：连通无回路的无向图
  • 树叶：度数等于 11 的顶点
  • 分支点：度数大于等于 22 的顶点

树的性质

  • 设 G=<V,E>G=< V, E> 是 nn 阶 mm 条边的无向图，则下面命题互相等价：

    • GG 是树
    • GG 中任意两个顶点之间存在唯一的路径
    • GG 是无回路且 m=n−1m=n-1
    • GG 是连通的且 m=n−1m=n-1

  • 设 TT 是 nn 阶非平凡的无向树，则 TT 中至少有 22 片树叶。

    • 例1：无向简单图G是棵树，当且仅当 A‾\underline{A}

      • A. G 连通并且边数比节点数少1
      • B . G 连通并且节点数比边数少1
      • C . G 的边数比节点数少1
      • D . G 中没有回路

    • 例2：边数等于节点数减1的无向图是树 ×‾\underline{\times}

    • 例3：设GG是5个顶点的完全图，则从 G 中删除 C‾\underline{C} 条边可以得到树
      A.4 B.5 C. 6 D. 10

    • 例4：一棵树有2个2度顶点，1个3度顶点 和3个4度顶点，则1度顶点数为 99
      解：任何无向图中，所有顶点的度数之和等于边数的2倍。
      设1度顶点数为 tt，
      则 1×t+2×2+1×3+3×4=2(t+2+1+3−1)1 \times t+2 \times 2+1 \times 3+3 \times 4=2(t+2+1+3-1)
      解得 t=9t=9

最小生成树

  1. 子图：设 G=<V,E>G=< V, E>，G′=<V′,E′>G'=< V', E'>，若 V′⊆VV' \subseteq V，E′⊆EE' \subseteq E 则称 G′G' 为GG的子图。若 V′=VV'=V 则称 G′G' 为 GG 的生成子图。
  2. 生成树：如果无向图 GG 的生成子图 TT 是树，则称TT是 GG 的生成树。
  3. 生成树的权：无向连通带权图 G=<V,E,W>G=< V, E, W>，TT是G的一颗生成树，TT 的各边权之和称为TT的权，记作 W(T)W(T)。
  4. 无向图 GG 有生成树当且仅当GG是连通图。
  5. 最小生成树：G的所有生成树中权最小的生成树。
    • 例：设赋权无向连通图GG如下，求 G 的最小生成树，并求该最小生成树的权总和。
      • step1: 给权排序: 1,2,3,3,4,5,5,5,6,61,2,3,3,4,5,5,5,6,6
      • step2: 描点，将边数置零
      • step3: 选边(权最小，且不构成回路)
      • step4: 一直重复第三步，直到边数 = 顶点数−1−1，结束。
        得：W(T)=1+2+3+3+5=14W(T)=1+2+3+3+5=14

2.根

  • 有向树：若有向图的基图是无向树，则称这个有向图是有向树。
  • 根树：一个顶点的入度是00，其余顶点的入度为11的有向树。
  • 层数：从树根到顶点的路径的长度(即路径中的边数)。
    在画根树时，通常会把树根画在最上方，有向边的方向向下或者斜下方，并省去各边上的箭头。 若TT的每个分支点至多有rr个儿子，则称TT为rr叉树。

最优二元树

  • 最优二叉树：权最小的二叉树。
    W(T)=∑i=1tWil(Vi)W(T)=\sum_{i=1}^{t} W_{i} l\left(V_{i}\right) 即：每个元素 ×\times 它的层数的和。

    • 例：用Huffman算法，计算一组权为2,3,5,7,11,13,172,3,5,7,11,13,17的最优二叉树，并求它们的权值。

      • step1: 给权排序
      • step2: 选出2个权最小的顶点，添加新点，权为两点之和
      • step3: 重复step1、2，直到只有1个顶点。 W(T)=∑i=1tWi l(Vi)=2×5+3×5+5×4+7×3+11×2+13×2+17×2=148W(T)=\sum _{i=1}^{t}W_{i}\, l(V_{i})=2\times 5+3\times 5+5\times 4+7\times 3+11\times 2+13\times 2+17\times 2=148

    • 例：某字符串如下：AABBCCCDDEEECCCCDDDDDAAABBBDDDEEEEECCDDEEEEAABBBEEEE，请为该字符串设计哈夫曼编码，要求画出哈夫曼树构建过程。
      解：字符串A、B、C、D、E出现的次数分别是7,8,9,12,167,8,9,12,16次，以此作为权值构建哈夫曼树。 由图可设计各字符编码：A:000, B:001, C:01, D:10, E:11\boldsymbol{A: 000,\ B: 001,\ C: 01,\ D: 10,\ E: 11}

  • 2元前缀码：0−10-1符号串构成的前缀码。

  • 最佳前缀码：由最优二叉树产生的前缀码。

    • 例：下面给出的符号串集合中，构成前缀码的是 C‾\underline{C}

      • A. {b, c, aa, ac, aba, abb, aaa}\{b,\ c,\ aa,\ ac,\ aba,\ abb,\ aaa\}
      • B. {b, c, a, aa, ac, aba, abb, abc}\{b,\ c,\ a,\ aa,\ ac,\ aba,\ abb,\ abc\}
      • C. {b, c, aa, ac, aba, abb, adc}\{b,\ c,\ aa,\ ac,\ aba,\ abb,\ adc\}
      • D. {b, c, aa, ac, aba, abb, aac}\{b,\ c,\ aa,\ ac,\ aba,\ abb,\ aac\}

    • 例：在通信中，设八进制数字出现的频率(%)如下：
      0:25, 1:20, 2:15, 3:10, 4:10, 5:10, 6:5, 7:50: 25,\ 1: 20,\ 2: 15,\ 3: 10,\ 4: 10,\ 5: 10,\ 6: 5,\ 7: 5
      采用2元前缀码，求传输数字最少的2元前缀码，画出最优二叉树，
      并求传输 10n10^{n} 个按上述比例出现的八进制数字需要多少个二进制数字？
      若用等长的(长为3)的码字传输需要多少个二进制数字？
      解：用100乘各频率为权，用Huffman算法求最优二叉树。 最优前缀码为：
      0101传00，
      1111传11，
      001001传22，
      100100传33，
      101101传44，
      00010001传55，
      0000000000传66，
      0000100001传77。
      W(T)=10+20+35+60+100+40+20=285W ( T ) = 1 0 + 2 0 + 3 5 + 6 0 + 1 0 0 + 4 0 + 2 0 = 2 8 5
      10n−2×285=2.85×10n10^{n-2} × 285=2.85 × 10^{n}，等长编码需要 3×10n3 × 10^{n}。

← 返回 Note