Пусть уже построен сетевой график проекта. Приведем алгоритмы, позволяющие перенумеровать события (вершины) так, чтобы для любой работы (Pi, Pj) выполнялось неравенство i<j, что во многих задачах представляет существенное удобство.
Рассмотрим сначала частный случай, когда каждая пара событий Pi и Pj соединена либо дугой (Рi, Рj), либо дугой (Рj, Рi), так что каждое событие Рi, соединено точно n дугами со всеми остальными; из этих дуг часть выходит из Рi, а часть входит в Pj.
Каждому событию присвоим номер, равный числу дуг, входящих в это событие. Тогда, например, событие Р0, в которое не входит ни одна дуга, получит номер 0, а событие Рm, из которого не выходит ни одна дуга, получит номер n.
Легко убедиться в однозначности такой нумерации. Действительно, допустим противное, и пусть в Рi и Рj входит одно и то же число k дуг. Так как Рi и Рj соединены между собой, например, дугой (Рi, Рj), то в Рj, кроме дуги (Pi, Pj), входит еще k–1 дуг. Рассмотрим теперь все k дуг (Рi1, Рj),...,(Рik, Рj), входящие в Рj. Событие Рj соединено дугами с каждым из событий Рi1,..., Pik. Среди этих дуг найдется хотя бы одна, пусть (Рj, Рiv), выходящая из Рj, так как в противном случае получили бы, что в Рj входит больше чем k дуг (дуги (Рi1, Рj),...,(Pik, Рj) и (Рi, Рj)). Остается лишь заметить, что дуги (Рiv, Рj), (Рi, Рj) и (Рj, Рiv) образуют цикл вопреки предположению об отсутствии циклов в сети.
Из однозначности нумерации следует, что среди n+1 событий существует одно, содержащее точно одну входящую дугу, одно, содержащее точно две входящие дуги и т.д., одно, содержащее точно п входящих дуг, так что события получат сквозную нумерацию 0, 1,..., (n).
Эту же нумерацию можно получить следующим образом (метод вычеркивания дуг). Начинаем просмотр сети с события Р0, которому присваиваем номер 0. Вычеркиваем все дуги, выходящие из Р0, и единственному событию, лишенному входящих дуг, присваиваем номер 1. Вычеркиваем затем все дуги, выходящие из Р1 и единственному событию, лишенному входящих дуг, присваиваем номер 2 и т.д.
Убедимся, что этим алгоритмом каждому событию присваивается номер, равный числу дуг, входящих в это событие.
Действительно, после нулевого шага, вычеркнув все n выходящих из Р0 дуг, мы в каждом из оставшихся n событий вычеркнули этим по одной входящей дуге и получили одно событие Р1 без входящих дуг, так что этому событию присвоен номер 1, равный числу входящих в него дуг. После первого шага, вычеркнув все n–1 дуг, выходящих из Р1, мы в каждом из оставшихся n–1 событий вычеркнули уже по две входящие дуги и получили одно событие Р2 без входящих дуг, так что этому событию присвоен номер 2, равный числу входящих в него дуг, и т.д.
Нетрудно показать, что номер каждого события равен максимальному числу дуг пути, соединяющего это событие с Р0.
Рассмотренный частный случай редко встречается на практике. Наиболее общей является ситуация, когда каждое событие соединено лишь с некоторыми из остальных, т.е. сеть не сильно разветвлена (рис. 13).
В этом случае, если вычеркнуть все дуги, выходящие из события Р0, которому присваиваем ранг 0, может случиться, что несколько событий окажутся без входящих дуг (на рис. 13 таковы события Р1 и Р6). Будем называть эти события событиями первого ранга. Максимальное число дуг пути, соединяющего Р0 с любым из них, равно единице.
P
P2
Рис. 13. Исходная сеть
Вычеркнув все дуги, выходящие из событий первого ранга, получим ряд событий без входящих дуг, которые назовем событиями второго ранга. Каждое событие второго ранга обязательно соединено с Р0 посредством некоторого события первого ранга, т.е. путем, состоящим из двух дуг. Хотя некоторые события второго ранга могут быть, кроме того, соединены с Р0 непосредственно, т.е. путем, состоящим из одной дуги, но максимальное число дуг пути из Р0 в любое событие второго ранга всегда равно двум, и это характеризует события второго ранга.
Вообще, если максимальное число дуг пути, соединяющего данное событие с Р0, равно l, то это — событие 1-го ранга.
Таким образом, все события сети единственным образом распределяются по рангам.
Нумерацию событий произведем так. Единственному событию Р0 нулевого ранга присвоим номер 0. Событиям первого ранга присвоим в произвольном порядке номера 1, 2,…, k1 событиям второго ранга присвоим номера k1+1,..., k1+k2 и т д. Так как события одного ранга между собой не соединены, а события меньшего ранга имеют меньший индекс, то в пронумерованной сети для любой дуги (Рi, Рj) всегда i<j.
Рассмотрим способ нумерации событий на примере рис 13. Событие Р0 — нулевого ранга. Вычеркнем выходящие из него дуги (Р0, Р1), (Р0, Р5), (Р0, Р6). События Р1 и Р6 останутся без входящих дуг. Это — события 1-го ранга. Вычеркнув дуги (Р1, Р2), (Р1, Р7), (Р1, Р5), (Р6, Р4) и (Р6, Р5), получим одно событие Р5 без входящих дуг; оно — событие 2-го ранга. Аналогично Р4 и Р7 — события 3-го ранга, Р2 — события 4-го ранга, Р3 — события 5-го ранга. Сеть упорядочена рангами. События внутри ранга равноценны в том смысле, что им можно присваивать номера в любом порядке. В рассматриваемом примере события Р1 и Р6 относятся к первому рангу. Порядковые номера, которые им нужно присвоить, 1 и 2 (так как Р0 имеет номер 0). Присвоим событию P1 номер 1, а Р6 — номер 2. Следующее событие Р5 — второго ранга. Его порядковый номер 3. События Р4 и Р7 получат соответственно номера 4 и 5, Р2 — номер 6, и, наконец, событие Р3 получит номер 7. Пронумерованная сеть изображена на рис. 14.
Рис. 14. Упорядоченная сеть
При больших сетях удобно пользоваться следующим алгоритмом Форда, являющимся основным алгоритмом решения не только задачи нумерации событий, но и некоторых других задач.
Предварительный шаг. Каждой вершине Рj ставят в соответствие число l(0)j=0, а каждой дуге (Рi, Рj) ставят в соответствие число уij=1, (которое не меняется на протяжении всего алгоритма).
Общий (q-й) шаг. Просматривают все вершины сети в каком-нибудь порядке, например, Р0, P1,..., Рn, и заменяют числа l(q–1)j, вычисленные на предыдущем шаге, на новые числа l(q)j>l(q–1)j по формуле (2.1):
(2.1)
где р равно q или q–1 в зависимости от того, просматривалась ли уже на q-м шаге вершина Р или еще не просматривалась. На каждом шаге можно рассматривать все вершины в произвольном порядке.
Повторяют общий шаг до тех пор, пока на очередном q-м шаге останутся без изменения все l(q-1)j. Тогда числа
(2.2)
являются рангами соответствующих вершин сети.
Чтобы убедиться в этом, достаточно выяснить смысл чисел l(q)j, получаемых на q-м шаге приведенного алгоритма. Оказывается l(q)j равно максимальному числу дуг цепочки, входящей в Рd, обнаруженной на q-м шаге.
Действительно, рассмотрим какую-нибудь вершину Pj (j¹0). На q-м шаге мы для нее получим:
где из всех вершин Рi, соединенных с Рj одной дугой, входящей в Рj, выбрана та вершина Рi1 для которой соответствующее число l(p)i1 оказалось наибольшим; при этом р равно q, если на q-м шаге вершина Рi1 уже просматривалась, и р=q–1, если еще не просматривалась, т.е.
Аналогично при l(p)i1¹0 найдем, что либо
где r равно q или q–1, либо
где s равно q–1 или q–2. Подставляя в l(q)j, получим
где t равно q или q–1, или q–2.
Этот процесс выделения цепочки дуг (Рi1, Рj), (Pi2, Pj1), ... можно продолжить до тех пор, пока не получим:
где l(v)ik=0. Но l(v)ik может равняться нулю только в следующих двух случаях: либо при ik=0, и тогда l(q)j — число дуг цепочки, соединяющей Р0 с Pj, либо при v=0, и тогда l(q)j — число дуг цепочки, соединяющей Pi1 c Pj.
Таким образом, l(q)j равно числу дуг цепочки, входящей в Рj. Максимальность же этого числа дуг следует из выбора вершин Pi1, Pi2,..., Pik (по формуле (2.1)).
На следующем (q+1)-м шаге либо будет обнаружена более длинная цепочка, либо будет удлинена данная (при ik¹0), либо l(q+1)j окажется равным l(q)j. Однако последнее еще не является признаком равенства l(q+1)j=l(q)j= I*j, так как другие l(q+1)k (k¹j) могли измениться по сравнению с l(q)k, следовательно, возможно в дальнейшем удлинение какой-нибудь из цепочек, входящих в Рj. Алгоритм закончен лишь тогда, когда l(q+1)j=l(q)j для всех j=1, 2,..., n, т.е. когда для каждой вершины Рj нельзя удлинить ни одну из цепочек, входящих в эту вершину (так как все они начинаются в Р0).
После распределения вершин по рангам их нумерация производится так, как в предыдущем методе вычеркивания дуг.
Проиллюстрируем применение алгоритма на рассмотренном выше примере (рис. 13).
Предварительный шаг. Полагаем
Первый шаг. Просматриваем вершины сети, например, в порядке Р0, P1,..., Р7. В вершину Р1 входит лишь одна дуга (Р0, Р1), поэтому
В вершину Р2 входят две дуги (Р1,Р2) и (Р7, Р2), поэтому
Аналогично
Второй шаг. Производим просмотр, например, с конца сети. Получим:
После третьего шага, в котором просмотр производился с начала сети, получаются следующие значения для Ij:
Наконец, на четвертом шаге не меняется ни одно l(3)j, т.е.
Таким образом, получаем следующее распределение вершин сети по рангам:
Р0 — вершина нулевого ранга,
P1,P6 — вершины первого ранга,
Р5 — вершина второго ранга,
Р4, Р7 — вершины третьего ранга,
Р2 — вершина четвертого ранга,
Р3 — вершина пятого ранга.
Затем всем вершинам присваиваем номера так, как это сделано выше.
Пронумерованная сеть — это сеть, вершины которой пронумерованы так, что для любой дуги (Рi, Рj) имеет место i<j.
(2.1)
(2.2)
