动机:最远的顶点究竟有多远?
连通图保证任意两个顶点之间都有路径,却不保证从哪里出发都同样方便。在一条很长的路径上,一个端点离另一个端点很远;从中间的顶点出发,到两端的距离就比较均衡。要准确比较这些出发位置,我们先固定一个顶点,测量它到所有顶点的距离,再取其中的最大值。接下来才问:选择哪个出发点,能够使这个最大值尽可能小?
一般图中可能有多条路径相互竞争。树中任意两点之间只有一条路径,分支无法提供捷径。这个限制使我们能得到完整而明确的结论:任取一条直径路径,它的两个端点就足以确定每个顶点的最远距离;路径的中间位置则确定整棵树的中心。另一种证明会说明,为什么不断同时删除全部叶顶点,也能找到相同的中心。
距离与几种不同的极值
本节的图都是有限、简单、无向、无权的图。设 连通且至少有一个顶点。
定义 1.4.1
(连通图中的距离)
两点的距离 是所有 – 路径中最少的边数,并规定 。连通性保证距离有限。图明确时可以省略下标。
距离具有对称性,不同顶点之间的距离为正,并满足三角不等式
证明时,把从 到 的最短路径与从 到 的最短路径接起来,得到长度等于右侧的游走。删去重复部分后得到一条不更长的路径。不等式不一定取等号,因为经过 的最佳路线未必是从 到 的最短路线。
定义 1.4.2
(偏心度、直径、半径与中心)
顶点的偏心度、图的直径、半径与中心分别定义为
偏心度先固定一个端点再取最大值;直径允许两个端点都变化;半径则是在每个出发点的最坏情况之间,选择最好的出发点。中心是一个顶点集合,不是距离数值。由于顶点集有限且非空,这些极值都能达到。只有一个顶点的图,直径和半径都是零,唯一的顶点就是中心。对于不连通图,本节不定义有限的全图半径,可以分别研究它的各个连通分支。
定理 1.4.3
(一般连通图的半径与直径界)
任意有限、非空、连通图都满足
证明
(直径端点处的三角不等式)
选择距离为 的两个顶点 。对任意 ,三角不等式给出 。对 取最小值,再利用距离是整数,就得到左侧。每个偏心度都不超过直径,因此右侧也成立。下面将证明:树的半径总能达到这个下界。这是树的一条额外定理,不是半径定义本身的内容。
一条直径如何限制所有分支
设 是非空树,取一条长度等于直径 的路径
记 、。这样的路径存在,因为最大距离能够达到。树中两点之间的路径唯一,所以直径两端之间的路径也是最长简单路径。
每个顶点 在 上都有唯一的连接点 :从 走向 时第一次进入 的位置就是它,而且从 到 上任意顶点的路径都会经过这个连接点。若 已经在 上,连接点就是 。为什么路径 外分支的连接点唯一?删除 的全部顶点后,任一剩余连通分支都必须通过某条边连接回 。如果有两条不同的连接边,无论它们在 上的端点相同还是不同,都能结合分支内的路径及 的一部分构成圈,与树无圈矛盾。路径唯一性也说明,到 的路径必须先经过连接点。
令 。于是到两端的距离分别是 与 。二者都不能超过直径,所以
这就是“直径”一词隐含的关键限制。长分支不能接在 的端点附近,否则它与另一端之间会出现更长的路径。中间位置允许较长的分支,但分支高度仍同时受两端约束。
定理 1.4.4
(两个直径端点决定全部偏心度)
设 是有限非空树的任意一条直径的两个端点,则对每个顶点 ,
具体地,若 的连接点是 ,且 ,则
证明
(经由连接点估计每个距离)
固定 ,任取 ,分别记它们的连接点下标为 ,到连接点的距离为 。从 到 ,沿 到 ,再走到 ,得到长度为 的游走。两个分支重叠时,这条游走可能往返经过一些边,但仍然给出距离的上界。若 ,利用 得 ;若 ,利用 得 。因此
另一方面,,,其中至少一个恰好达到上界。对 取最大值,两个公式都得证。若 ,树只有一个顶点,各量都是零,证明仍然适用。
证明透视
直径的极大性在哪里用上
上界 是全部内容,而它建立在一个不等式上。路线 只是一条游走,所以只给出距离的上界,这一步不需要树的性质。树的性质经由连接点的唯一性进入,它使 与 有明确定义。 的极大性则经由分支界 进入,并在两种情形中各用一次: 连接在 靠 的一侧时用 ,靠 的一侧时用 。下界毫无代价,因为端点 本身就实现了 与 。在圈上连接点并不唯一,下面四圈的反例正是从这里逃脱。
推论 1.4.5
(树的半径与中心)
设 是有限非空树 的一条直径路径。则 。若 ,中心是 ;若 ,中心是 。
证明
(直径的中间位置)
偏心度公式把两种代价分开了:离开直径的代价是 ,沿直径选择位置的代价是 。后者在最接近 的整数位置达到最小值 。直径外的顶点有 ,不可能达到这个最小值。
因此 。若 ,中心只有 ;若 ,中心是相邻的两个顶点 。树可能有多条不同直径,但上述论证用任意一条直径都描述了由偏心度定义的同一个集合 ,所以它们的中间顶点或中间顶点对必定相同。
这里允许选择的位置是顶点。长度为五的路径有两个中间顶点,它们的偏心度都是三;连接这两点的边的内部中点,并不是一个偏心度为二点五的额外顶点。
概念视角算法
两次搜索找出直径及其中点
连接点的估计还表明:离任意顶点最远的顶点必定是某条直径的端点。因此从任意顶点做广度优先搜索,可以找到满足 的顶点 ;再从 出发搜索,找到最远的顶点 以及 – 路径,它就是一条直径路径。由上面的推论,它的中间顶点或中间顶点对就是中心。于是两次线性时间的搜索算出了与修剪相同的集合。
为什么删除叶顶点不会改变中心
定义 1.4.6
(叶顶点与同时删除)
叶顶点是度数为一的顶点。若树 至少有三个顶点,同时删除它的全部叶顶点,用 表示保留顶点导出的子图。
至少有一个顶点被保留,否则至少有三个顶点的连通图中,每个顶点的度数都至多为一,这是不可能的。两个保留顶点之间的路径也全部被保留,因为路径内部的每个顶点至少有两个邻点。因此 仍是非空树,保留顶点之间的距离不变。
定理 1.4.7
(一轮完整删除使保留顶点的偏心度统一减一)
若树 至少有三个顶点, 是同时删去全部叶顶点后的树,那么对每个保留顶点 ,
证明
(每个被删的叶顶点都挂在保留顶点上)
每个被删去的叶顶点都有一个保留的邻点,否则两个相邻叶顶点就会构成整个连通树,与顶点数至少为三矛盾。因此对固定的保留顶点 ,到任意被删顶点的距离至多为 ,到保留顶点的距离至多为 。这证明了 。
为证明等号,在 内选离 最远的顶点 。若 不止一个顶点,则 ,且 在 中只有一个邻点;否则可以沿另一个邻点延长唯一的 – 路径。但 被保留下来,说明它在 中的度数至少是二,所以它还有一个被删除的叶邻点。把这条边接到路径末端,就得到从 出发、长度为 的路径。若 只有一个顶点,它在 中的邻点全部被删去,同样得到结论,此时 。
还需要排除原中心被删除的可能。设叶顶点 的唯一邻点是 。从 到其他任意顶点的路径都先到 。因为还有不同于 的第三个顶点,从 最远的顶点可以选得不是 。于是 ,叶顶点不会使偏心度最小。原中心全部被保留,而所有保留顶点的偏心度都减少相同的数,因此最小值所在的顶点集合不变,中心也就不变。
证明透视
为什么一轮修剪使所有偏心度减少同一个数
顶点数的假设只用了一次:至少有三个顶点时,被删的叶顶点不会只与另一个叶顶点相邻,因此每个被删顶点都通过一条边挂在某个保留顶点上,这给出上界。等号需要在 中最远顶点之外还有一个被删的叶顶点;该顶点是 的叶顶点(或唯一顶点),而它在 中度数至少为二。减少量对所有保留顶点相同,所以它们的大小次序和最小值点都不变。被删的叶顶点另行排除,因为每个都比它的邻点多一步。
算法与停止条件
如果只剩一个或两个顶点,就全部返回。单顶点树的唯一顶点是中心,双顶点树的两个端点都是中心。否则同时删除一整轮当前叶顶点,再重复。有限非平凡树至少有两个叶顶点:取最长路径的两个端点即可证明。因此过程一定终止。每轮保持中心不变,所以最终剩下的单顶点或相邻顶点对恰好是原树的中心。
使用邻接表时,先计算当前度数,把叶顶点放入队列。每轮先记下队列当前长度,只处理这批顶点;更新保留邻点的度数,把新出现的叶顶点加入队列,留到下一轮处理。不能在本轮立即删除新叶顶点。活动顶点数至多为二时停止,返回所有活动顶点;最后只剩一个顶点时,它的度数是零,也应被返回。每个被删顶点只扫描一次,邻接表中总共只有 个条目,因此度数更新、队列操作和最后一次活动顶点扫描总计需要 工作量、 存储空间。若每轮重新扫描所有顶点寻找叶顶点,就不能由上述论证得到线性时间界。
例题
例题 1.4.8
(有两个中心顶点的路径)
考虑 ,其直径为五。由 ,按顺序得到偏心度 。所以半径为三,中心是 。第一轮删除 ,第二轮删除 ,然后在相邻顶点对处停止。一个顶点属于中心,并不意味着它是唯一的最佳位置。
例题 1.4.9
(分支可以产生另一条直径,而不移动中间顶点)
取路径 ,把 连到 ,再把 连到 。原路径长六。从 到任意路径顶点的距离至多为 ;较浅的分支顶点,以及原路径内部的顶点对,都不会给出更大距离。因此直径仍为六,– 与 – 都是直径路径。公式给出 、、。中心是 ,它也是这两条直径的共同中点。分支长度很关键:若分支长得多,原路径就不再是直径。
例题 1.4.10
(度数并不能决定中心)
从 出发,把 接到 ,把 接到 。四个叶顶点是 ,而 的度数都是三。任意两叶之间距离至多为三,且 ,所以直径为三。 的偏心度都是二,每个叶顶点的偏心度都是三。一轮同时删除四个叶顶点后,剩下中心边 。再看一条很长的路径:所有内部顶点的度数都是二,中心却只有中间的一个或两个顶点。局部度数并不记录到远端的距离。
反例与常见误解
反例模式
圈会破坏树的结论
在四圈 上,每个顶点的偏心度都是二。直径与半径都为二,四个顶点全是中心。直径端点 到 的距离都是一,但 。因此,端点偏心度公式、,以及中心只有一个或两个顶点的结论,都不能推广到一般连通图。这个圈没有叶顶点,删除叶顶点的算法也无法前进。树的证明用到了唯一连接路径,圈并不具备这个性质。
即使在树中,删叶规则也有一个容易被忽略的条件。
反例模式
立即删除新叶顶点可能删掉中心
在 上,先删除 ,再删除刚出现的叶顶点 ,接着删除 。此时确实只剩两个顶点,但剩下的是 ,原树的中心却是 。任意顺序的逐个删除不保持中心。正确的一轮必须在动手前确定本轮的叶集合:这里两轮分别是 与 。
常见错误
(直径数的是边,不是顶点)
直径数的是边,不是顶点:路径 有六个顶点,直径却是五。距离始终由最短路径定义;只是树的直径路径同时也是最长简单路径。叶顶点未必是直径端点:在第二道练习中,叶顶点 的偏心度是三,小于直径四。
常见错误
(中心使最大距离最小,而非距离总和)
使最大距离最小,与使距离总和最小,是两个不同的优化问题。在最后一题中,中心 的最大距离是二、距离总和是 ;而 的最大距离是三,距离总和却较小,为 。
练习
快速检查
(对路径 ,求直径、半径、中心及 的偏心度,并列出每一轮同时删除的叶顶点。)
解答 · 答案
直径为八,半径为四,中心是 ,且 。各轮依次删除 、、、,留下 。每轮使用的是该轮开始时的叶顶点。
快速检查
(在 上把一个新叶顶点 接到 。求中心与 。 是某条直径的端点吗?列出删除轮次。)
解答 · 答案
直径为四,由 – 达到,中点是 。 到 的距离都是三,因此 。直径端点的偏心度必须等于直径,所以这个叶顶点不是任何直径的端点。先删除 ,再删除 ,剩下 。
快速检查
(证明:任意有限非空连通图的相邻顶点都满足 。它们的偏心度必须不同吗?)
解答 · 答案
对每个 ,有 。取最大值得到 ;交换 得到另一侧不等式。偏心度可以相等:双顶点树的两个顶点偏心度都是一,四圈的全部顶点偏心度都是二。相邻性限制差值,却不保证每走一步都严格接近中心。
快速检查
(在非空树 的顶点 处接上一个新叶顶点 。证明新直径为 。分别把叶顶点接到 的 与 ,求新中心。)
解答 · 答案
旧顶点之间的距离不变,因为新叶顶点不可能位于它们之间路径的内部。旧顶点对给出的最大距离是 ;含 的顶点对给出的最大距离是 。所有顶点对都已包含,公式得证。五顶点路径有 、,所以在 接叶顶点后直径仍为四,中心仍为 。在 接叶顶点时,,新直径为五;直径路径 的中间顶点是 ,即新中心。直径公式先给出数值,再用一条直径路径确定中心。
快速检查
(从 出发,在 处接上四个新叶顶点。找出中心,比较从 与从 出发到所有顶点的距离总和。中心一定使距离总和最小吗?)
解答 · 答案
每个新叶顶点到 的距离是四,任意顶点对距离也不超过四。因此 – 是一条直径,中心是偏心度为二的 。从 出发的距离总和为 ,最后一项来自四个新叶顶点。从 出发的总和为 。所以中心未必使距离总和最小: 的总和更小,但它的最大距离为三,比 的最大距离二更大。