ВУЗ:
Составители:
Рубрика:
Рис. 1.28 Преобразование графа (рис. 1.26) в глубину
Необходимо отметить, что так как вершина 7
(6)
находится за чертой допустимости (это показа-
но в табл. 1.4 пунктирной линией), то вершина 8
(3)
вносится в начало списка, но за пунктирную чер-
ту. Вершина 7 (рис. 1.26) стала теперь выше предельного уровня и подлежит раскрытию в первую
очередь.
Аналогичными приемами осуществляются поиски оптимальных путей на графах и при других
алгоритмах. При этом всегда в конечном итоге граф преобразуется в дерево, т.е. граф без циклов.
2 СЕТЕВЫЕ ЗАДАЧИ
2.1 Основные понятия
Сетью называется граф, каждая вершина которого представляет работу (событие), а дуги – порядок
выполнения работ. При этом каждая работа (вершина) характеризуется временем (продолжительно-
стью) выполнения работы.
Сеть удобно изображать в виде, представленном на рис. 2.1. Здесь кружочками обозначаются рабо-
ты, цифры в кружочках обозначают продолжительность выполнения работы, стрелки – последователь-
ность. Цифры i = 1, 2, 3, 4, 5, 6 обозначают номера (названия) работ.
Отношения между работами обозначаются знаками " ", " ". Так i j обозначает, что работа i
предшествует работе j, т.е. работа i выполняется раньше, чем работа j; работа j выполняется позже ра-
боты i.
Знак " " обозначает непосредственное следование работ. Так i j обозначает, что работа i непо-
средственно предшествует работе j (рис. 2.2) или работа j непосредственно следует за работой i.
Рис. 2.1 Граф последовательности выполнения работ – сеть
Рис. 2.2 Непосредственное предшествование работ
i j
6
125
25
18
31
0
1
2 4
3
5
6
Страницы
- « первая
- ‹ предыдущая
- …
- 23
- 24
- 25
- 26
- 27
- …
- следующая ›
- последняя »
