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

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

Иерархия вложенных альтов (Hierarchy of nested alts) — множество нетривиальных альтов \,A = \{H_{i}\} управляющего графа таких, что для любых двух альтов либо их пересечение пусто, либо один целиком содержится в другом.

Альт H_{i} \in A непосредственно вложен в альт H_{j} \in A относительно \,A, если H_{i} \subset H_{j} и в \,A не существует такого альта \,H_{k}, что H_{i} \subset H_{k} \subset H_{j}.

Альт H_{i} \in A называется внутренним альтом относительно \,A, если в \,A не существует альтов, непосредственно вложенных в \,H_{i} и внешним альтом относительно \,A, если в \,A не существует альта, в который \,H_{i} непосредственно вложен.

Последовательность уграфов G_{0}, \; G_{1}, \; \ldots, \; G_{r} называется представлением уграфа \,G в виде иерархии вложенных альтов \,A (A-граф, A-представление уграфа \,G), если

  • \,G_{0} = G,
  • для любого \,i уграф \,G_{i} получается из \,G_{i-1} стягиванием в вершины всех внешних альтов относительно \bigcup \{A_{j} : \; 1 \leq j \leq i \}, где \,A_{j} — множество всех внутренних альтов относительно A\setminus \bigcup \{A_{s}: \; 1 \leq s < j\}.

Hierarchy of nested alts.png

Литература

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