Префиксный граф ширины n

Префиксный граф ширины </math>n[math]\displaystyle{ ''' (''Prefix graph of width }[/math]n[math]\displaystyle{ '') - бесконтурный граф с }[/math]n[math]\displaystyle{ входами }[/math]x_{1}, \ldots, x_{n}[math]\displaystyle{ и }[/math]n[math]\displaystyle{ выходами }[/math]y_{1}, \ldots, y_{n}[math]\displaystyle{ удовлетворяющий условиям (здесь }[/math]span(v) = \{i| 1 \leq i \leq n\mbox{ и } G\mbox{ содержит путь из } x_{i}\mbox{ в } v\}[math]\displaystyle{ ): 1. Для }[/math]i = 1, \ldots, n[math]\displaystyle{ }[/math]span(y_{i}) = \{1, \ldots, i-1\}[math]\displaystyle{ (для }[/math]i = 1[math]\displaystyle{ это есть }[/math]\emptyset[math]\displaystyle{ ). 2. Для всех }[/math]v \in V[math]\displaystyle{ }[/math]span(v)[math]\displaystyle{ либо пусто, либо представляет собой "интервал" вида }[/math]\{s, \ldots, t\}[math]\displaystyle{ для некоторых }[/math]s[math]\displaystyle{ и }[/math]t[math]\displaystyle{ , }[/math]1 \leq s \leq t \leq n[math]\displaystyle{ . 3. Любые две вершины с общим потомком имеют различные множества }[/math]span<math>.

Литература

[WG'94]