Аноним

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

Материал из WEGA
нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Префиксный граф ширины <math>n</math>''' (''[[Prefix graph of width n|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) = \{i| 1 \leq i \leq n</math> и  <math>G</math> содержит [[путь]] из <math> x_{i}</math> в  <math>v\}</math>):
<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>):


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\,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]
* Workshop. Herrsching, 1994 // Lect. Notes Comp. Sci., 1995, vol. 903.