Content #
括号化定理(Parenthesis theorem)。在对有向或无向图G=(V,E)进行的任意深度优先搜索中，对于任意两个结点u和v来说，三种情况中只有一种成立。
- 区间[u.d, u.f]与区间[v.d, v.f]完全分离，在深度优先森林中，彼此不是对方的后代。
- 区间[u.d, u.f]完全包含在区间[v.d, v.d]内，在深度优先树中，结点u是结点v的后代。
- 区间[v.d, v.f]完全包含在区间[u.d, u.d]内，在深度优先树中，结点v是结点u的后代。
括号化定理
August 6, 2022