瓶颈生成树

以最小化最大边权为目标的生成树;任一棵 MST 都是瓶颈生成树,但反过来不一定。

标签 图论 / 生成树 / 瓶颈生成树

定义

给定连通带权无向图 𝐺=(𝑉,𝐸)。对生成树 𝑇,定义它的瓶颈为

bottleneck(𝑇)≝max𝑒∈𝑇𝑤(𝑒)

使 bottleneck(𝑇) 最小的生成树称为最小瓶颈生成树,简称瓶颈生成树;这个最小值称为图的瓶颈值。

与最小生成树的关系

任一棵 MST 都是瓶颈生成树。

设 𝑇 是 MST,𝑒 是 𝑇 中权值最大的边。删去 𝑒 会把 𝑇 分成两个连通块,形成一个割。若存在一棵生成树 𝑇′,其最大边权小于 𝑤(𝑒),那么 𝑇′ 必须有一条边 𝑓 跨过这个割。由割性质,𝑤(𝑓)≥𝑤(𝑒),与 𝑇′ 的最大边权小于 𝑤(𝑒) 矛盾。因此没有生成树的最大边权能比 𝑇 更小。

反过来不成立。三角形边权为 1,2,2 时,MST 使用边权 1 和 2,边权和为 3,瓶颈为 2;另一棵生成树使用两条边权 2,边权和为 4,瓶颈仍然是 2。它也是瓶颈生成树,但不是 MST。

阈值刻画

设 𝐺𝑡 为只保留权值不超过 𝑡 的边得到的子图。瓶颈值就是使 𝐺𝑡 连通的最小 𝑡:

𝐵(𝐺)=min{𝑡:𝐺𝑡连通}
  • 若 𝐺𝑡 连通,任取一棵生成树,它的最大边权不超过 𝑡。
  • 若存在一棵最大边权不超过 𝑡 的生成树,则 𝐺𝑡 连通。

因此按边权从小到大合并,第一次使图连通时的边权就是瓶颈值;此时得到的生成树也是 MST。

由此还可得到一个常用推论:MST 上 𝑢 到 𝑣 的路径中最大的边权,等于原图中 𝑢 到 𝑣 所有路径的最小可能最大边权。

常见误解

  • 认为瓶颈生成树就是 MST:MST 一定是瓶颈生成树,但瓶颈生成树可能边权和更大。
  • 认为所有瓶颈生成树的边权和相同:不一定,它们只共享最小化的最大边权。
  • 认为瓶颈值是最小边权或平均边权:瓶颈值是一个连通阈值。
  • 认为瓶颈生成树一定包含全局最小边:不一定,关键是所选边在阈值内能连通全图。
源码位置