1. 第十章 有向图

1.1. 10.5 有向树与有序树

1.1.1. 8.

令 $T$ 是一个正则二元树，它有 $i$ 个内顶点（出度为 $2$ 的顶点）。如果 $E$ 为所有内顶点深度之和， $I$ 为所有叶节点的深度之和，证明：

$$I = E + 2i$$

证明：

设 $T$ 有 $p$ 个顶点，施归纳于 $p$ :

• $p = 1$ 时， $I = E = i = 0$ 。
• $p \neq 2$ 。
• $p = 3$ 时， $I = 2$ ， $E = 0$ ， $i = 1$ ，结论成立。

假设节点数小于 $p$ 时成立，往证节点数为 $p$ 时也成立：

若去掉根节点及其边，产生的两棵子树节点树均小于 $p$ ，符合归纳假设。设这两棵子树满足：

$$I_1 = E_1 + 2 i_1 \tag{1}$$ $$I_2 = E_2 + 2 i_2 \tag{2}$$

加回根节点后，两棵子树所有节点深度均加 $1$ 。故：

$$I = I_1 + I_2 + (p - i_1 - i_2 - 1)$$ $$E = E_1 + E_2 + i_1 + i_2$$ $$i = i_1 + i_2 + 1$$

仅证需证明 $I_1 + I_2 + (p - i_1 - i_2 - 1) = E_1 + E_2 + i_1 + i_2 + 2 (i_1 + i_2 + 1)$

由 $(1)$ 式和 $(2)$ 式，化简得 $p = 2(i_1 + i_2 + 1) + 1$ ，即 $p = 2i + 1$ ，由于 $T$ 是正则二元树，此式显然成立，故结论成立。【证毕】

1.1.2. 9.

令 $T$ 是一个正则 $m$ 元树，它有 $i$ 个内顶点（出度为 $m$ 的顶点）。如果 $E$ 为所有内顶点深度之和， $I$ 为所有叶节点的深度之和，证明：

$$I = (m-1)E + mi$$