Составители:
Рубрика:
ваются максимальными). При последовательности максимальных
отбрасываний начало любого пути может встретиться только на
первом шаге операции. Это означает, что на каждом шаге опера-
ции (за исключением последней) обязательно отбрасывается строго
одна дуга критического пути графа. Этот путь не может закончить-
ся раньше завершения всех отбрасываний, ибо тогда он не был бы
критическим путем графа. Это означает, что число отбрасываний
(вместе с последним) в точности на единицу больше длины крити-
ческого пути графа.
Следствие 3.3. Для любого натурального числа s, s
n
≤ s ≤
n, существует такая разметка вершин графа, при которой ис-
пользуются все s индексов.
Д о к а з а т е л ь с т в о легко вытекает из следствий 3.1 и 3.2.
Определение 3.1. Разметка вершин графа, удовлетворяю-
щая условиям теоремы 3.2, называется сортировкой графа.
Определение 3.2. Разметка вершин графа, проведенная при
максимальных операциях отбрасывания, называется топологиче-
ской сортировкой графа.
Нетрудно заметить следующее.
1. При топологической сортировке все пути могут начинаться
лишь в вершинах с индексом k; вершины с индексом k > 1 не могут
служить началом пути.
2. При сортировке вершина с индексом k > 1 может являться
концом пути длины не более k − 1.
3. При топологической сортировке в вершине с индексом k > 1
могут заканчиваться лишь пути длины k − 1.
4. При топологической сортировке число используемых индек-
сов на единицу больше длины критического пути графа.
Определение 3.3. Топологическая сортировка называется
линейной, если индексы любых вершин различны; в этом случае
говорят, что граф линейно упорядочен.
Замечание. Если топологическая сортировка не является ли-
нейной, то из нее можно получить другие сортировки с б´ольшим
числом индексов.
Д о к а з а т е л ь с т в о этого замечания очевидно.
§ 4. Примеры графов параллельных форм
Рассмотрим процесс вычисления выражения (a
1
a
2
+
a
3
a
4
)(a
5
a
6
+ a
7
a
8
) и построим для него графы нескольких
45
Страницы
- « первая
- ‹ предыдущая
- …
- 42
- 43
- 44
- 45
- 46
- …
- следующая ›
- последняя »
