Понятие о пути

Предположим, что при составлении некоторого проекта (рис.6.2.) определено 7 событий: О, 1, 2, 3, 4, 5, 6, 7 и 10 связываю­щие их работы: (0,1),(0,2),(1,2),(1,4),(1,6),(2,3),(3,5),(4,5),(5,7),(6,5).

Необходимо упорядочить сетевой график.

Как следует из перечня работ, исходным событием сетевого графика является событие 0 (ему не предшествуют никакие рабо­ты), а завершающим — событие 7 (за ним не следует ни одна работа).

Полагая на сетевых графиках изменение времени слева направо, поместим событие 0 в левую часть графика, а событие 7 — в правую часть, разместив между ними промежуточные со­бытия в некотором порядке.

Построенный сетевой график удовлетворяет сформулирован­ным в разделе 3 правилам, предъявляемым к его построению.

Однако этот график не полностью упорядочен.

Упорядочение сетевого графика заключается в таком располо­жении событий и работ, при котором для любой работы предшест­вующее ей событие расположено левее и имеет меньший номер по сравнению с завершающим эту работу событием.

Другими словами, в упорядоченном сетевом графике все работы-стрелки направле­ны слева направо: от событий с меньшими номерами к событиям с большими номерами.

Разобьем условно сетевой график на несколько слоев (обводим их пунктирными линиями и обозначаем римски­ми цифрами).

Поместив в I слое начальное событие 0 (рис.5), мысленно вычеркнем из графика это событие и все выходящие из него работы - стрелки.

Тогда без входящих стрелок останется событие 1, образующее II слой.

Вычеркнув мысленно событие 1 и все выходящие из него работы, увидим, что без входящих стрелок остаются события 2, 4 и 6 которые образуют III слой.

Продолжая указанную процедуру, получим

IV слой с событиями 5 и 3,

V слой — с событием 5,

VI слой — с событием 7.

Теперь видим, что первоначальная нумерация событий не со­всем правильная: так, событие 5 лежит в V слое и имеет номер, меньший, чем событие 6 из предшествующего слоя.

Изменим нумерацию событий в соответствии с их расположе­нием на графике (рис.6.4.) и получим упорядоченный сете­вой график ¹), в котором над стрелками укажем продол­жительность соответствующих работ (в неделях).

Рис.6.4.

Одно из важнейших понятий сетевого графика — понятие пути.

Путь — любая последовательность работ, в которой конечное собы­тие каждой работы совпадает с начальным событием следующей за ней работы.

Среди различных путей сетевого графика наибольший интерес представляет полный путь — любой путь, начало которого совпадает с исходным событием сети, а конец — с завершающим.

¹) Порядок нумерации событий, расположенных в одном слое, принципиального значения не имеет, так что нумерация одно­го и того же сетевого графика может быть неоднозначной.