Книги по разным темам Pages:     | 1 |   ...   | 3 | 4 | 5 | 6 | 7 |   ...   | 26 |

емма 1.1. Для любого графа G = (V, E) и любой вершины v V \ NG выполнено gG (v) = gG (v1) gG (vk ), где QG (v) = {v1,,vk }. Если вершина v V подчинена вершине v V, то gG (v ) gG (v ).

Доказательство. Если для начальной вершины u NG выполнено u gG (vi ), то u подчинена vi, а так как из vi в v идет ребро, то u подчинена v, следовательно u gG (v). То есть gG (vi ) gG (v). Если u gG (v), то из u существует путь в v, который проходит хотя бы через одну из вершин vi (только из этих вершин идут ребра в v ), то есть u подчинена vi, следовательно u gG (vi ). В итоге имеем gG (v) = gG (v1) gG (vk ). Если начальная вершина u подчинена вершине v, а та, в свою очередь, подчинена вершине v, то из u существует путь в v и u gG (v ). То есть gG (v ) gG (v ). Лемма доказана.

Определение 1.15. Субиерархии или слои D1 = (V1, E1) и D2 = (V2, E2) назовем структурно эквивалентными, если для некоторых графов G1,G2, таких что D1 H (G1) S(G1), D2 H (G2 ) S(G2 ), существует изоморфизм D1 и D2, сохраняющий подчиненные группы. То есть существует взаимно однозначное отображение :V1 V2, такое, что условие (u,v) E1 эквивалентно условию ( (u), (v)) E2 и для любой вершины u V1 выполнено gG1 (u) = gG2 ( (u)).

Поясним определение структурной эквивалентности на примере. Пусть иерархии D1 = G1 и D2 = G2 структурно эквивалентны. Рассмотрим начальную вершину u NG1. Ей в графе G1 подчинена только она сама, то есть gG1 (u) = {u}.

Выполнено (u) NG2, так как в соответствующие вершины должны входить соответствующие ребра, а в u ребер не входит.

Имеем gG2 ( (u)) = { (u)} = gG1 (u) = {u}, то есть (u) = u. Итак, выполнено NG1 = NG2, причем соответствие начальных вершин тождественно. Оставшиеся части графов G1 и G2 могут отличаться только УпереименованиемФ вершин с сохранением структуры подчинения.

Рассмотрим графы G1 и G2, изображенные на рис. 1.3.

Выполнено NG1 = NG2 = {1,2,3,4,5,6}, но G1 и G2 не являются структурно эквивалентными. Рассмотрим слои D1 = ZG1 (9) и D2 = ZG2 (14) графов G1 и G2. D1 и D2 изоморфны: (7) = 12, (8) = 13, (9) = 14. Вершинам 7 и 12 в графах G1 и Gподчиняется одна и та же группа gG1 (7) = gG2 (12) = {1,2,3}.

Аналогично gG1 (8) = gG2 (13) = {4,5,6}. Вершины 9 и 14 управляют одной и той же группой gG1 (9) = gG2 (14) = {1,2,3,4,5,6} с помощью управления одними и теми же непосредственно подчиненными подгруппами {1,2,3} и {4,5,6}. Таким образом, нашлись графы G1 и G2, в которых слои D1 и D2 имеют Уодну и ту же структуру подчиненияФ, то есть структурно эквивалентны. Обозначим результат 9-упрощения G1 через H1, 14-упрощения G2 - через H2.

Субиерархии H1 и H2 имеют Уразные структуры подчиненияФ, то есть не являются структурно эквивалентными, что и приводит к отсутствию структурной эквивалентности G1 и G2, несмотря на эквивалентность D1 и D2.

9 12 7 8 10 1 2 3 4 5 6 1 2 3 4 5 Рис. 1.3. Пример графов G1, G2 (слева направо).

5. Простые и структурные функционалы.

Определение 1.16. Функционал P назовем простым, если его можно аддитивно продолжить на множество (см. опр. 1.10) так, чтобы для любых структурно эквивалентных графов D1, Dвыполнялось P(D1) = P(D2 ).

