Patarakin: 1 версия импортирована

2022-10-19T07:30:50Z

1 версия импортирована

← Предыдущая версия	Версия от 10:30, 19 октября 2022
(нет различий)

ru_wikipedia>Uranix: отмена правки 104509019 участника 88.87.79.70 (обс.)

2020-01-18T12:11:48Z

отмена правки 104509019 участника 88.87.79.70 (обс.)

Новая страница

'''Ярусно-параллельная форма графа''' (ЯПФ) — деление вершин ориентированного ациклического [[граф (математика)|граф]]а на перенумерованные подмножества <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> — его '''номером''', количество вершин <math>\left| V_i \right |</math> в ярусе — его '''шириной'''. Количество ярусов в ЯПФ называется её '''высотой''', а максимальная ширина её ярусов — '''шириной ЯПФ'''.

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

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

Если в составе яруса могут быть вершины, находящиеся в различных [[бинарное отношение|отношениях]] (например, [[отношение параллельности|параллельности]] или [[отношение альтернативы|альтернативы]], что типично для [[Граф-схема алгоритма|граф-схем параллельных алгоритмов]]), ярус называется сечением, а ЯПФ — множеством сечений. Наличие более одного отношения между вершинами сечения существенно усложняет большинство алгоритмов обработки <ref>Организация и синтез микропрограммных мультимикроконтроллеров / И.В. Зотов, В.А. Колосков, В.С. Титов [и др.]. Курск: Изд-во «Курск», 1999. 368 с. ISBN 5-7277-0253-4</ref><ref>Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управления при проектировании логических мультиконтроллеров / Э.И. Ватутин, И.В. Зотов, В.С. Титов [и др.]. Курск: изд-во КурскГТУ, 2010. 200 с. ISBN 978-5-7681-0523-5.</ref>.

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

== Примечания ==
{{примечания}}

{{info-stub}}
{{Нет иллюстрации}}

[[Категория:Теория графов]]
[[Категория:Параллельные вычисления]]
[[Категория:Структуры данных]]

Ярусно-параллельная форма графа - История изменений

Patarakin: 1 версия импортирована

ru_wikipedia>Uranix: отмена правки 104509019 участника 88.87.79.70 (обс.)