1294
правки
Иерархия вложенных зон: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 3: | Строка 3: | ||
(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>. | |||
Частным случаем является ''[[иерархия вложенных контуров]]''. | Частным случаем является ''[[иерархия вложенных контуров]]''. | ||
| Строка 10: | Строка 16: | ||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | * Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | ||
[[Категория: Сводимые и регуляризуемые графы]] | |||