Таким образом, аддитивный функционал прост, если его значение одинаково для графов с Уодинаковой структурой подчиненияФ. То есть УпереименованиеФ любых управляющих (неначальных) вершин графа не приводит к изменению стоимости, так как сохраняется структура подчинения начальных вершин.

Определение 1.17. Функционал P назовем структурным, если для любого графа G = (V, E) выполнено P(G) = vV \NG P(gG (v1),, gG (vk )),1 где QG (v) = {v1,,vk } и величина P(gG (v1),, gG (vk )) 0 однозначно определяется своим аргументов - набором групп2 - и не зависит от графа G и порядка групп gG (v1),, gG (vk ).

Теорема 1.2. Простой функционал стоимости структурен.

Доказательство. По определению простого функционала продолжим его на и докажем структурность P. По теореме 1.P локален, следовательно для любого графа G = (V, E) выполнено P(G) = vV \NG P(ZG (v)). Рассмотрим v V \ NG.

Здесь и далее одной и той же буквой P обозначается как стоимость графов из, так и стоимость наборов групп, что не приводит к путанице в силу различия аргументов функционалов.

В наборе могут быть повторяющиеся группы.

Обозначим QG (v) = {v1,,vk } и положим по определению P(gG (v1),, gG (vk )) = P(ZG (v)) 0. Пусть для некоторого графа G1 = (V1, E1) и некоторой вершины u V1 \ NG1 выполнено QG1 (u) = {u1,,uk }, gG (vi ) = gG1 (ui ), i = 1, k. Тогда звенья ZG (v) и ZG1 (u) структурно эквивалентны: (vi ) = ui, i = 1, k, (v) = u, по лемме 1.1 gG (v) = gG (v1) gG (vk ) = gG1 (u1) gG1 (uk ) = = gG1 (u) = gG1 ( (v)). В силу равенства P(ZG (v)) = P(ZG1 (u)) величина P(gG (v1),, gG (vk )) определяется набором групп и не зависит от графа G. Изменение порядка записи вершин v1,,vk никак не влияет на значение P(ZG (v)), то есть P(gG (v1),, gG (vk )) не зависит от порядка групп. Теорема доказана.

Определение 1.18. Множество назовем вершинно определенным, если любой вершине v соответствует одна и та же подчиненная группа g в любом графе G = (V, E), который содержит v : v V, gG (v) = g.

Неформально выражаясь, множество вершинно определено, если каждой вершине во всех графах подчинена одна и та же группа. Следующая теорема уточняет теорему 1.2 для вершинно определенных множеств.

Теорема 1.3. На вершинно определенном множестве функционал стоимости прост тогда и только тогда, когда он структурен.

Доказательство. Простота влечет за собой структурность на любом множестве в силу теоремы 1.2. Докажем обратное для вершинно определенного множества. Предположим, что функционал структурен. Рассмотрим произвольный граф D = (V, E) \ и некоторую вершину v V \ ND. Пусть QD (v) = {v1,,vk }. В силу вершинной определенности подчиненные группы gG (v1) = g(v1),, gG (vk ) = g(vk ) не зависят от того, в какие графы G входит D. То есть величина P(gG (v1),, gG (vk )) (см. опр. 1.17) зависит только от v1,,vk, а не от графа G. Если ZD (v), то положим по определению P(ZD (v)) = P(g(v1),, g(vk )). Тогда для всего графа D определим P(D) = vV \ND P(ZD (v)). Аналогично доказательству теоремы 1.можно показать, что построенное продолжение функционала аддитивно (см. опр. 1.10). Рассмотрим структурно эквивалентные графы D1 = (V1, E1) и D2 = (V2, E2). Для v V1 \ ND1, QD1 (v) = {v1,,vk } выполнено QD2 ( (v)) = { (v1),, (vk )}. Кроме того, g(vi ) = g( (vi )), i = 1,k. То есть P(ZD1 (v)) = P(ZD2 ( (v))) = = P(g(v1),, g(vk )). Таким образом, графы D1 и D2 разбиваются на пары соответствующих звеньев с одинаковой стоимостью.

