Оптимальные иерархические структуры - Воронин А.А., Мишин С.П.

Доказательство следует из лемм 5.1-5.3. Утверждение доказано.

2. Стоимость реорганизации наборов групп.

В данном пункте на основании метрики на множестве групп, построенной в пункте 1, строится метрика на множестве наборов групп.

Определение 5.2. Стоимостью реорганизации произвольного

меньшей мощности дополнен пустыми группами до мощности k , минимум берется по всевозможным разбиениям наборов Q1 и Q2

на пары (gi , hi ), i = 1, k . Если Q1 – пустой набор, то величину ρ( ,Q2 ) назовем стоимостью организации набора Q2 “с нуля”. Если Q2 – пустой набор, то величину ρ(Q1, ) назовем стоимостью деорганизации набора Q1.

Задача о поиске разбиения на пары минимальной суммарной стоимости является задачей о назначениях. Таким образом, стоимость реорганизации эффективно вычисляется. Методы решения задачи о назначениях приведены, например, в работе [7].

Поясним определение. Предположим, что необходимо реорганизовать некоторый набор (множество) групп Q1 в набор Q2 . Рассмотрим две группы: g Q1 и h Q2 . Затраты на деорганизацию g и последующую организацию h “с нуля” составят ρ(g, ) + ρ( , h) . Затраты на непосредственную реорга- низацию g в h составят ρ(g,h) . Второй способ предпочтительнее в силу неравенства ρ(g, h) ≤ ρ(g, ) + ρ( , h) (см. лемму 5.3). Поэтому для реорганизации Q1 в Q2 разбиваем эти наборы на пары (g, h) Q1 × Q2 и реорганизуем g в h . Если Q1 < Q2 , то оставшиеся после разбиения на пары группы набора Q2 организуем “с нуля”. А если Q1 > Q2 , то оставшиеся группы

1 Набор групп Q – некоторое множество групп, в частности пустое. Q –

количество групп в наборе (мощность). В наборе могут быть одинаковые (повторяющиеся) группы.

172

набора Q1 деорганизуем. Таким образом, набор с меньшей

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

суммируя стоимость реорганизации первой группы пары во вторую, получим стоимость реорганизации набора Q1 в набор Q2 . Разбиение на пары производим таким образом, чтобы стоимость реорганизации была минимальна. Если Q1 – пустой набор, то получим стоимость организации набора Q2 “с нуля” (или сумму стоимостей организации всех групп набора “с нуля”), если Q2 – пустой набор, то получим стоимость деорганизации набора Q1 (или сумму стоимостей деорганизации всех групп набора).

Лемма 5.4. Добавление к любому из наборов групп Q1, Q2

Добавим к одному из наборов Q1, Q2 пустые множества. Обозначим мощность полученного набора через k′′. Если k′′ £ k ,

173

в пары (g,h), ( , ). При таком разбиении снова получим ρ(Q′′,Q′′),

1 2

так как сумма не увеличилась в силу ρ(g, h) ≤ ρ(g, ) + ρ( , h) (см. лемму 5.3), ρ( , ) = 0. Повторяя такие действия, получим в результате разбиение, в котором нет двух пар вида (g, ), ( , h).

Такое разбиение может быть получено из некоторого разбиения

Лемма 5.5. Если для любых групп f и g выполнена первая аксиома метрики, то и для любых наборов непустых групп Q1 и Q2 также выполнена первая аксиома метрики: равенство ρ(Q1,Q2 ) = 0

ρ(g, ) > 0 и ρ( , h) > 0 для любых непустых групп g и h . Далее

когда наборы Q1 и Q2 разбиваются на пары (gi , hi ) , для которых ρ(gi , hi ) = 0, то есть на пары одинаковых множеств, что возможно лишь при Q1 = Q2 . Лемма доказана.

Лемма 5.6. Если для любых групп выполнена вторая аксиома метрики, то и для любых наборов групп Q1 и Q2 также выполнена вторая аксиома метрики (симметричность): ρ(Q1,Q2 ) = ρ(Q2 ,Q1 ).

