Составители:
Рубрика:
Определение 6.1.Пусть задан алгоритм и G = (V, E) его
граф. Рассмотрим V
1
, . . . , V
k
— непересекающиеся подмножества
его вершин,
V =
k
[
i=1
V
i
, V
i
∩ V
j
= ∅, i 6= j, (6.1)
такие, что если u ∈ V
i
, v ∈ V
j
и существует дуга (u, v) ∈ E, то
i < j. В этом случае представление (6.1) называется параллель-
ной формой алгоритма, а множества V
1
, V
2
, . . . , V
k
— его ярусами.
Число k называется высотой параллельной формы; число |V
j
|
элементов множества V
j
называется шириной j-го яруса V
j
, а мак-
симальное из чисел |V
j
| — шириной параллельной формы.
Параллельная форма минимальной высоты называется макси-
мальной.
Высотой алгоритма называется высота максимальной парал-
лельной формы.
Ширина максимальной параллельной формы называется ши-
риной алгоритма.
Параллельная форма ширины 1 называется последовательной.
Максимальная параллельная форма называется канонической,
если через каждую вершину i-го яруса проходит путь длины i − 1.
На рис. 9 представлены неканоническая (слева) и каноническая
(справа) параллельные формы.
Рис. 9. Неканоническая и каноническая параллельные формы.
Отметим некоторые свойства графов параллельных форм:
1) никакие две вершины одного яруса не связаны дугой;
2) все дуги, входящие в вершины первого яруса, являются реб-
рами с одной вершиной (лежащей в первом ярусе);
50
Страницы
- « первая
- ‹ предыдущая
- …
- 47
- 48
- 49
- 50
- 51
- …
- следующая ›
- последняя »
