
%%TEXT_BEGIN%%
在各种各样的图中, 有一类简单但是很重要的图, 那就是"树". 树之所以重要, 不仅仅因为它在众多领域有着广泛的应用, 更在于图论本身.
因为树是非常简单的图,所以在讨论关于图的一般性结论或猜想时, 可从先考虑树这种情形.
先引人几个概念.
在图 $G$ 中,一个由不同的边组成的序列:
$$
e_1, e_2, \cdots, e_m .
$$
如果其中边 $e_i=\left(v_{i-1}, v_i\right), i=1,2, \cdots, m$. 则称这个序列是从 $v_0$ 到 $v_m$ 的链.
数 $m$ 称为这条链的长.
$v_0$ 与 $v_m$ 称为这条链的端点.
并且这条链记为 $v_0 v_1 \cdots v_m$.
如果一条链的两个端点 $v_0$ 与 $v_m$ 重合, 称这条链为圈 ${ }^*$.
如图(<FilePath:./figures/fig-c4i1.png>) 中, $e_1, e_2, e_3, e_4, e_5$ 组成一条链, $e_1, e_2, e_3$ 组成一个圈.
如果图 $G$ 中的任意两个顶点 $u$ 与 $v$, 都有一条从 $u$ 到 $v$ 的链, 称这样的图 $G$ 为连通图.
不是连通的图称为不连通图.
如图(<FilePath:./figures/fig-c4i1.png>) 中的图是连通图.
如图(<FilePath:./figures/fig-c4i2.png>) 中的图是不连通图.
本书所指的 "圈" 实为 "闭链". 与通常图论书中的 "圈"有别.
图论中的圈是指: 在 "闭链" $v_0 v_1 \cdots v_m\left(v_0=v_m\right)$ 中, 点 $v_1, v_2, \cdots, v_m$ 互不相同.
现在给出树的定义.
一个连通且没有圈的图称为树.
通常用字母 $T$ 来表示树.
根据树的定义, 树显然是简单图.
如图(<FilePath:./figures/fig-c4i3.png>) 是一个有 8 个顶点的树.
显然,一个不含圈的图必定是由一个或数个顶点不交的树所组成的.
我们称这样的图为森林.
如图(<FilePath:./figures/fig-c4i4.png>) 所示是一个森林, 它由 3 个树组成.
度为 1 的顶点称为悬挂点 (或树叶).
定理一如果树 $T$ 的顶点数 $\geqslant 2$, 则 $T$ 中至少有两个悬挂点.
证法一设想我们从某个顶点 $u$ 出发, 沿着 $T$ 的边走, 已经走过的边不再重复.
由于树是没有圈的, 因此不会回到已经走过的点, 也就是说每个顶点至多走一次.
如果我们走到的一个点不是悬挂点, 由于这个点的度大于 1 , 还可以继续走下去.
但 $T$ 的顶点个数是有限的, 所以不可能永远走下去.
如果在顶点 $v$ 处不能再继续走下去了, 则顶点 $v$ 就是一个悬挂点.
我们从一个悬挂点 $v$ 出发, 又可以走到另一个悬挂点 $v^{\prime}$, 所以树 $T$ 至少有两个悬挂点.
证法二设 $\mu=w v_1 v_2 \cdots v_k v$ 是树 $T$ 中的一条最长的链, 可以证明 $d(u)=d(v)=1$, 即 $u 、 v$ 是悬挂点.
事实上, 若 $d(u) \geqslant 2$, 则存在不同于 $v_1$ 的顶点 $w$ 与 $u$ 相邻, 如果 $w$ 是 $v_2, \cdots, v_k, v$ 中的一个, 则出现圈, 与树的定义矛盾.
如果 $w$ 是不同于 $v_2, \cdots$, $v_k, v$ 的点, 则 $r u v_1 \cdots v_k v$ 是比 $\mu$ 更长的链, 这与 $\mu$ 的取法矛盾.
从而 $d(u)=$ 1. 同样地, $d(v)=1$. 所以树 $T$ 至少有两个悬挂点.
注:: 证明一是"构造性"的, 证明二是用"最长链"的方法, 这是两个很重要的解题方法.
定理二设树 $T$ 的顶点数为 $n$, 则它的边数 $e=n-1$.
证明对顶点数 $n$ 用数学归纳法.
当 $n=1$ 时, $e=0$, 结论正确.
假设当 $n=k$ 时结论成立.
设 $T$ 是有 $k+1(k \geqslant 1)$ 个顶点的树, 由定理一, $T$ 至少有两个悬挂点, 设 $v$ 是其中之一, 则去掉 $v$ 及与它关联的边, 就得到一个有 $k$ 个顶点的树 $T^{\prime}$, 根据归纳假设 $T^{\prime}$ 有 $k-1$ 条边, 所以 $T$ 的边数为 $k$, 从而结论对一切自然数 $n$ 都成立.
%%TEXT_END%%



