瓶颈生成树
以最小化最大边权为目标的生成树;任一棵 MST 都是瓶颈生成树,但反过来不一定。标签 图论 / 生成树 / 瓶颈生成树
定义
给定连通带权无向图 。对生成树 ,定义它的瓶颈为
使 最小的生成树称为最小瓶颈生成树,简称瓶颈生成树;这个最小值称为图的瓶颈值。
与最小生成树的关系
任一棵 MST 都是瓶颈生成树。
设 是 MST, 是 中权值最大的边。删去 会把 分成两个连通块,形成一个割。若存在一棵生成树 ,其最大边权小于 ,那么 必须有一条边 跨过这个割。由割性质,,与 的最大边权小于 矛盾。因此没有生成树的最大边权能比 更小。
反过来不成立。三角形边权为 时,MST 使用边权 和 ,边权和为 ,瓶颈为 ;另一棵生成树使用两条边权 ,边权和为 ,瓶颈仍然是 。它也是瓶颈生成树,但不是 MST。
阈值刻画
设 为只保留权值不超过 的边得到的子图。瓶颈值就是使 连通的最小 :
- 若 连通,任取一棵生成树,它的最大边权不超过 。
- 若存在一棵最大边权不超过 的生成树,则 连通。
因此按边权从小到大合并,第一次使图连通时的边权就是瓶颈值;此时得到的生成树也是 MST。
由此还可得到一个常用推论:MST 上 到 的路径中最大的边权,等于原图中 到 所有路径的最小可能最大边权。
常见误解
- 认为瓶颈生成树就是 MST:MST 一定是瓶颈生成树,但瓶颈生成树可能边权和更大。
- 认为所有瓶颈生成树的边权和相同:不一定,它们只共享最小化的最大边权。
- 认为瓶颈值是最小边权或平均边权:瓶颈值是一个连通阈值。
- 认为瓶颈生成树一定包含全局最小边:不一定,关键是所选边在阈值内能连通全图。