Префиксный граф ширины n: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Префиксный граф ширины </math>n<math>''' (''Prefix graph of width </math>n<math>'') - бесконтурный г...)
 
Нет описания правки
Строка 1: Строка 1:
'''Префиксный граф ширины </math>n<math>''' (''Prefix graph of width </math>n<math>'') -  
'''Префиксный граф ширины <math>n</math>''' (''[[Prefix graph of width n|Prefix graph of width <math>n</math>]]'') -  
бесконтурный граф с </math>n<math> входами </math>x_{1}, \ldots, x_{n}<math>и </math>n<math> выходами
[[бесконтурный орграф|бесконтурный граф]] с <math>n</math> [[вход|входами]] <math>x_{1}, \ldots, x_{n}</math>и <math>n</math> [[выход|выходами]]
</math>y_{1}, \ldots, y_{n}<math> удовлетворяющий условиям (здесь </math>span(v) =
<math>y_{1}, \ldots, y_{n}</math> удовлетворяющий условиям (здесь <math>span(v) = \{i| 1 \leq i \leq n</math> и <math>G</math> содержит [[путь]] из <math> x_{i}</math> в <math>v\}</math>):
\{i| 1 \leq i \leq n\mbox{ и } G\mbox{ содержит путь из } x_{i}\mbox{
в } v\}<math>):


1. Для </math>i = 1, \ldots, n<math> </math>span(y_{i}) = \{1, \ldots, i-1\}<math> (для </math>i =
1. Для <math>i = 1, \ldots, n</math> <math>span(y_{i}) = \{1, \ldots, i-1\}</math> (для <math>i =
1<math> это есть </math>\emptyset<math>).
1</math> это есть <math>\emptyset</math>).


2. Для всех </math>v \in V<math> </math>span(v)<math> либо пусто, либо представляет собой
2. Для всех <math>v \in V</math> <math>span(v)</math> либо пусто, либо представляет собой
"интервал" вида </math>\{s, \ldots, t\}<math> для некоторых </math>s<math> и </math>t<math>, </math>1 \leq s
"[[интервал]]" вида <math>\{s, \ldots, t\}</math> для некоторых <math>s</math> и <math>t</math>, <math>1 \leq s
\leq t \leq n<math>.
\leq t \leq n</math>.


3. Любые две вершины с общим потомком имеют различные множества
3. Любые две [[вершина|вершины]] с общим [[потомок вершины|потомком]] имеют различные множества
</math>span<math>.
<math>span</math>.
==Литература==
==Литература==
[WG'94]
[WG'94]

Версия от 18:20, 24 декабря 2009

Префиксный граф ширины [math]\displaystyle{ n }[/math] (Prefix graph of width [math]\displaystyle{ n }[/math]) - бесконтурный граф с [math]\displaystyle{ n }[/math] входами [math]\displaystyle{ x_{1}, \ldots, x_{n} }[/math]и [math]\displaystyle{ n }[/math] выходами [math]\displaystyle{ y_{1}, \ldots, y_{n} }[/math] удовлетворяющий условиям (здесь [math]\displaystyle{ span(v) = \{i| 1 \leq i \leq n }[/math] и [math]\displaystyle{ G }[/math] содержит путь из [math]\displaystyle{ x_{i} }[/math] в [math]\displaystyle{ v\} }[/math]):

1. Для [math]\displaystyle{ i = 1, \ldots, n }[/math] [math]\displaystyle{ span(y_{i}) = \{1, \ldots, i-1\} }[/math] (для [math]\displaystyle{ i = 1 }[/math] это есть [math]\displaystyle{ \emptyset }[/math]).

2. Для всех [math]\displaystyle{ v \in V }[/math] [math]\displaystyle{ span(v) }[/math] либо пусто, либо представляет собой "интервал" вида [math]\displaystyle{ \{s, \ldots, t\} }[/math] для некоторых [math]\displaystyle{ s }[/math] и [math]\displaystyle{ t }[/math], [math]\displaystyle{ 1 \leq s \leq t \leq n }[/math].

3. Любые две вершины с общим потомком имеют различные множества [math]\displaystyle{ span }[/math].

Литература

[WG'94]