Следовательно, P(D1) = P(D2 ). Теорема доказана.

Если множество не является вершинно определенным, то найдется вершина v, которой в различных графах подчинены разные группы. Множество подчиненных групп имеет вид {gG (v) : G = (V, E), v V}. В этом случае можно перейти к множеству, в графах которого вместо вершины v будут присутствовать новые вершины, определяемые подчиненными группами: {vG = (v, gG (v)) : G = (V, E), v V}. Множество уже будет вершинно определенным. Если функционал структурен на, то он, очевидно, структурен и на. Таким образом, по теореме 1.3 функционал прост на.

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

Данная работа посвящена исследованию структурных функционалов. Настоящий параграф позволяет содержательно интерпретировать требование структурности: если при Усложении частейФ в иерархию их стоимости складываются, стоимость вырожденной иерархии нулевая и при замене (переименовании) управляющих (неначальных) вершин стоимость не меняется, то функционал прост и излагаемые ниже методы могут быть использованы для решения задачи об оптимальной иерархии.

Ниже (см. п.4 и п.5 з1 гл. II) приводятся примеры задач с неструктурным функционалом, что иллюстрирует необходимость изучения таких функционалов. Остальные примеры главы II показывают, что структурными функционалами описываются разнообразные задачи. Глава II в целом иллюстрирует применение полученных в работе общих методов исследования структурных функционалов для анализа частных задач.

з2. Редукция общей задачи к задаче об оптимальной организации.

1. Графы организации.

Определение 1.19. Ориентированный конечный ациклический граф G = (V, E), в котором множество вершин V может содержать повторения, назовем графом организации над множеством элементов N, если выполнены следующие условия:

a) в вершинах графа находятся группы элементов, то есть для любой вершины g V выполнено g F (см. опр. 1.13);

b) для любой группы g V \ NG выполнено g = h, hQG (g ) где через QG (g) = {h : h V,(h, g) E} обозначено множество вершин графа G, из которых идут ребра в g,1 а через NG = {g V : QG (g) = } обозначено множество начальных вершин G. Будем говорить, что группа g V \ NG организуется из подгрупп множества QG (g).

c) Любая группа g NG элементарна. Множество NG не содержит повторяющихся групп.

Все множество графов организации (организаций) над множеством элементов N обозначим через O(N).

Для любой организации G = (V, E) O(N) и любых групп g,h V можно определить подчиненность g и h, множества RG (g), TG, звенья ZG (g), g -упрощение так же, как в Множество QG (g) может содержать повторяющиеся группы.

определениях 1.2-1.6. Ниже будем пользоваться этими обозначениями.

емма 1.2. Любой граф G = (V, E) после замены всех вершин v V на подчиненные им группы gG (v)1 становится графом организации над N.

Доказательство. Если v NG, то вершине v подчинена только она сама, следовательно группа gG (v) = {v} элементарна.

Вершины графа G не повторяются, следовательно после замены в начальных вершинах не будет повторяющихся групп. Рассмотрим вершину v V \ NG. Пусть вершине v непосредственно подчинены вершины v1,,vk, то есть QG (v) = {v1,,vk }. Тогда по лемме 1.имеем gG (v) = gG (v1) gG (vk ). Лемма доказана.

Определение 1.20. Отображение O : O(N ) определим как замену всех вершин графа G подчиненными им группами.

По лемме 1.2 O действительно отображает в O(N ). Множество образов обозначим через O() O(N).

емма 1.3. Иерархии из, переводящиеся отображением O в один граф, структурно эквивалентны и в случае структурного функционала имеют одинаковую стоимость.

Доказательство. Пусть графы G1 и G2 отображением O переводятся в один и тот же граф D = (VD, ED ) O(N ).

Рассмотрим вершину g VD и ее прообразы v V1 и u V2 в графах G1 и G2. Положим по определению (v) = u. У каждой группы g VD в графе G1 один и только один прообраз (VD может содержать повторяющиеся группы). То же касается и графа G2.

