基本介紹
- 中文名：括弧定理
- 名詞類型：學科定理
- 套用領域：電腦編程、數據結構
- 適用結構：樹
在對一個(有向或無向)圖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的後裔
