Иерархия вложенных зон

Материал из WikiGrapp
Перейти к:навигация, поиск

Иерархия вложенных зон (Hierarchy of nested zones) — множество зон \,\{S_{i}\} управляющего графа таких, что выполняются следующие два условия:

(1) для любых двух зон иерархии либо их пересечение пусто, либо одна целиком содержится в другой;

(2) для любой зоны \,S существует такая зона иерархии \,S_i,что S\subseteq S_i и у \,S и \,S_i есть общая входная вершина.

Пусть F - обратная нумерация некоторого уграфа G , а Z — множество всех его нетривиальных F-областей. Тогда Z - иерархией вложенных зон уграфа G.

Для каждой зоны S \in Z рассмотрим ее уровень h(S), равный нулю, когда  B(S) = \{S' \in Z : S'\subset S\}=\empty , и равный \max\{h(S'): S' \in Z , S'\subset S\} + 1 , когда B(S) \neq \empty. Пусть r — максимальный уровень зон из Z, и пусть для любого i через Z_i обозначается множество всех таких S \in Z , что либо h(S)=i , либо h(S) < i и нет зон S' \in Z, что S \subset S'.

Тогда уграф G является регуляризуемым тогда и только тогда, когда G_0 = G, Z_1(G), Z_2(G),... , Z_r(G) является зонно-интервальным представлением уграфа G.

Частным случаем является иерархия вложенных контуров.

Литература

  • Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.