Доказательство. Добавим пустые множества так, чтобы наборы Q1 и Q2 содержали одинаковое количество k множеств.

Тогда имеем ρ(Q1,Q2 ) = min åi=1,k ρ(gi , hi ) = min åi=1,k ρ(hi , gi ) = = ρ(Q2 ,Q1) . Лемма доказана.

Лемма 5.7. Для произвольных наборов групп Q1, Q2 , Q3

выполнено неравенство треугольника:ρ(Q1,Q3) ≤ ρ(Q1,Q2) + ρ(Q2,Q3). Доказательство. Обозначим k = max(Q1 , Q2 , Q3 ). Добавим

к Q1, Q2 , Q3 пустые множества так, чтобы k = Q1 = Q2 = Q3 . По лемме 5.4 это не изменит величин ρ(Q1,Q3 ), ρ(Q1,Q2 ), ρ(Q2 ,Q3 ) .

174

Предположим, что ( fi , gi ), i = 1, k – разбиение множеств Q1 и Q2

соответствует значению ρ(Q2,Q3), тогда имеем: ρ(Q1,Q2)+ ρ(Q2,Q3) =

= åi=1,k [ρ( fi , gi ) + ρ(gi ,hi )] ³ åi=1,k ρ( fi ,hi ) ³ ρ(Q1,Q3), где послед-

нее неравенство выполнено в силу того, что ρ(Q1,Q3 ) соответст- вует разбиению наборов групп Q1 и Q3 на пары с минимальной суммарной стоимостью реорганизации. Лемма доказана.

метрикой наборах непустых групп.

Доказательство. По утверждению 5.1 стоимость

реорганизации любых групп удовлетворяет первой и второй аксиомам метрики и неравенству треугольника. По леммам 5.5-5.7 этого достаточно для того, чтобы те же свойства выполнялись для любых наборов непустых групп. Утверждение доказано.

3. Стоимость реорганизации графов.

Определение 5.3. Для произвольных ориентированных

графов G1 = (V1, E1) и G2 = (V2 , E2 ), вершины которых являются группами (V1,V2 F { }), стоимостью реорганизации G1 в G2

k = max(V1 , V2 ) , множество вершин меньшей мощности дополне-

но изолированными вершинами до мощности k , минимум берется по всевозможным разбиениям множеств V1 и V2 на пары (gi , hi ) ,

подчинены g , то есть из которых идут ребра в g в графе G1 . Аналогично QG2 (h)

– вершины, непосредственно подчиненные h в G2 .

175

граф G2 . Разбиение на пары производим таким образом, чтобы

стоимость реорганизации была минимальна.

На графах организации можно определить стоимость реорганизации как сумму по всем парам неначальных вершин. При этом, как показано в [31], стоимость реорганизации будет совпадать со стоимостью определения 5.3. Таким образом, понятие

стоимости реорганизации может быть расширено на произвольные ориентированные графы.

Лемма 5.8. При добавлении к любому из графов G1 = (V1, E1) и G2 = (V2 , E2 ) любого числа изолированных вершин стоимость реорганизации ρ(G1,G2 ) не изменится.

Доказательство. Обозначим k1 = V1 , k2 = V2 , k = max(k1, k2 ) .

При вычислении ρ(G1,G2 ) к V1 добавляется k − k1 изолированных вершин, к V2 добавляется k − k2 изолированных вершин. Обозна- чим полученные множества вершин через V1′ и V2′. Далее выбира-

ются пары (gi ,hi ) V1¢×V2¢, i =1,k так, чтобы åi=1,k ρ(QG1 (gi ),QG2 (hi )) была минимальна. Добавим к одному из множеств V1 или V2 изолированные вершины. Обозначим мощность полученного множества вершин через k′′, а соответствующие графы через G3 и G4 . Если k′′ ≤ k , то при вычислении ρ(G3 ,G4 ) снова получим

множества вершин V1′ и V2′, то есть ρ(G3 ,G4 ) = ρ(G1,G2 ).

Если k′′ > k , то при вычислении ρ(G3 ,G4 ) получим множества вершин V1′′ и V2′′, где Vj′′ образуется из Vj′ добавлением

