ВУЗ:
Составители:
35
Пометим любое число вершин графа, не имеющих предшествующих, еди-
ницей и удалим из графа эти вершины вместе с инцидентными им дугами. Ос-
тавшийся граф также ациклический. В нем любое число вершин, не имеющих
предшествующих, пометим индексом 2 и удалим их. Продолжим этот процесс
до исчерпания графа. Поскольку на каждом шаге помечается не менее одной
вершины, число индексов не превысит число вершин графа.
Нетрудно заметить, что, например, для графов, показанных на рис. 3.1 и
3.2, в обоих случаях n=7, а число s при этом принимает значения 4 и 3 соответ-
ственно. Из схемы разметки, в частности, следует:
- никакие две вершины с одинаковым индексом не связаны дугой;
- минимально число индексов на единицу больше длины критического пути;
- для любого целого s , не превосходящего числа вершин, но большего длины
критического пути, существует разметка, при которой используются все s
индексов.
Граф, размеченный в соответствии с описанной схемой, называют строгой па-
раллельной формой графа [2].
Существует строгая параллельная форма, в которой максимальная из длин
путей, оканчивающихся в вершине с индексом k, равна k -1, и все входные вер-
шины находятся в одной группе с индексом 1. Она называется канонической.
Для заданного графа каноническая форма единственна.
Группа вершин с одинаковыми индексами называется ярусом, число вер-
шин в группе – шириной яруса, а число ярусов – высотой параллельной формы.
Параллельная форма минимальной высоты называется максимальной, т.к. в ка-
ждом ярусе такой формы максимальное число вершин.
Предположим теперь, что все операции алгоритма выполняются за одина-
ковое время, равное 1, каждая операция может начаться в момент готовности ее
аргументов, а все операции, не имеющие предшествующих, могут выполняться
одновременно (параллельно). Обозначим момент начала реализации алгоритма
нулем, а каждой операции будем присваивать индекс, равный моменту оконча-
Страницы
- « первая
- ‹ предыдущая
- …
- 33
- 34
- 35
- 36
- 37
- …
- следующая ›
- последняя »
