支配树

[giscus[bot]]

支配树

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

https://oi.wiki/graph/dominator-tree/

[sunyuheng365]

定理1的 $sdom(u)=\min({v|\exists v \rightarrow u, v < u) } \cup {sdom(w) | w > u\ and\ \exists w \rightarrow \dots \rightarrow v \rightarrow u })$ 中第二个集合中
$w \rightarrow \dots \rightarrow v \rightarrow u$ 这里 $v$ 和第一个集合中 $v$ 毫无关联，是否应该去掉

定理2 证明中 $x$ 未定义，是 $s \rightarrow u$ 任意路径中最后一个编号小于 $sdom(u)$ 的 $x$ ？

定理3 $T$ 上从 $sdom(u)$ 到 $u$ 的路径上的所有节点中 sdom 最小的节点 $v$

[AtomAlpaca]

定理一中的 $v$ 是为了将直接的前驱和间接的祖先区分开;

定理二的证明确实存在错误, 应为
令 $v$ 为 $P$ 中最后一个满足 $v < sdom(u)$ 的节点;

定理三的叙述确实存在错误.

以上错误稍后会进行修正, 感谢您的贡献.

[DingDongCat]

定理2和定理3的证明是不是有些逻辑混乱，参考了一下这篇博客https://www.cnblogs.com/meowww/p/6475952.html

[only52607]

在数据流迭代法中，初始状态应该是：除了根节点外，其他节点的初始支配点集为图中的所有节点。文章中似乎没有提及。

[qz-i]

可以认为引理 9是伪证吗？事实上，使 dfs 序较小到较大转移的只有前向边，所以第一次转移一定会转移到 sdom(u) 的子树上的某点。从这点再转移的过程中，还是因为使 dfs 序较小到较大转移的只有前向边，所以不管怎么走都是在 sdom(u) 的子树中折腾。（因为，如果通过横叉边或反向边走到了 sdom(u) 的子树以外，走到的这个点的 dfs 序就会小于 sdom(u) 进而小于 u 了。）

[AtomAlpaca]

横插边也可以使 dfs 序从小到大转移啊。

[qz-i]

这个叫前向边……一定是祖先到孩子；如果横叉边从小到大，那当初这条边为什么没有变成树边就值得思考了

[ppolariss]

if (tmp.count() == 1 and tmp[u]) 这里是错的，tmp[u]一定为true，判断条件应该是if (tmp.count() == 1 and dom[u][v])
举个例子，比如2和3都是1的子节点，这里会把2当成3的直接支配节点

[NtLazy]

求支配点的定理 1 的第三段的一处 $\LaTeX$ 挂了

[Lampese]

那好像是一个\setminus不是挂了