AbabCatのblog

• 树必不含多重边和自环,故是简单图
• 边称为 树枝
• 度为1的结点称为 树叶(leaf) 或 悬挂点
• 度大于等于2的结点称为 分叉点

• 林可能不是连通的
• 林的每个连通支都是树

• 删去 $e=(u,v)$,则u,v分属于不同的连通支

• 证明:
  • 若e属于某回路,则 $G^{\prime}=G-e$ 中仍有从u到v的道路,故u,v属于同一连通支,与e是割边矛盾。
  • 若 $e=(u,v)$ 不是割边,则 $G^{\prime}=G-e$ 中与G的连通支数一样,故u, v属于同一连通支,有从u到v的道路,连通e即构成回路,矛盾。

定理2: 设T是结点数 $n\ge2$ 的树,则下列性质互相等价

• (1) T连通且无回路
• (2) T的任意两结点间有唯一道路
• (3) T有 $n-1$ 条边且无回路
• (4) T连通且有 $n-1$ 条边
• (5) T连通且每条边都是割边(极小连通)
• (6) T无回路,但任意增加一边后恰有一个回路(极大无回)

树是边数最少的连通图,也是边数最多的无回路图。

满足连通,无回路,有n-1条边之任意两条者是树。

证明 (1) -> (2):

• 树T是连通的,T中任意两结点u和v间存在路径。
• 如果两结点u和v间有存在的路径不唯一,则树T中必然会有回路。

证明 (2) -> (3):

• 任意两结点间存在唯一道路,可知图T中无回路。
• 证明T中边数 $m=n-1$。
• 当 $n=2$ 时,命题成立。
• 设当 $n\le k$ 时,命题成立,即T中的边数为 $m=k-1$。
• 当 $n=k+1$ 时,任选T中的一条边e,T-e有两个连通分支, 其中结点数为 $n_{1}$ 和 $n_{2}$。其中的边数分别为 $n_{1}-1$ 和 $n_{2}-1$。
• 所以当 $n=k+1$ 时, $m=(n_{1}-1)+(n_{2}-1)+1 = (n_1+n_2)-2+1 = n-1$。

证明 (3) -> (4):

• 证明T连通: 假设T中存在s个连通分支,每个连通分支都是树, 所以T中的边m有:
• $m=m_{1}+m_{2}+...+m_{s}$
• $=(n_{1}-1)+(n_{2}-1)+...+(n_{s}-1)$
• $=(n_1+n_2+...+n_s) - s = n-s$
• 已知 $m=n-1$, 所以 $n-1 = n-s$, 可知 $s=1$,即T是连通的。

证明 (4) -> (5):

• 证明极小连通,即T中任何一条边都是割边。
• 任选T中的一条边e, T-e中有n个结点和 $n-2$ 条边。
• 一个有 $n$ 个结点, $n-2$ 条边的图肯定不连通 (因为连通图至少 $n-1$ 条边), 因此e是割边。

证明 (5) -> (6):

• T是极小连通, T中不存在回路 (若有回路, 回路上的边都不是割边, 矛盾), 且任意两结点u和v间存在唯一路径 $\Gamma$。
• 则有 $\Gamma+(u,v)$ 是T中增加边(u,v)后的唯一回路。

证明 (6) -> (1):

• 证明T连通。
• T中任意两结点u和v, 若它们不相邻, $T+(u,v)$ 有唯一回路C。
• 令 $C-(u,v)=\Gamma$, 则有 $\Gamma$ 是两结点u和v间存在的一条路径。
• 若T不连通，则存在两点u, v在不同连通支，它们之间没有路径。增加边(u,v)后，(u,v)是割边，不会形成回路。这与(6)中“任意增加一边后恰有一个回路”矛盾。
• 所以可知T连通。

• (1) 证法1: 若各结点度都 $\ge2$,则总度数 $\sum d(v) \ge 2n$。而 $\sum d(v) = 2m = 2(n-1)$。 $2n \le 2(n-1)$ 即 $2n \le 2n-2$ 矛盾。
• (2) 证法2: 考虑从任一结点,出发沿边前进,走过的边不重复, (因为无回路)则必止步于某树叶。

• 同上面证法2,考虑从一树叶出发前进,必止步于另一个树叶。

• 记为 $\overline{T}=G-T$
• 余树不一定是树。

• (1) 对n个权值排序,得到 $w_{i_{1}}\le w_{i_{2}}\le...\le w_{i_{n}}$。
• (2) 计算 $w_{i}=w_{i_{1}}+w_{i_{2}}$ 作为中间结点 $v_{i}$ 的权; $v_{i}$ 的左子结点是 $v_{i_{1}}$,右子结点是 $v_{i_{2}}$。
• 在权序列中删去 $w_{i_{1}}$ 和 $w_{i_{2}}$,加入 $w_{i}$。
• $n\leftarrow n-1$,若 $n=1$,结束;否则转(1)。

• 算法的计算复杂度主要取决于步骤(1),n个权值的第一次排序需要进行 $n \log n$ 次比较。总共进行n-2次迭代,算法的计算复杂性是 $O(n \log n)$。

• 权最小的树叶离根最远。
• 权最小的树叶必有兄弟。

• $T\leftarrow\emptyset$;
• WHILE $|T|<n-1$ AND $E\ne\emptyset$ DO
  • BEGIN
    • $e\leftarrow E$ 中最短边;
    • $E\leftarrow E-e$;
    • 若 $T+e$ 无回路,则 $T\leftarrow T+e$;
  • END
• IF $|T|<n-1$ THEN打印“非连通”
• ELSE 输出最短树 T

• 证明 (必要性 $\Rightarrow$): 若有余树边满足 $w(e)<w(a), a\in C^{e}$,则以e换a得到的树T’比T更短,与T是最短树矛盾。
• 证明 (充分性 $\Leftarrow$): 对不同于T的支撑树T’,有 $T^{\prime}-T\ne\emptyset$, $\forall e\in T^{\prime}-T$, $T+e$ 中有回路 $C^{e}$; 据已知条件,对 $\forall a\in C^{e}\cap T$ 有 $w(e)\ge w(a)$, 则易证 $w(T^{\prime})\ge w(T)$。

• $T\leftarrow\emptyset$; $U\leftarrow\{v_{1}\}$ (任选 $v_1$);
• WHILE $U\ne V$ DO
  • BEGIN
  • $w(t,u) = \min_{v \in V-U}\{w(t,v)\}$;
  • $T \leftarrow T + e(t, u)$;
  • $U \leftarrow U + u$;
  • FOR $v \in V-U$ DO
    • $w(t,v) \leftarrow \min\{w(t,v), w(u,v)\}$
  • END

• 证明: 令 $T_{0}$ 为一最短树。假设 $e\notin T_{0} \Rightarrow T_{0}+e$ 构成唯一回路。回路包含e和 $e^{\prime}=(u,v)\in T_{0}$,其中 $u\in V^{\prime}$, $v\in V-V^{\prime}$。由已知, $w(e)\le w(e^{\prime})$。 $T_{0}\oplus(e,e^{\prime})$ (即 $T_0 - e' + e$) 也是支撑树, 且其权不大于 $T_0$。故它也是最短树。

• 最短树不唯一。
• 最小权和唯一。