Prefix graph

Prefix graph --- префиксный граф.

For all [math]\displaystyle{ n \in N }[/math], a prefix graph of width [math]\displaystyle{ n }[/math] is a directed acyclic graph [math]\displaystyle{ G = (V,E) }[/math] with [math]\displaystyle{ n }[/math] distinguished input vertices [math]\displaystyle{ x_{1}, \ldots, x_{n} }[/math] of indegree zero and [math]\displaystyle{ n }[/math] distinguished output vertices [math]\displaystyle{ y_{1}, \ldots, y_{n} }[/math] of outdegree zero and with the following properties, where the span of a vertex [math]\displaystyle{ v \in V }[/math], [math]\displaystyle{ span(v) }[/math], is defined as [math]\displaystyle{ \{i: \; 1 \leq i \leq n\mbox{ and } G \mbox{ contains a path from }x_{i}\mbox{ to }v\} }[/math]:

(1) For [math]\displaystyle{ i = 1, \ldots, n }[/math], [math]\displaystyle{ span(y_{i}) = \{1, \ldots, i-1\} }[/math] (for [math]\displaystyle{ i = 1 }[/math] this is [math]\displaystyle{ \emptyset }[/math]).

(2) For all [math]\displaystyle{ v \in V }[/math], [math]\displaystyle{ span(v) }[/math] is either empty or an interval of the form [math]\displaystyle{ \{s, \ldots, t\} }[/math], for some integers [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math] with [math]\displaystyle{ 1 \leq s \leq t \leq n }[/math].

(3) Any two vertices in [math]\displaystyle{ V }[/math] with a common successor have disjoint spans.