树上结论速记

SkyWave · 2025-08-06 10:25:50 · 个人记录

如何证明无边权的树上离一个点的最远点一定取在直径两个端点之一

好的，以下是 LaTeX 正常渲染的版本，避免使用 $ 包围行内公式，而是使用 \(...\)，区块公式用 \[...\]：

🔧 关键定义

• 树的 直径：树中最远的两点之间的距离，设为 d，其两个端点记为 s, t，满足 \text{dist}(s, t) = d。

🧠 直观理解

在树上，从任意点 u 出发往最远点 v 走，最终会走到“某个角落”——也就是树的某个“最深”位置。 而直径的两个端点正是“两个最远的角落”，所以这个最远点 v 必然是某条直径的端点。

🧾 形式化证明

设：

• 树为 T = (V, E)，无边权，边长为 1。
• 取树的直径两个端点为 s, t，满足 \text{dist}(s, t) 最大。

🧩 目标

我们要证明：对任意 u \in V，有

即：u 的最远点在直径的两个端点中。

🧠 证明思路（基于 BFS 与三角不等式）

从直径的定义出发：

1. 对任意点 u，从 u 开始做一次 BFS，找到最远点 v。
2. 从 v 再做一次 BFS，找到它的最远点 w。则路径 v \to w 是树的一条直径路径。

所以：

即 任意点的最远点一定是某条直径的端点。

又因为树的直径是唯一最长路径，所以其端点至多只有两个（设为 s, t），所以任意点的最远点一定是 s 或 t。

✅ 举例说明

考虑如下树：

1 - 2 - 3 - 4 - 5 - 6
            |
            7

• 树的直径是从 1 到 6，长度为 5。
• 任意节点（如 3、4、7）的最远点一定是 1 或 6（直径端点之一）。

🔚 总结

我们已经证明：

在无边权的树上，任意点的最远点一定是某条直径的端点。

这个结论常用于树的算法设计，比如：

• 两次 BFS 求直径；
• 树的重心判定；
• 树上最长路径分析等。

如果你希望我补充图论术语更完整的严谨证明（如从“无环图的路径唯一性”出发），我也可以进一步补充。

为了使节点 u 的eccentricity（即 \max_{v\in V}\mathrm{dist}(u,v)）最小，u 必须位于某条直径路径的“中点”上。下面给出理由，并说明中点的个数。

树上，要使所有点到 u 的最长路最短，u 为什么一定是直径中点？直径中点有几个？

1. 记号与定义

• 树为 T=(V,E)，无边权。

• 直径端点记为 s,t，且

  D \;=\;\mathrm{dist}(s,t)

  是树的直径长度。

• 对任意节点 u，定义其 eccentricity

  e(u)\;=\;\max_{v\in V}\mathrm{dist}(u,v).

• 我们要选取一个节点 u^* 使得

  e(u^*) \;=\;\min_{u\in V} e(u).

2. 为什么最优 u^* 在直径路径上

1. 任何节点的最远点必在 \{s,t\}： 上一问已证明，对任意 u，

   e(u) =\max_{v\in V}\mathrm{dist}(u,v) =\max\bigl(\mathrm{dist}(u,s),\,\mathrm{dist}(u,t)\bigr).

2. 因此，

   e(u) =\max\bigl(\mathrm{dist}(u,s),\,\mathrm{dist}(u,t)\bigr) \;=\;\text{在路径 }s\!\to\!t\text{ 上测量到端点的最大值}.
3. 要让这个最大值尽可能小，自然将 u 放在路径 s\!\to\!t 上，且尽量 “居中”——也就是距离 s 与 t 的距离都不要太大。

3. 中点的具体位置

设直径路径上的节点序列为

• 若 D 为偶数，令 k = D/2，则唯一本节点

  v_k

  即为唯一的中点，此时

  \mathrm{dist}(v_k,\,s) =\mathrm{dist}(v_k,\,t) =\tfrac{D}{2}, \quad e(v_k)=\tfrac{D}{2}.

• 若 D 为奇数，令 k = \lfloor D/2\rfloor，则有 两个相邻节点

  v_k,\;v_{k+1}

  都可以使得

  \max\bigl(\mathrm{dist}(v_i,s),\,\mathrm{dist}(v_i,t)\bigr) =\Bigl\lceil \tfrac{D}{2}\Bigr\rceil =k+1, \quad i=k\text{ 或 }k+1.

  这两个节点都是最优解。

4. 结论

1. *最优节点 $u^ 必在直径路径 \overline{st}$ 的中点上。**

2. 中点的个数：

   • 若直径长度 D 为偶数，恰有 1 个中点；
   • 若 D 为奇数，恰有 2 个中点（它们互为邻居）。

这也正是“树的中心”（tree center）的定义：要使所有点到中心的最大距离最小，中心正好是直径的中点，且至多两个。