Представление горочной горловины в виде бинарного дерева

Основные понятия о древовидных графах

Моделью горочных горловин сортировочного парка является ориентированное бинарное дерево D = (V, Е), где V – множество вершин, Е – множество дуг.

Дерево – связный граф, не имеющий циклов. Ориентированное дерево – связный орграф без циклов, в котором полустепень захода одной вершины равна 0 (корень дерева), а полустепени остальных вершин равны 1.

di(Vj) – полустепень захода – число дуг, которые входят в j-ю вершину: di(V1) = 0 (вершина V1 – корень дерева), di (Vj) = 1, j = 2-9 dо(Vj) – полустепень исхода – число дуг, которые выходят из j-й вершины. do(V1) =2, do (V2) = 1, do (V3) = 3, do (Vj) = 0, j = 5-9

Ориентированное бинарное дерево – это ориентированное дерево, в котором полустепени исхода всех вершин не превышают двух (do (Vj)£2).

Представление горочной горловины в виде бинарного дерева

Горочную горловину можно рассматривать как ориентированное бинарное дерево, если заменить кривые их тангенсами. Принято, что все дуги дерева горловины ориентированны слева направо (см. рис. 2.1).

Все вершины дерева горочной горловины делятся на 3 типа: ЦП – центр стрелочного перевода; ВУС – вершина угла поворота на спускной части горки; ВУП– вершина угла поворота на сортировочном пути. Эти вершины отличаются полустепенями исхода.

d_o(ЦП<) = 2 (противошерстный стрелочный перевод).

d_o(ЦП>) = 1 ( пошерстный стрелочный перевод).

d_o(ВУС) = 1.

d_o(ВУП) = 0 (собственно пути не рассматриваются как дуги).

Корень дерева–головной стрелочный перевод.

Различают правое и левое поддеревья

Рис. 2.1. Дерево горочной горловины

Для каждой группы вершин устанавливается своя нумерация: для ЦП – N={1¸99}, для ВУС –N={101¸199}, для ВУП –N={201¸299}. При этом порядок нумерации вершин отличается от горловин станций. Первоначально все точки спускной части горки (ЦП, и ВУС, исключая вершины ВУП на сортировочных путях), нумеруют последовательными номерами 1, 2, ...; при этом, головная стрелка, являющаяся корнем дерева, обязательно должна иметь номер 1. Затем номера всех вершин углов поворота на спускной части (ВУП) увеличиваются на 100.

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

Для представления дерева D в ЭВМ используются списки инцидентности вершин и дуг. Для каждой вершины в списке указывают конечные вершины исходящих дуг V®U. Для того, чтобы различать две исходящих дуги, введено понятие левой и правой дуги (V®Uп, V®Uл). Это необходимо, потому что для симметричных стрелок, в отличие от обыкновенных, нельзя указать прямой и боковой пути.

Принято, что левой является конечная вершина Uл дуги, исходящей из вершины V и отклоняющейся от направления заходящей дуги против часовой стрелки (см. рис 2.2).

Рис. 2.2.

Ниже приведены списки инцидентности для горочной горловины, схема которой показана на рис. 2.3

Рис. 2.3.

v	uл	uп

2.2.1. Численные параметры плана горочной горловины

Списки инцидентности полностью описывают структуру плана горочной горловины, однако не содержат необходимых геометрических размеров. Поэтому каждой вершине дерева V ставится в соответствие вектор параметров Х, необходимых для расчета плана горочной горловины:

ХV=(a⁰, a¢, a², l _л, l _п, R, y),

где l_л, l_п – прямая часть дуги ордерева, исходящей из V, соответственно, в левом и правом направлениях (прямая вставка).

a – угол поворота кривой в точке V в градусах a^o, минутах a¢ и секундах a²;

R-радиус кривой;

y- признак включения длины кривой k_a в заданную длину исходящей дуги орграфа l _л или l _п. Если y = 0, то длина кривой k_a не включается в длину l_л (l_п) и прямая вставка f =l_л (или f =l_п). Если же y = 1, то длина прямой вставки f будет уменьшена на длину кривой k_a (f =l_л - k_a или f =l_п - k_a).

Следует заметить, что если вершина V является стрелочным переводом (V_ЦП), то среди компонентов вектора Х ненулевыми являются только длины l _л и/или l _п. Если же вершина V является вершиной угла поворота на спускной части горки (V_ВУС), то из двух величин (l _л и l _п.) только одна может быть ненулевой (выбор зависит от направления угла поворота кривой). Если угол поворота кривой неизвестен, то принимается a⁰=0, a¢=0, a²=0; нужно заметить, что на каждом маршруте от головной стрелки до сортировочного пути не должно быть более одного неизвестного угла поворота кривой a.

Ниже приведены списки инцидентности вершин дерева, дополненные векторами параметров ХV, для горочной горловины, схема которой показана на рис. 2.3