2012年noi冬令营唐文斌讲稿(生成树) PPT.ppt

图的绝对中心 绝对中心： 中心未必要在原图的点上 可以在边上 到最远点距离最小 最小直径生成树就是绝对中心的最短路树 偏心距最小 ? 直径最小 无权图：枚举绝对中心? 带权图的MDST 求绝对中心 带区间的最短路算法 最小直径最小生成树 ? 双连通图的固定中心生成树 给定一个双连通图和一个顶点s，求一棵以s为中心的生成树。 双连通: 连通图, 且图中没有割点 即, 删除任意单个节点都不会导致图不连通 双连通图的固定中心生成树 算法： 设t为s的任意一个相邻顶点。找到一组标号D，满足所有顶点被不重复地标为1…n，并且D(s)=1,D(t)=n。对于每个顶点v(v≠s,t)，都存在两个与v相邻的顶点u和w，满足D(u)D(v)D(w)。 图论专题之 生成树 清华大学 唐文斌 tangwb06@ 定义: 生成树 无向图G=(V,E) G的一个生成树T是G的一个子图(树) 包含G的所有节点: V’ = V 包含G的部分E’∈E 性质: 包含所有点, 无环 生成树: 最大的无环边集 生成树: 最小的连接所有点的边集 包含所有的桥(割边) 更多定义… 树的直径: 树的直径定义为树上最远两点的距离 树的中心 在树上选择一个点, 离其他所有点最远点距离最小 Q: 可能有多少个? 性质: 一定是直径路径的中心点 最小生成树(MST) 最小生成树(Minimal Spanning Tree) 带权无向图 生成树的权定义为所有树边的权值之和 最小树形图(Minimum Arborescence) 带权有向图 从某一个节点出发, 可以到达所有节点 生成森林 原图不连通, 每一个连通块的生成树集合 Prim Prim算法: 与Dijkstra相近 选任一点为根 找不在树上且离树最近的点加入生成树 时间复杂度O(mlogn) //优先队列优化 Kruskal Kruskal算法: 一开始所有的点为独立连通块 按边权从小到大检查每一条边 如果这条边连接了两个不同的连通块(即不形成环) 则将这条边加入, 并将两个连通块合并 使用并查集进行连通块判定 O(mlogm + mα(m)) Bor?vkas algorithm Bor?vkas algorithm 类似Kruskal的多路增广版 一开始所有点为独立连通块 每一次: 每一个连通块寻找一条往外连接的最小权值边 将所有的这些边都加入 边权两两不同时可以保证不形成环 若边权有相同: (边权, 点标号)一起判最小 合并次数: 最坏情况logn次 时间复杂度: 最坏O( (m+n) logn ), 随机图 O(n+m) 最小瓶颈生成树(Minimum Bottleneck Spanning Tree) 一个无向图中权重最大的边最小 算法一: Kruskal的最后一条边就是瓶颈 定理: 任意 MST 一定是 MBST. Why? 所以任何MST的算法均可. 注意MBST并不一定是MST 存在更好算法? 最小瓶颈生成树(Minimum Bottleneck Spanning Tree) 线性算法 类似 快排分治 查找第k小数 按照边权的集合，选择当前的瓶颈值V 寻找所有权值不超过V的边，构成子图 若子图连通, V是答案的上界, 继续在权值较小的部分寻找 若子图不连通, 按当前连通性进行缩点, 在权值较大部分寻找 时间复杂度: T(m) = O(m) + T(m/2) 时间复杂度O(n+m) 扩展: 最小瓶颈路径查询 Q个query 每次查询a, b两个点 输出a ~ b点之间的最小瓶颈路径的瓶颈值 算法: 先求生成树 在生成树上做RMQ维护 再扩展: 若加入动态修改边权? 动态树 次小生成树 求图的次小生成树 扩展: 严格次小生成树 次小生成树 先求出最小生成树MST 然后枚举不在MST上的边(u,v)，若将(u,v)替换掉MST上节点u与节点v之间权值最大的边，那么得到的生成树的权值为 w(MST)+w(u,v)-maxw(u,v) 取最小值即得到次小生成树。 用F[i,j]表示由节点i向上2j条边中边权的最大值，那么查询两点之间边权最大值可以在O(log n)时间内解决。 严格次小生成树 同最小生成树做法，但有略微不同。 先求出最小生成树MST 然后枚举不在MST上的边(u,v)，若将(u,v)替换掉MST上节点u与节点v之间权值最大的边，若这条边的权值与w(u,v)相同，那么替换后的树不可能成为严格次小生成树。所以我们要替换节点u与节点v之间边权严格次大的边，这样得到的树才有可能是严格次小生成树。 最小比率生成树 给定无向图G