一道有点疑惑的关于横叉边的简答题

题目：通过深度优先搜索算法生成有向图的DFS树，是否有可能存在横叉边数目等于Ω(n^2)的情况？

感觉网上横叉边的资料特别少。。。不知有没有朋友可以解答的？非常感谢！

考虑一个有n + 1个节点的有向图，其中

点集 V = { 0 .. n }
边集 E = { <0, t> | 1 <= t <= n } U { <s, t> | 1 <= t < s <= n }

也就是从0号点出发到其他点各添加一条边，然后其它点只有通往比自己小的节点的边。

那么如果DFS算法是按0 -> 1 -> ... -> n的顺序枚举节点，易知DFS树的高度只有2，也就是0号点为树根，1 .. n依次都是0号点的子节点。

cross edge的数量为0 + 1 + ... + (n - 1) = O(n^2)

magicsets 发表于 2020-1-27 06:42
考虑一个有n + 1个节点的有向图，其中

点集 V = { 0 .. n }

非常感谢回答！！所以cross edge最多只能是O(n^2)，不能是Ω(n^2)吗？还是说也可算作Ω(n^2)呢？

milkkkmillkk 发表于 2020-1-27 06:58
非常感谢回答！！所以cross edge最多只能是O(n^2)，不能是Ω(n^2)吗？还是说也可算作Ω(n^2)呢？

是的，最后一个累加式子的结果是n * (n - 1) / 2，准确来说是确界Θ(n^2)，其满足上界O(n^2)也满足下界Ω(n^2)