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

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

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

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

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

• [math]\displaystyle{ \,G_{0} = G }[/math],

• [math]\displaystyle{ \,G_{r} }[/math] — тривиальный уграф и

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

Литература

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