Depth of a flow graph: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Depth of a flow graph''' --- глубина управляющего графа. Given a ''depth-first spanning tree''for a ''flow graph'', the '''depth''' is t…»)
 
Нет описания правки
 
Строка 10: Строка 10:
retreating, although, if the graph is ''nonreducible'' there will be some
retreating, although, if the graph is ''nonreducible'' there will be some
retreating edges that are not back edges.
retreating edges that are not back edges.
[[Категория: Сводимые и регуляризуемые графы]]

Текущая версия от 21:26, 8 октября 2019

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 [math]\displaystyle{ m }[/math] to an ancestor of [math]\displaystyle{ m }[/math]. 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.