Составители:
Рубрика:
17
Работы эти должны быть упорядочены во времени: естест-
венно, что крышу нельзя сооружать, пока нет фундамента и стен
и т.д. Построим граф, вершины которого (кружочки) означают
указанные работы, а дуги характеризуют упорядоченность работ
во времени. В графе есть один вход ― вершина 1 ― и один вы-
ход ― вершина 11 (рис. 1.2а).
Рисунок 1.2 ― Взаимосвязь работ при сооружении жилого дома:
a
― вершины графа – работы,
b
― дуги графа – работы
Поскольку строительство жилья носит массовый характер,
то время на проведение каждой работы, в общем-то, известно.
Поэтому каждой вершине графа можно приписать определенное
число ― время выполнения работы, ― а дуге, исходящей из
вершины
i
, ― минимально возможный срок окончания
i
-й рабо-
ты. Граф строится для того, чтобы определить кратчайший срок
окончания строительства.
Информацию о работах и их взаимосвязи можно передать
несколько другим способом (рис. 1.2b). Вершины графа – прямо-
1
5
8
2
3
4
6
7
9
10
3
11
а
I, 0
2
3
4
9
7
20
3
III, 20
IV, 20
VI, 20
0
II, 20
VII, 30
V, 27
0
VIII,30
X, 30
IX, 34
XI, 37
20
3
20
3
9
7
3
3
3
3
4
b
Страницы
- « первая
- ‹ предыдущая
- …
- 15
- 16
- 17
- 18
- 19
- …
- следующая ›
- последняя »
