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

Иерархия вложенных альтов (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,\dots ,G_r$ называется представлением уграфа $G$ в виде иерархии вложенных альтов $A$ (A-граф, A-представление уграфа $G$), если

• $G_0=G$,

• $G_r$--- тривиальный уграф и

• для любого $i$ уграф $G_i$получается из $G_{i-1}$ стягиванием в вершины всех внешних альтов относительно $\bigcup \{A_j:1\le j\le i\}$, где $A_j$--- множество всех внутренних альтов относительно $A\setminus \bigcup \{A_s:1\le s<j\}$.

Литература

[Касьянов/88]