%%TEXT_BEGIN%%
定理三设 $T$ 是有 $n$ 个顶点、 $e$ 条边的图.
则下述三个命题是等价的:
(1) 图 $T$ 是树;
(2) 图 $T$ 无圈, 并且 $e=n-1$;
(3) 图 $T$ 连通, 并且 $e=n-1$.
证明由(1)推出 (2):
设图 $T$ 是树, 则由树的定义知 $T$ 无圈, 由定理二知, $e=n-1$, 故 (2) 成立.
由 (2) 推出 (3):
只要证明 $T$ 是连通的即可, 用反证法.
设 $T$ 是不连通的, 它有 $k(k \geqslant 2)$ 个连通分支, 因为每个连通分支都无圈, 故每个连通分支都是树.
若第 $i$ 个分支有 $p_i$ 个顶点, 根据定理二知, 第 $i$ 个分支有 $p_i-1$ 条边, 故
$$
e=\left(p_1-1\right)+\cdots+\left(p_k-1\right)=n-k \leqslant n-2 .
$$
这与 $e=n-1$ 矛盾.
于是证得 $T$ 是连通的.
由(3)推出 (1):
只要证得 $T$ 无圈, 则 $T$ 便是树.
当 $n=1$ 时结论显然成立.
设 $n \geqslant 2$, 那么 $T$ 必有悬挂点.
否则, 因 $T$ 连通且 $n \geqslant 2$, 故 $T$ 中每个顶点的度 $\geqslant 2$,于是
$$
e=\frac{1}{2}\left[d\left(v_1\right)+d\left(v_2\right)+\cdots+d\left(v_n\right)\right] \geqslant \frac{1}{2} \times 2 n=n .
$$
这与 $e=n-1$ 矛盾.
现对 $n$ 用数学归纳法证明 $T$ 无圈.
当 $n=2$ 时, $e=1$, 此时 $T$ 无圈.
设 $n=k$ 时命题成立.
$T$ 是有 $k+1$ 个顶点的图, 顶点 $v$ 是 $T$ 的悬挂点.
在 $T$ 中去掉 $v$ 及与它关联的边得到图 $T^{\prime}$, 由归纳假设可知 $T^{\prime}$ 无圈, 在 $T^{\prime}$ 中加人 $v$ 及与它关联的边又得到图 $T$, 故 $T$ 是无圈的.
从而命题正确.
定理三说明了"连通"、"无圈"及 " $e=n-1$ " 这三个性质中的任何两个都足以保证图 $T$ 是树, 所以也都可以作树的定义.
%%TEXT_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例1. 若 $T$ 是树, 则
(i) $T$ 是连通图, 但 $T$ 中去掉任一条边后, 所得的图 $G$ 不连通.
(ii) $T$ 无圈, 但添加任何一条边后, 得到的图 $G$ 便包含一个且仅包含一个圈.
反之, 若图 $T$ 满足(i) 或(ii), 则 $T$ 是树.
%%<SOLUTION>%%
证明:(i) 若图 $G$ 是连通的,则 $G$ 仍然是树, 所以 $G$ 有 $n-1$ 条边, 与 $T$ 的边数相等,矛盾.
(ii) 若 $G$ 没有圈, 则 $G$ 仍是树, 故 $G$ 有 $n-1$ 条边, 与 $T$ 的边数相同, 这是不可能的,所以 $G$ 含有圈.
显然 $G$ 仅含一个圈.
本题刻画了树的一个特征, 在点数给定的所有图中, 树是边数最少的连通图, 也是边数最多的无圈图.
由此可见, 在任意一个图 $G$ 中, 若 $e<n-1$, 则 $G$ 是不连通的,若 $e>n-1$, 则 $G$ 必有圈.
树的另一个特征也是很有用的.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例2. 设 $T$ 是树, 则 $T$ 中任何两个顶点之间恰有一条链; 反之, 若图 $T$ 中,任何两点之间恰有一条链,则 $T$ 必是树.
%%<SOLUTION>%%
证明:若 $T$ 是树, 由于 $T$ 是连通的,所以 $T$ 中任意两个顶点之间至少有一条链,又因为 $T$ 无圈,任意两点之间必只能有一条链.
反之, 若 $T$ 中任何两点之间恰有一条链, 则 $T$ 显然是连通的, 同时 $T$ 也必定无圈.
否则, 圈上的任意两点之间就至少有两条链, 这与假设矛盾.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例3. $n$ 个城市, 每个城市都可以通过一些中转城市与另一个城市通话, 证明至少有 $n-1$ 条直通的电话线路, 每条连结两个城市.
%%<SOLUTION>%%
证明:作图 $G$ : 用 $n$ 个顶点表示 $n$ 个城市, 若两个城市之间有直通电话, 则在相应的顶点之间连一条边.
由题意知, 图 $G$ 是连通图.
故 $G$ 的边数一定 $\geqslant n-1$, 从而至少有 $n-1$ 条直通的电话线路连结两个城市.
本题也可以这样考虑: 若得到的连通图 $G$ 有圈, 我们就去掉这个圈的一条边, 得图 $G_1$, 此时 $G_1$ 比 $G$ 少了一条边, 但仍然是连通的: 如果 $G_1$ 还有圈, 再去掉圈的一条边得连通图 $G_2 \cdots \cdots$...这样继续下去, 直到图中没有圈, 这个图当然就是树.
它有 $n-1$ 条边.
故图 $G$ 至少有 $n-1$ 条边.
上面所得到的树称为原来连通图 $G$ 的生成树.
在生成树上添上若干条边, 就可以得到(生成) 原来的图.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例4. 某 15 座城市,它们之间的航线分属三家航空公司.
已知无论哪一家航空公司停飞,旅客总还能从任意城市飞往其他任何城市 (当然, 可能中途需要转机),那么至少需要多少条航线?
%%<SOLUTION>%%
解:最少得有 21 条航线.
首先, 如果用航线把 15 个城市连接起来, 还要求从任何一个城市飞往其他任何一个城市的话,那么这样的航线当然不能少于 14 条.
下面我们把属于三家航空公司的航线数分别记为 $a 、 b$ 和 $c$. 由上所述, 可知任何两家公司的航线数和
(1) 都不能少于 14 , 也就是说 $a+b \geqslant 14, b+ c \geqslant 14, c+a \geqslant 14$. 把这三个不等式叠加后, 得 $2(a+b+c) \geqslant 42$, 即三家航空公司航线总数不能少于 21 .
如图(<FilePath:./figures/fig-c4i5.png>)列出 21 条航线的实例,其中用了不同线条来表示不同航空公司的航线.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例5. 某地区网球俱乐部的 20 名成员已举行 14 场单打比赛,每人至少上场一次.
求证: 其中必有 6 场比赛, 12 个参赛者各不相同.
%%<SOLUTION>%%
证本题在第二节已经讲过,这里我们再从树的角度给出另一种证明.
用 20 个点代表 20 名参赛者.
若两人比一场则在他们之间连边.
这样共有 14 条边, 每点至少连出 1 条边, 所证结论相当于: 可以找出 6 条边两两不相邻.
设图中共有 $n$ 个连通分支, 其中第 $i$ 个分支点数为 $v_i$, 边数为 $e_i$, 显然 $e_i \geqslant v_i-1$, 故 $\sum_{i=1}^n e_i \geqslant \sum_{i=1}^n\left(v_i-1\right)=\sum_{i=1}^n v_i-n$. 而 $\sum_{i=1}^n e_i=14, \sum_{i=1}^n v_i=20$, 故 $14 \geqslant 20-n, n \geqslant 20-14=16$. 由于每点至少连出一条边, 因此不可能存在一个连通分支, 它仅含一个孤立点.
故从每个连通分支中各取一条边, 即可保证两两不相邻,边数至少为 6 . 原命题得证.
如图(<FilePath:./figures/fig-c4i6.png>) 可知, 顶点数为 20 ,边数为 14 ,任选 7 条边,则必有两边在同一连通分支内, 它们必定相邻.
故 6 为最佳结果.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例6. 以一些圆(圆面)覆盖平面上给定的 $2 n$ 个点.
证明: 若每个圆至少覆盖 $n+1$ 个点, 则任意两个点能由平面上的一条折线所连结, 而这条线段整个地被一些圆所覆盖.
%%<SOLUTION>%%
证明:以这 $2 n$ 个点为顶点, 若存在一个圆, 它覆盖着两个点, 则在这两顶点之间连一条边, 得到一个图 $G$. 由题意知, $G$ 中每个顶点的度不小于 $n$. 每条边之所以能画出, 就表明它能整个地被一个圆所覆盖, 于是我们只需证明 $G$ 是连通图.
若 $G$ 不是连通图, 则存在一个连通分支 $G_1$, 至多含有 $n$ 个顶点, 这样对
$G_1$ 中每一个顶点 $v$, 都有 $d(v) \leqslant n-1$, 与题意矛盾, 从而 $G$ 是连通图.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例7. $n(n>3)$ 名乒乓球选手单打比赛若干场后, 任意两个选手已赛过的对手恰好都不完全相同.
证明: 总可以从中去掉一名选手, 而使余下的选手中, 任意两个选手已赛过的对手仍然都不完全相同.
%%<SOLUTION>%%
证明:用 $n$ 个顶点 $v_1, v_2, \cdots, v_n$ 表示这 $n$ 名选手, 如果命题不成立, 即每一个选手都是不可去选手.
对选手 $v_k(1 \leqslant k \leqslant n)$, 因为他不是可去选手, 所以去掉 $v_k$ 后, 总可以找到一对选手 $v_i$ 与 $v_j$, 他们所赛过的选手相同 (若有不止一对这样的选手, 则任取其中的一对), 这说明 $v_i$ 和 $v_j$ 赛过的选手仅差 $v_k$.不妨设 $v_i$ 与 $v_k$ 赛过, 而 $v_j$ 与 $v_k$ 末赛过, 在这样的一对点 $v_i$ 与 $v_j$ 之间连一条边, 并标上数字 $k$. 这样就得到一个有 $n$ 个顶点, $n$ 条边的图, 并且这 $n$ 条边上标有 $n$ 个互不相同的数.
由于 $n$ 个顶点 $n$ 条边的图一定有圈, 设 $v_{i_1} v_{i_2} \cdots v_{i_k}$ 为一个圈, 沿着这个圈前进时, 每通过一条边就相当于比赛选手增加或者减少一个人, 并且增加或减少的人是互不相同的.
由于沿着圈前进一周后仍回到 $v_{i_1}$, 即与 $v_{i_1}$ 比赛过的选手再增加或者减少不同的选手, 最后的结果仍与 $v_{i_1}$ 原来赛过的选手相同,产生矛盾.
因此,在 $n$ 个选手中至少有一个可去选手.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例8. 在一次演讲中, 有五名数学家每人均打两次盹, 并且每两人均有同时在打盹的时刻.
证明:一定有三个人, 他们有同时打盹的时刻.
%%<SOLUTION>%%
证明:作图 $G$ : 用 $v_1, v_2, \cdots, v_{10}$ 这 10 个顶点表示这五位数学家的十次盹, 当且仅当第 $i$ 次盹与第 $j$ 次盹有共同时刻时, 在 $v_i$ 与 $v_j$ 之间连一一条边.
由题意, 每两个数学家均有同时在打盹的时刻, 从而图 $G$ 中的边数至少是 $\mathrm{C}_5^2=10$ 条.
而图 $G$ 的顶点数为 10 , 故 $G$ 中必有圈.
设这个圈为 $v_{i_1} v_{i_2} \cdots v_{i_k} v_{i_1}$, 且 $v_{i_1}$ 是圈中最先结束的一个盹, 那么当 $v_{i_1}$ 刚结束时, $v_{i_2}$ 及 $v_{i_k}$ 还在进行, 这就证明了有三位数学家有同时打盹的时刻.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
例9. 某居民区内有 1990 个居民, 每天他们之中每个人都把昨天听到的消息告诉给他所有的熟人,而且任何消息都能逐渐地被全区居民所知道.
证明: 可以指定 180 个居民, 使得同时向他们报导某一消息,那么至多经过 10 天,这一消息便为全区居民所知道.
%%<SOLUTION>%%
证明:用点表示这些居民,两个顶点相邻就表示相应的居民是熟人, 这样就得到了一个有 1990 个顶点的图 $G$.
由题意知, 图 $G$ 是连通的.
不妨设这个图是树 $T_{1990}$ (否则用这个图的生成树来代替它), 在树 $T_{1990}$ 中, 取一条最长的链, 设为
$$
v_1^{(1)} v_2^{(1)} v_3^{(1)} \cdots v_{11}^{(1)} \cdots v_n^{(1)} \text {. }
$$
取 $v_{11}^{(1)}$ 作为一个居民代表, 并将边 $\left(v_{11}^{(1)}, v_{12}^{(1)}\right)$ 去掉.
这时 $T_{1990}$ 被分成两棵树, 前一棵树中, 每个顶点 $v$ 到 $v_{11}^{(1)}$ 的距离不大于 10 (否则在树 $T_{1990}$ 中, $v$ 到 $v_n^{(1)}$ 是一条比 $v_1^{(1)}$ 到 $v_n^{(1)}$ 更长的链). 于是代表 $v_{11}^{(1)}$ 所知道的消息, 前一棵树的顶点所表示的人在 10 天之内都能知道.
对后一棵树, 也有一条最长的链, 设为
$$
v_1^{(2)} v_2^{(2)} v_3^{(2)} \cdots v_{11}^{(2)} \cdots v_m^{(2)} \text {. }
$$
这里 $m \leqslant 1990-11=1979$. 同样地, 取 $v_{11}^{(2)}$ 作为一个居民代表, 并去掉边 $\left(v_{11}^{(2)}, v_{12}^{(2)}\right)$, 将这棵树再分为两棵树.
这样继续下去, 当选好 $v_{11}^{(i)}(i \leqslant 179)$ 时, 剩下的树的顶点数 $\leqslant 11$, 这时代表总数为 $i+1 \leqslant 180$, 命题成立.
否则陆续得出代表
$$
v_{11}^{(1)}, v_{11}^{(2)}, \cdots, v_{11}^{(179)} \text {. }
$$
每个代表都可以把一个消息在 10 天之内告知他那个居民区中的居民.
最后剩下一棵树,至多有
$$
1990-11 \times 179=21
$$
个顶点.
设
$$
v_1 v_2 \cdots v_k
$$
是它的一条最长链, 若 $k \geqslant 11$, 则取 $v_{11}$ 作为第 180 个居民代表 $v_{11}^{(180)}$, 若 $k<$ 11 , 则取 $v_1$ 作为第 180 个居民代表 $v_{11}^{(180)}$. 这样选出的 180 个居民代表
$$
v_{11}^{(1)}, v_{11}^{(2)}, \cdots, v_{11}^{(179)}, v_{11}^{(180)}
$$
是满足题目要求的 180 个居民.
%%PROBLEM_END%%


