7
правок
Prefix graph: различия между версиями
Материал из WikiGrapp
нет описания правки
Glk (обсуждение | вклад) (Новая страница: «'''Prefix graph''' --- префиксный граф. For all <math>n \in N</math>, a ''' prefix graph''' of width <math>n</math> is a directed acyclic graph <math…») |
ALEXM (обсуждение | вклад) Нет описания правки |
||
| Строка 6: | Строка 6: | ||
<math>y_{1}, \ldots, y_{n}</math> of outdegree zero and with the following | <math>y_{1}, \ldots, y_{n}</math> of outdegree zero and with the following | ||
properties, where the span of a vertex <math>v \in V</math>, <math>span(v)</math>, is | properties, where the span of a vertex <math>v \in V</math>, <math>span(v)</math>, is | ||
defined as <math>\{i: \; 1 \leq i \leq n\mbox{ and } G \mbox{ contains a | defined as <math>\{i: \; 1 \leq i \leq n\mbox{ and } G \mbox{ contains a path from }x_{i}\mbox{ to }v\}</math>: | ||
path from }x_{i}\mbox{ to }v\}</math>: | |||
(1) For <math>i = 1, \ldots, n</math>, <math>span(y_{i}) = \{1, \ldots, i-1\}</math> (for <math>i | (1) For <math>i = 1, \ldots, n</math>, <math>span(y_{i}) = \{1, \ldots, i-1\}</math> (for <math>i | ||
