683
правки
Иерархия вложенных альтов: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KVN (обсуждение | вклад) (Создана новая страница размером '''Иерархия вложенных альтов''' (Hierarchy of nested alts)--- множество нетривиальных [[...) |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 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]} | ||