Википедия

Ярусно-параллельная форма графа: различия между версиями

Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[непроверенная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
м fix cat
мНет описания правки
Строка 1:
'''Ярусно-параллельная форма графа''' (ЯПФ) -— деление вершин ориентированного ациклического [[граф (математика)|граф]]а на перенумерованные подмножества <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> -— его '''номером''', количество вершин в ярусе -— его '''шириной'''. Количество ярусов в ЯПФ называется её '''высотой''', а максимальная ширина её ярусов -— '''шириной ЯПФ'''.
 
Для ЯПФ [[граф алгоритма|графа алгоритма]] важным является тот факт, что операции, которым соответствуют вершины одного яруса, не зависят друг от друга, и поэтому заведомо существует параллельная реализация [[алгоритм]]а, в которой они могут быть выполнены параллельно на разных устройствах [[ЭВМ|вычислительной системы]]. Поэтому ЯПФ [[граф алгоритма|графа алгоритма]] может быть использована для подготовки такой параллельной реализация [[алгоритм]]а.
Источник — https://ru.wikipedia.org/wiki/Ярусно-параллельная_форма_графа