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

Материал из WikiGrapp
Перейти к:навигация, поиск

Префиксный граф ширины \,n (Prefix graph of width \,n) — бесконтурный граф с \,n входами x_{1}, \ldots, x_{n} и \,n выходами y_{1}, \ldots, y_{n} удовлетворяющий условиям (здесь span(v) = \{i| 1 \leq i \leq n и \,G содержит путь из \,x_{i} в \,v\}):

1. Для i = 1, \ldots, n span(y_{i}) = \{1, \ldots, i-1\} (для \,i = 
1 это есть \emptyset).

2. Для всех v \in V\,span(v) либо пусто, либо представляет собой "интервал" вида \{s, \ldots, t\} для некоторых \,s и \,t, 1 \leq s
\leq t \leq n.

3. Любые две вершины с общим потомком имеют различные множества \,span.

Литература

  • Workshop. Herrsching, 1994 // Lect. Notes Comp. Sci., 1995, vol. 903.