Таким образом, - взаимно однозначное соответствие V1 и V2.

Условие (v,v ) E1 эквивалентно условию (gG1 (v ), gG1 (v )) ED, которое, в свою очередь, эквивалентно условию ( (v ), (v )) E2.

То есть - изоморфизм G1 и G2. Кроме того, для любой v V При этом несколько вершин могут замениться на одинаковые группы, что приведет к появлению повторений во множестве вершин, а не к отождествлению совпадающих групп.

выполнено gG1 (v) = gG2 ( (v)), то есть G1 и G2 структурно эквивалентны.

Пусть функционал структурен. По определению 1.17 для графа G1 = (V1, E1) выполнено следующее равенство P(G1) = vV \NG1 P(gG1 (v1),, gG1 (vk )), где QG1 (v) = {v1,,vk }.

Рассмотрим вершину v V1 \ NG1. Тогда имеем QG2 ( (v)) = { (v1),, (vk )} и выполнено gG1(vi) = gG2 ( (vi)) = gi, i = 1, k. Следовательно, и в P(G1), и в P(G2 ) присутствуют одни и те же слагаемые P(g1,, gk ), то есть P(G1) = P(G2 ). Лемма доказана.

Определение 1.21. Определим функционал стоимости P : O(N) [0;+) на O(N) следующим образом: для любого G = (V, E) O(N) положим P(G) = gV \NG P(g1,, gk ), где QG (g) = {g1,, gk }, величина P(g1,, gk ) 0 определена заданным на структурным функционалом (см. опр. 1.17), в противном случае задана произвольно. Вместо P(g1,, gk ) будем также использовать обозначение P(QG (g)).

Поясним определение. В зависимости от множества величина P(g1,, gk ) может быть определена не на всех наборах групп из F, а только на тех, которые встречаются в графах O().

На остальных наборах определим P(g1,, gk ) 0 произвольным образом, так, чтобы величина P(g1,, gk ) не изменялась при перестановках групп g1,, gk.

Итак, считаем функционал структурным. Тогда прообразы любого графа организации структурно эквивалентны и имеют одинаковую стоимость (см. лемму 1.3). По определению 1.21 для любого графа G выполнено P(G) = P(O(G)). То есть стоимость организации из O() и стоимости всех ее прообразов совпадают. Следовательно, для поиска оптимальной на иерархической структуры достаточно найти оптимальную организацию на O() O(N), после чего найти любой из ее прообразов в. Таким образом, задача об оптимальной иерархии трансформируется в задачу об оптимальной организации.

В дальнейшем в работе считается заданным функционал стоимости на O(N ) (см. опр. 1.21) и решается задача об оптимальной организации на различных подмножествах O(N), что позволяет решать задачи об оптимальной иерархии на соответствующих множествах для структурных функционалов.

2. Оптимальная организация набора групп.

Множество O(N) содержит, в частности, вырожденные графы (то есть графы, состоящие из изолированных элементарных групп) нулевой стоимости. Поэтому решение задачи об оптимальной организации на всем множестве O(N ) тривиально.

В общем случае множество исследуемых организаций O() может иметь сколь угодно сложную структуру. В задачах, интересных с математической точки зрения, структура множества O() Фдостаточно простаФ в том смысле, что для любого графа G O(N ) имеется УэффективныйФ алгоритм проверки условия G O().

Определение 1.22. Множество организаций, в которые входят группы f1,, fm,1 обозначим через O( f1,, fm ) или O(f ), где f = { f1,, fm}. Любую организацию из O(f ) назовем организацией групп f1,, fm. Любую неначальную группу, отличную от f1,, fm, назовем промежуточной группой.

Содержательно условие O() = O(f ) означает, что ставится задача поиска оптимальной организации среди тех, которые управляют группами элементов f1,, fm. Если в O() входят организации, управляющие хотя бы одним из наборов групп Подразумевается, что среди f1,, f нет повторяющихся групп.

Pages:     | 1 |   ...   | 3 | 4 | 5 | 6 | 7 |   ...   | 26 |    Книги по разным темам