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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Иерархия вложенных альтов''' (Hierarchy of nested alts)--- множество нетривиальных [[...)
 
Нет описания правки
Строка 11: Строка 11:
существует альта, в который <math>H_{i}</math>непосредственно вложен.
существует альта, в который <math>H_{i}</math>непосредственно вложен.


Последовательность уграфов <math>G_{0}, \; G_{1}, \; \ldots, \;
Последовательность уграфов <math>G_{0}, \; G_{1}, \; \ldots, \; G_{r}</math> называется представлением [[Уграф |уграфа]] <math>G</math> в виде '''иерархии вложенных альтов''' <math>A</math> ([[A-граф|''A-граф'']], [[A-представление уграфа|''A-представление уграфа'']] <math>G</math>), если  
G_{r}</math>называется представлением уграфа <math>G</math> в виде иерархии
 
вложенных альтов <math>A</math> ([[A-граф|''A-граф'']], [[A-представление уграфа|''A-представление уграфа'']] <math>G</math>), если <math>G_{0} = G</math>, <math>G_{r}</math>--- [[Тривиальный граф|тривиальный]] уграф и для любого <math>i</math> уграф <math>G_{i}</math>получается
* <math>G_{0} = G</math>,  
из <math>G_{i-1}</math> стягиванием в вершины всех внешних альтов
 
относительно <math>\bigcup \{A_{j} : \; 1 \leq j \leq i \}</math>, где
* <math>G_{r}</math>--- [[Тривиальный граф|тривиальный]] уграф и  
<math>A_{j}</math>--- множество всех внутренних альтов относительно <math>A
 
\setminus \bigcup \{A_{s}: \; 1 \leq s < j\}</math>.
* для любого <math>i</math> уграф <math>G_{i}</math>получается из <math>G_{i-1}</math> стягиванием в вершины всех внешних альтов относительно <math>\bigcup \{A_{j} : \; 1 \leq j \leq i \}</math>, где <math>A_{j}</math>--- множество всех внутренних альтов относительно <math>A\setminus \bigcup \{A_{s}: \; 1 \leq s < j\}</math>.


==Литература==
==Литература==
{[Касьянов/88]}
{[Касьянов/88]}

Версия от 22:12, 4 мая 2009

Иерархия вложенных альтов (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{ 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].

Литература

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