括号定理
在对一个(有向或无向)图G=(V,E)的任何深度优先搜索中,对于途中任意两个顶点u和v,下述三个条件中仅有一个成立:
1.区间[d[u],f[u]]和区间[d[v],f[v]]是完全不相交的,且在深度优先森林中,u或v都不是对方的后裔
2.区间[d[u],f[u]]完全包含于区间[d[v],f[v]]中,且在深度优先树中,u是v的后裔
3.区间[d[v],f[v]]完全包含于区间[d[u],f[u]]中,且在深度优先树种,v是u的后裔
在对一个(有向或无向)图G=(V,E)的任何深度优先搜索中,对于途中任意两个顶点u和v,下述三个条件中仅有一个成立:
1.区间[d[u],f[u]]和区间[d[v],f[v]]是完全不相交的,且在深度优先森林中,u或v都不是对方的后裔
2.区间[d[u],f[u]]完全包含于区间[d[v],f[v]]中,且在深度优先树中,u是v的后裔
3.区间[d[v],f[v]]完全包含于区间[d[u],f[u]]中,且在深度优先树种,v是u的后裔