Нумерация событий в сетевом графике

При построении сетевых графиков желательно выдерживать последовательность в нумерации событий от исходного к завершающему. Это значительно упрощает их анализ и расчеты, а также обработку на ЭВМ.

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

Понятие «ранг» вводится для того, чтобы объединить в отдельные группы события по признаку одинаково максимального числа дуг путей, соединяющий данное событие с нулевым. События, сгруппированные по рангам, легко пронумеровать таким образом, чтобы для любой работы номер начального события был меньше номера конечного события.

Метод вычеркивания дуг состоит в следующем. Прежде всего отыскиваем событие, не имеющее ни одной входящей дуги, ему присваивается ранг 0. затем на графике вычеркиваются все дуги, выходящие из события с рангом 0. в результате одно или несколько событий могут оказаться без входящих дуг. Всем им присваивается 1-й ранг. Для любого из этих событий максимальное число дуг пути, соединяющего их с событиями нулевого ранга, равно 1. после вычеркивания всех дуг, выходящих из события 1-го ранга, получают вновь некоторое количество событий без входящих дуг. Их называют событиями 2-го ранга. Максимальное число дуг путей, соединяющих эти события с событиями нулевого ранга, равно 2. событию присваивается i-й ранг, если максимальное число дуг пути, соединяющего данное событие с событием нулевого ранга, равно i.

После распределения всех событий по рангам их нумеруют следующим образом. Единственное событие нулевого ранга получает номер 0. Событие 1-го ранга в произвольном порядке получают номера от 1 до n₁, где n₁ – число событий 1-го ранга. События 2-го ранга получают номера от n₁+1 до n₁+ n₂, где n₂ – число событий 2-го ранга и т.д.

Не нашли, что искали? Воспользуйтесь поиском: