Иерархия вложенных зон: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показаны 2 промежуточные версии 2 участников)
Строка 1: Строка 1:
'''Иерархия вложенных зон''' (''[[Hierarchy of nested zones]]'') - множество ''[[зона|зон]]'' <math>\{S_{i}\}</math> ''[[управляющий граф|управляющего графа]]'' таких, что выполняются следующие два условия:
'''Иерархия вложенных зон''' (''[[Hierarchy of nested zones]]'') множество ''[[зона|зон]]'' <math>\,\{S_{i}\}</math> ''[[управляющий граф|управляющего графа]]'' таких, что выполняются следующие два условия:


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


(2) для любой зоны <math>S</math> существует такая зона иерархии <math>S_i</math>,что <math>S\subseteq S_i</math> и у <math>S</math> и <math>S_i</math> есть общая входная [[вершина]].
(2) для любой зоны <math>\,S</math> существует такая зона иерархии <math>\,S_i</math>,что <math>S\subseteq S_i</math> и у <math>\,S</math> и <math>\,S_i</math> есть общая [[входная вершина фрагмента|входная вершина]].
 
Пусть F - [[обратная нумерация]] некоторого [[уграф|уграфа]] <math>G</math> , а <math>Z</math>  — множество всех его нетривиальных [[F-Область|F-областей]]. Тогда <math>Z</math> - '''иерархией вложенных зон''' уграфа <math>G</math>.
 
Для каждой зоны <math>S \in Z </math> рассмотрим ее уровень <math>h(S)</math>, равный нулю, когда <math> B(S) = \{S' \in Z : S'\subset S\}=\empty </math>, и равный <math>\max\{h(S'): S' \in Z , S'\subset S\} + 1 </math>, когда <math>B(S) \neq \empty</math>. Пусть <math>r</math> — максимальный уровень зон из <math>Z</math>, и пусть для любого <math>i</math> через <math>Z_i </math> обозначается множество всех таких <math>S \in Z </math>, что либо <math>h(S)=i </math>, либо <math>h(S) < i</math> и нет зон <math>S' \in Z</math>, что<math> S \subset S'</math>.
 
Тогда уграф <math>G</math> является [[Регуляризуемый граф|регуляризуемым]] тогда и только тогда, когда <math>G_0 = G, Z_1(G), Z_2(G),... , Z_r(G) </math> является [[зонно-интервальное представление|зонно-интервальным представлением]] уграфа <math>G</math>.


Частным случаем является ''[[иерархия вложенных контуров]]''.
Частным случаем является ''[[иерархия вложенных контуров]]''.
==Литература==
==Литература==
[Касьянов/88],
* Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
 
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
 


[Евстигнеев/85]
[[Категория: Сводимые и регуляризуемые графы]]

Текущая версия от 12:07, 17 сентября 2019

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

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

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

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

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

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

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

Литература

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