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

Префиксный граф ширины [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]