7.2 生成树
本章目录 · 2 节
本章导读
【定义7.2.1:生成树、树枝、弦与余树】若无向图 的生成子图 是树,则 是 的生成树。它保留 的全部顶点,恰含 条边。属于 的边称树枝; 中不属于 的边称弦。全部弦的边导出子图称对应的余树,记 。
“余树”是名称,不保证本身为树;它不一定连通,也可以含圈。它也不是通常的图补图:余树只从原图边中取未选的弦,不能补进原图没有的边。本书用边导出子图,因此只保留弦及其端点;若采用全部顶点仍保留的另一画法,应说明会额外出现孤立点。
为讲清端点,图中补上顶点 。树枝为 ,弦为 ,共有7个顶点、11条边。余树单独展开如下,它是边 与圈 的不相交并,顶点 不属于任何弦而不出现在边导出图中。
【定理7.2.1:生成树存在的充要条件】无向图有生成树,当且仅当图连通。必要性:生成树保留全部顶点并使它们连通,原图边更多,当然也连通。
充分性采用破圈法:若连通图有圈,删除该圈中任一条边,连通性保持;反复删圈边直到无圈。始终保留全部顶点,最后图连通无圈,因此为生成树。对多重图,环和两条平行边组成的二圈也可据此处理。图若不连通只能为各分支求生成树,所得是生成森林,不能把它叫作一棵覆盖全部顶点的生成树。
【推论7.2.1】 阶 边连通图中 ,因为任一生成树已使用 条不同边。这与5.50的证明相衔接。
【定理7.2.2与定义7.2.2:基本回路】给定生成树 ,加入任一弦 ,它与 中唯一的 路径构成唯一的圈。这个圈只含一条弦 ,其余全为树枝,称对应 的基本回路或基本圈;不同弦对应不同基本圈,因为它们各自含有不同且唯一的弦。
全部基本圈构成对应 的基本回路系统。连通图有 条弦,因此基本圈个数为 ,称圈秩,记 。圈秩只由原图的点、边数决定,不随生成树改变;具体的基本回路系统却可能改变。
图7.2.1对应的五个基本圈,以下把它们当作边集书写,不把列举边号的顺序误认为一次连续行走次序:,,,,。图的圈秩为 。
【广义回路与回路空间】一个圈或若干个两两边不重的圈之并,称广义回路,并把空边集也纳入。等价地,选出一些边后,每个顶点的所选度数都为偶数;允许多个分支、共享顶点,不能强求每个广义回路都只有一个圈。
用 表示边集的对称差,即只保留出现奇数次的边,也称环和。两个广义回路的对称差仍是广义回路。在 上,定义 ,广义回路全体 构成维数为 的线性空间,每套基本回路系统都是一组基。这里标量的加法、乘法都按模2计算,,不是通常整数加法。
例如原图中 ,,分别对应教材列出的两个回路。公共边要抵消,不能取普通并集。
基的理由也可直接理解:给任一广义回路,把它所含每条弦对应的基本圈做环和,便可消去全部弦;余下若非空,就是森林中的非空偶度子图,但任何非空森林都有树叶,不可能全偶。因此余集为空,说明能够表示;每个基本圈又有自己独占的一条弦,表示的系数唯一。电网络分析中选独立回路方程,正是利用这种基本回路思想,不必把所有圈都重复列为独立约束。
【定理7.2.3与定义7.2.3:基本割集】从生成树中删除一条树枝 ,树分成两部分 。原图中全部跨越 的边组成割集 。它只含这一条树枝,其余都是弦,称对应树枝 的基本割集;不同树枝给出不同基本割集。
这个集合是包含关系下极小的割集:删掉全部跨边,两侧无法相通;若保留其中任何一条,两侧各自已有树内路径,再经此边仍连通。故这里不仅是随意找到一个会割断图的边集合。全部 个基本割集组成对应 的基本割集系统,称 为割集秩,记 。
图7.2.1对应树枝 的六个基本割集依次为 ,,,,,。注意 对应树枝 ,并不是按不存在的“第六条树枝 ”配对。割集秩为6,也不随选树改变。
【广义割集与割集空间】任取顶点子集 ,定义 为原图中恰有一个端点落在 的边的集合;它称广义割集,。只允许从实际边集 中取边,不能把两部间原本没有的顶点对也当成边。广义割集不一定极小,因此不一定是前述严格定义的割集。
广义割集全体记 ,以对称差为加法、以0或1作标量,构成 上维数为 的线性空间,任一基本割集系统都是一组基。每个基本割集只含一条对应树枝,所以它们独立;任一广义割集可用其所含树枝对应的基本割集做对称差表示。抵消树枝后若还有非空广义割集,就意味着某个非平凡顶点分割没有树枝跨越,与生成树连通矛盾。
原图中 ,。因此“广义”并非增添假边,而是允许由基本割集组合得到不一定极小的实际跨边集合。上面的两个维数公式都以连通图为前提。
【定义7.2.4:最小生成树】在连通无向带权图中,生成树 的权为 ;所有生成树中权最小者称最小生成树。每棵生成树都含相同数量的 条边,最小化的是总权,不是边数。最小生成树也不是从某一点到其余各点的最短路径树,两个优化目标不能混用。
【避圈法,即克鲁斯卡尔算法】先删自环,因为自环不能属于任何树;将剩余边按权从小到大排序。从保留全部顶点、没有边的森林开始,依次考察各边:若其两端在不同连通分支,就加入并合并两分支;否则会成圈,应跳过。选到 条边时停止。若扫描完仍不足 ,输入不连通,所得只能是最小生成森林。
权相等时可任意固定顺序,最优权相同,但最小生成树不一定唯一;负权也可用于本算法,不能把迪杰斯特拉法的非负权限制照搬过来。若用并查集维护分支,主要代价来自排序,通常为 。
最优性的交换论证:假设已选森林包含在某棵最优生成树中。下一条加入的边 若不在该树中,加它形成一个圈,其中必有另一条边 跨越当前某分支到外部。按从小到大的选边规则,;用 替换 仍是生成树,总权不增加,并包含新增森林。逐步保持这个性质,最终得到最优生成树。这补足教材略去的正确性理由。
例7.2.1:两幅图的最小生成树
图(a)各边为 。先选 ,三条1权边把 连在一起;两条2权边再加入都会成圈,跳过。连接剩下顶点 的最便宜边为 ,所以树边为 ,总权 。
图(b)自环 权虽为1,却必须先删除。其余边为 。按权选 ,再遇 会构成三圈而跳过;选 、 后覆盖全部五点,共4边,权为 。
这两例都应从图中逐边核对,不能因为自环权小就选入,也不能只给总数而不说明对应树边。(例完)
【例7.2.2:数据分析中的单链聚类】给数据集 以及对称的不相似度或距离 ,约定数值越小表示越接近。可以把它归一化到 ,不要求一定满足三角不等式。教材称其为“相似度”,但随后的从小到大合并及最小间隔最大化都使用距离的方向;若手中指标 是数值越大越相似,应先转成例如 ,不能原样排序。
给定 ,一个 聚类就是分成 个非空子集的划分 。两类之间的单链距离为 ;划分的最小间隔为 。目标是最大化不同类别之间最近一对数据的距离,不是把各类平均距离直接相加。
构建数据点的带权完全图,边权取 。从 个单点分支开始执行克鲁斯卡尔算法,只在不成圈时并入一边;合并 次,恰剩 个连通分支时停止,它们便是一组最小间隔最大的聚类。应数合并次数或分支数,不是“选到 条边就停”。
最优性说明:记下一条能连接当前不同分支的候选边权为 ,那么当前划分的最小间隔就是 。任何另一种不同的 划分,都必须拆开至少一个当前分支;该分支由此前选入的树边连通,故一定有一条此前边跨越另一划分的两类,其权不超过 ,所以另一划分的最小间隔不超过 。同权时可能有多个同样最优的划分,算法不保证唯一;这种单链法还可能把一串相邻但首尾较远的数据连成一类,是否适合具体数据须结合目标判断。(例完)
