Префиксный граф ширины n: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 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 | 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>. | ||
==Литература== | ==Литература== | ||
* Workshop. Herrsching, 1994 // Lect. Notes Comp. Sci., 1995, vol. 903. | |||
Текущая версия от 16:33, 23 июня 2011
Префиксный граф ширины [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\,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].
Литература
- Workshop. Herrsching, 1994 // Lect. Notes Comp. Sci., 1995, vol. 903.