Ярусно-параллельная форма графа

Ярусно-параллельная форма графа (ЯПФ) — деление вершин ориентированного ациклического графа на перенумерованные подмножества ${\displaystyle V_{i}}$ такие, что, если дуга ${\displaystyle e}$ идет от вершины ${\displaystyle v_{1}\in V_{j}}$ к вершине ${\displaystyle v_{2}\in V_{k}}$, то обязательно ${\displaystyle j<k}$.

Каждое из множеств ${\displaystyle V_{i}}$ называется ярусом ЯПФ, ${\displaystyle i}$ — его номером, количество вершин ${\displaystyle \left|V_{i}\right|}$ в ярусе — его шириной. Количество ярусов в ЯПФ называется её высотой, а максимальная ширина её ярусов — шириной ЯПФ.

Для ЯПФ

Если в составе яруса могут быть вершины, находящиеся в различных отношениях (например, параллельности или альтернативы, что типично для граф-схем параллельных алгоритмов), ярус называется сечением, а ЯПФ — множеством сечений. Наличие более одного отношения между вершинами сечения существенно усложняет большинство алгоритмов обработки ^[1][2].

См. также топологическая сортировка.

Это заготовка статьи по информатике. Помогите Википедии, дополнив её.