этом случае естественная возрастающая нумерация узлов на той
ветви, по которой мы двигаемся, не нарушается. Если же, очередной
узел является точкой ответвления и узлы каких-либо других про-
ходящих через него ветвей не пронумерованы, то мы его пока не
нумеруем, а следующий номер натурального ряда присваиваем ко-
нечной точке любой из этих ветвей, узлы которой еще не пронуме-
рованы. Затем от этой конечной точки будем двигаться в обратную
сторону по ветви, нумеруя встречающиеся узлы по тем же прави-
лам. Таким образом, узел, являющийся точкой ответвления, не по-
лучит номера до тех пор, пока не будут пронумерованы узлы всех
ветвей, исходящих из него.
Узел, являющийся точкой ответвления (узел ветвления), отли-
чается от других тем, что в нем нарушается естественная ну мерация.
Очевидно, что при таком способе нумерации мы не пропустим ни
один узел и все их пронумеруем, пока не дойдем до базисной точки,
являющейся корнем дерева. При этом базисная точка получит наи-
больший номер, равный числу узлов в сети.
На рис. Х1\.3 показан пример нумерации узлов кольцевой сети
по приведенным правилам. Все независимые линии сети, которые
мы отбрасываем при построении дерева, показаны на рисунке штри-
ховыми линиями, а зависимые линии, образующие дерево, показаны
СПЛОШНЫМИ ЛИНИЯМИ.
Поясним, как проведена нумерация этой сети. Выберем за базис-
ный узел В. Концевой точке самой длинной ветви присвоим номер
1. Будем двигаться по выбранной ветви по направлению к узлу В.
Встречающиеся узлы ветви нумеруем возрастающими натуральными
числами. Таким образом будут пронумерованы узлы 2, 8, 4, 5, 6.
К узлу, стоящему на этой ветви за узлом 6, примыкают еще две вет-
ви — он является узлом ветвления, поэтому его пока не нумеруем,
а следующий номер 7 присваиваем концевому узлу первой из этих
ветвей. Идя по этой ветви от узла 7 в сбратном направлении, после-
довательно нумеруем узлы &, 9, 10. Мы опять дошли до узла вет-
вления, но нумеровать его еще не можем, так как осталась еще одна
ветвь, узлы которой пока не пронумерованы. Очередной узел этой
ветви — узел /9 — в свою очередь является узлом ветвления, К
которому примыкают две ветви. Процесс нумерации узлов начнем
с псследнего 11-го узла первой из этих ветвей. Нумеруем узлы от
И до 14 и, дойдя до узла ветвления 19, опять прерываем нумера-
цию. Следующий номер /5 присваиваем концевому узлу послед-
ней ветви. Двигаясь в обратном направлении по этой ветви, про-
нумеруем все узлы, в том числе узлы ветвления 19 и 20, которые
теперь можно нумеровать, так как все ветви, выходящие из НиХх,
уже пронумерованы. Базисная точка В получит максимальный
номер 21.
Чтобы ввести информацию о построенном дереве сети в ЭВМ, не-
обходимо задать таблицу нарушений натурального ряда в нумера-
ции узлов сети и число строк в этой таблице.
Таблица нарушений указывает, сколько раз и перед какими уз-
лами ветвления происходило нарушение естественной возрастающей
нумерации узлов из-за того, что узлы некоторых ветвей, ВЫХодяЯЩИх
253