k′′ − k изолированных вершин, j = 1,2. Множества V1′′ и V2′′ можно разбить на пары следующим образом: сохраним разбиение для V1′, V2′, оставшиеся пары (g,h) состоят из изолированных вершин,

(Q(g),Æ) и (Æ,Q(h)) , где Q(g) ¹ Æ и Q(h) ¹ Æ , то переформиру- ем их в пары (Q(g),Q(h)) и (Æ,Æ). При таком разбиении снова получим ρ(G3 ,G4 ), так как сумма не увеличилась в силу неравен-

177

ства треугольника (см. лемму 5.7) ρ(Q(g),Q(h)) ≤ ρ(Q(g), ) + + ρ( ,Q(h)) и равенства ρ( , ) = 0. Повторяя такие действия, получим в результате разбиение, в котором нет двух пар вида (Q(g), ) и ( ,Q(h)) . Такое разбиение может быть получено из некоторого разбиения множеств V1′ и V2′ добавлением пар (g,h), состоящих из изолированных вершин, для которых ρ(Q(g),Q(h)) =

= ρ( , ) = 0 . Таким образом, ρ(G1,G2 ) ≤ ρ(G3,G4 ). То есть ρ(G1,G2 ) = ρ(G3 ,G4 ). Лемма доказана.

Лемма 5.9. Если для любых наборов непустых групп выполнена первая аксиома метрики, то и для любых графов

организации G1 = (V1,E1) O(N) и G2 = (V2,E2 ) O(N) без изолиро- ванных вершин также выполнена первая аксиома метрики: равен-

ство ρ(G1,G2 ) = 0 эквивалентно равенству G1 =G2 (V1 =V2 и E1 = E2).

ρ(G1,G2 ) = åi=1,k ρ(QG1 (gi ),QG2 (hi )), где (gi , hi ) , i = 1, k – некото-

рое разбиение на пары множеств V1′ и V2′. Из ρ(G1,G2 ) = 0 следует

ρ(QG1 (gi ),QG2 (hi )) = 0. Так как G1 и G2 – графы организации, то

на пары gi = hi , причем в gi входят в графе G1 ребра из тех же вершин, что и в hi в графе G2 . Начальные вершины G1 не могут

{a} V1 в графе G1 выходит хотя бы одно ребро (она не изолирована) в неначальную вершину g V1 \ NG1 . Следовательно,

178

входящие в h , совпадают с ребрами G2 , входящими в h . Таким образом, E1 = E2 , из чего следует G1 = G2 . Лемма доказана.

Лемма 5.10. Если для любых наборов групп выполнена вторая аксиома метрики, то и для любых графов G1 и G2 также выполнена вторая аксиома метрики (симметричность):

ρ(G1,G2 ) = ρ(G2 ,G1 ).

Доказательство. Добавим изолированные вершины так, чтобы графы G1 и G2 содержали одинаковое количество k

больше или равна ρ(G1,G3 ) в силу того, что ρ(G1,G3 )

соответствует разбиению на пары с минимальной суммарной стоимостью реорганизации. Лемма доказана.

метрикой на множестве графов организации без изолированных вершин.

179

Доказательство. По утверждению 5.2 стоимость

реорганизации наборов непустых групп удовлетворяет первой и второй аксиомам метрики и неравенству треугольника. По леммам 5.9-5.11 этого достаточно для того, чтобы те же свойства

выполнялись для любых графов организации без изолированных вершин. Утверждение доказано.

4. Некоторые свойства стоимости реорганизации.

Лемма 5.12. Для любых наборов групп Q′ и Q′′ выполнено ρ(g′, g′′) £ ρ(Q′,Q′′), где g′ = Uh Q′ h и g′′ = Uh Q′′ h – группы,

образующиеся в результате объединения групп каждого из наборов. Если наборы Q′ и Q′′ содержат только неповторяющиеся элементарные группы, то вышеуказанное неравенство выполнено как равенство.

a′ Î g′, a′′Î g′′. Рассмотрим a Î g′ \ g′′. Группа {a} войдет ровно в

построенное разбиение является оптимальным. Лемма доказана.

180