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

Ярусно-параллельная форма графа (ЯПФ) — деление вершин ориентированного ациклического графа на перенумерованные подмножества <math>V_i</math> такие, что, если дуга <math>e</math> идет от вершины <math>v_1 \in V_j</math> к вершине <math>v_2 \in V_k</math>, то обязательно <math>j < k</math>.

Каждое из множеств <math>V_i</math> называется ярусом ЯПФ, <math>i</math> — его номером, количество вершин в ярусе — его шириной. Количество ярусов в ЯПФ называется её высотой, а максимальная ширина её ярусов — шириной ЯПФ.

Для ЯПФ графа алгоритма важным является тот факт, что операции, которым соответствуют вершины одного яруса, не зависят друг от друга, и поэтому заведомо существует параллельная реализация алгоритма, в которой они могут быть выполнены параллельно на разных устройствах вычислительной системы. Поэтому ЯПФ графа алгоритма может быть использована для подготовки такой параллельной реализации алгоритма.

Минимальной высотой всех возможных ЯПФ графа является его критический путь. Построение ЯПФ с высотой, меньшей критического пути, невозможно.