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

Алгоритм получения правильной нумерации вершин

Упорядочение сетевого графика

Пример: Пусть при составлении некоторого проекта выделено 12 событий: 0,1,2,3,4,5,6,7,8,9,10,11 и 24 связывающих их работы: (0,1), (0,2), (0,3), (1,2), (1,4), (1,5), (2,3), (2,5), (2,7), (3,6), (3,7), (3,10), (4,8), (5,8), (5,7), (6,10), (7,6), (7,8), (7,9), (7,10), (8,9), (9,11), (10,9), (10,11). Необходимо составить и упорядочить сетевой график.

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

Нумеруют все начальные вершины.
Вычеркивают все дуги, выходящие из начальных вершин. При этом получают новые начальные вершины. Переходят к шагу 1.

Процесс повторяют до тех пор, пока все вершины не будут пронумерованы. Конечная вершина получает при этом наибольший номер.

Путь – любая последовательность работ, в которой конечное событие каждой работы совпадает с начальным событием следующей за ней работы. Полный путь L – любой путь, начало которого совпадает с исходным событием сети, а конец с завершающим. Продолжительность пути определяется суммой продолжительностей составляющих его работ. Полный путь, имеющий максимальную продолжительность во времени, называют критическим (обозначают ). Критическими называются также работы и события, расположенные на этом пути. Суммарная продолжительность операций, принадлежащих критическому пути, составляет критическое время выполнения комплекса операций в целом. На графике критический путь, как правило, выделяют жирной линией.