Depth of a flow graph

Материал из WikiGrapp
Версия от 22:02, 11 сентября 2019; KVN (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

Depth of a flow graph --- глубина управляющего графа.

Given a depth-first spanning treefor a flow graph, the depth is the largest number of retreating edges on any cycle-free path. Here retreating edges are those going from a node m to an ancestor of m. It is interesting and useful fact that if the flow graph is reducible, then the retreating edges are exactly the back edges of the flow graph, independent of the order in which successors are visited. For any flow graph, every back edge is retreating, although, if the graph is nonreducible there will be some retreating edges that are not back edges.