Оптимальное размещение взаимосвязанных объектов на древовидных сетях с ограничениями на расстояния, страница 4

                                                                                                                                                                                                                            46          з

                            ОПТИМАЛЬНОЕ РАЗМЕЩЕНИЕ НА ДРЕВОВИДНЫХ СЕТЯХ ОБЪЕКТОВ                                                         399

Введем на дереве Т ориентацию дуг от произвольно выбранной корневой вершины vr, Е множество ориентированных дуг Т, = vr}, Vl — множество вершин поддерева с корнем И. Для фиксированного размещения Х = (М, х ) и для каждой вершины е У' определим множества Rl и Ц номеров новых объектов, Rl п Ь = ф . Еслиј е Щ, то путь из vr в х. содержит вершину Ч, иначеј е Ц. Для наглядности поясним, что если условно рассматривать ориентацию дуги (И, И) ”слева направо”, то в первом случае х. находится в или ”правее”, во втором — в или ”левее” (так как Т— дерево, то существует единственная вершина такая, что (Vi, Vl) е Е).

Выберем произвольно вершину е V'. Стоимость связей Cl(Ll, Щ) между объектами, проходящих через вершину Ч (или дугу (Vi, УД), находится следующим образом:

(3.1)

Для того чтобы минимизировать (3.2), достаточно минимизировать каждое слагаемое вида (З. 1). Далее будет показано, что это можно сделать с помощью построения серии минимальных разрезов в специальных сетях.

Аналогично клокальной сети для задачи на линии (см. [6]) строится и-локальная сеть задачи на дереве следующим образом. Рассмотрим вспомогательную сеть, имеющую п + 2 вершины: s, t иј,ј е Ј. Определим ненаправленные дуги (s, ј) с пропускными способностями Eh Whj и (Л t) с пропускными способностями Eh Whj, а также дуги (Л К) с пропускными способностями ијк, у, К е .I. Построенная сеть называется углокальной.

Пусть Yl и У[ — множества такие, что YlV У[ = .I, Yl п У! = ф и множества {s} Yl, {t} У!

определяют разрез в и-локальной сети. Обозначим этот разрез через (Yl, У/ Справедливы следующие свойства.

Свойство 1. Пропускная способность произвольного разреза (Щ, Yl ) в ч-локальной сети равна значению выражения (3.1) при Yl = Ь и У[ = Rl.

Свойство 2. Определение множеств Ь и Rl, минимизирующих (З. 1), эквивалентно нахождению минимального разреза в и-локальной сети.

Обоснование указанных свойств аналогично рассуждениям, приведенным для задачи на линии, поскольку дерево (как и линию) можно разрезать на две части по любой дуге (Vi, Vl) (см. [6]).