Алгоритмы обработки сетевого графика

Нумерация событий - неповторяющаяся.

Отсутствие циклов в сети – важное условие.

Алгоритм перенумерации событий.

Рассмотрим случай, когда события соединены как i,j так, что каждое i соединено n дугами со всеми остальными, из которых часть выходит из i, а часть входит в j. Каждому событию присвоим номер, равный числу дуг, входящих в событие. Легко убедиться в однозначности такой нумерации. Откуда следует сквозная нумерация 0,1,2, …, n

Алгоритм ранжирование и нумерация событий:

Рис. 6.5

Метод вычеркивания дуг рассмотрен нами выше.

Рис.6.6.Результат ранжирования методом вычеркивания дуг.

Для реальных больших сетей применяется алгоритм Форда.

Предварительный шаг:

Каждой вершине j ставят в соответствие число λ j = 0, а каждой дуге (i,j) ставим в соответствие число y ij = 1 (не меняется).

Общий ( q -ый) шаг:

Просматриваем все вершины сети в некотором порядке

(например 0,1,2…, n) и заменяем λ ^q-1 j, а новые числа λ ^q j ≥ λ ^{q -1} j по формуле:

λ ^q j = max { λ ^p i + y ij } (j =1,…,n; λ ^qo = 0),

ⁱ

где p равно q или q–1 в зависимости от того, просматрива-лась уже на q -ом шаге вершина i или еще не просматривалась.

Общий шаг повторяют пока на q-ом шаге останутся без изменений все λ ^q-1 j, тогда числа λ j (j =1,2,…, n) являются рангами вершин сети.

После распределения вершин по рангам их нумерация производится так, как рассмотрено выше.