Ярусно-параллельная форма графа
Материал из Википедии — свободной энциклопедии
Ярусно-параллельная форма графа (ЯПФ) — деление вершин ориентированного ациклического графа на перенумерованные подмножества Vi такое, что, если дуга e идет от вершины 
к вершине 
, то обязательно j < k.
Каждое из множеств Vi называется ярусом ЯПФ, i — его номером, количество вершин в ярусе — его шириной. Количество ярусов в ЯПФ называется её высотой, а максимальная ширина её ярусов — шириной ЯПФ.
Для ЯПФ графа алгоритма важным является тот факт, что операции, которым соответствуют вершины одного яруса, не зависят друг от друга, и поэтому заведомо существует параллельная реализация алгоритма, в которой они могут быть выполнены параллельно на разных устройствах вычислительной системы. Поэтому ЯПФ графа алгоритма может быть использована для подготовки такой параллельной реализация алгоритма.
Минимальной высотой всех возможных ЯПФ графа является его критический путь. Построение ЯПФ с высотой, меньшей критического пути, невозможно.
