Консалтология Общая теория консалтинга (стр. 64 )

d(G())≥0, (10.33)

можно записать

d (G (L*)) < 0, (10.34) где

L* = LN \.

В дальнейшем при рассмотрении будем учитывать как ранее введенное его определение в виде (10.32), так и условие (10.33). В слу­чае, если = Ø, то это свидетельствует о том, что значение d(G ()) в условии (10.32) отрицательно, а вектор J недоопределен.

Итак, в основу предлагаемого метода положено членение ис­ходного множества LN на два непересекающихся подмножества и L*:

∩ L*=Ø

L* = LN ,

удовлетворяющих соответственно условиям (10.32) и (10.33), (10.34).

Отличительной чертой данного метода является целенаправлен­ность формирования множеств и L*, удовлетворяющих при­веденным выше условиям. Эта целенаправленность заключается в том, что исходный граф G(LN) представляется в виде совокуп­ности подмножеств определенных свойств (классов). Подмноже­ства отдельных классов при этом однозначно определяются как входящие в G (). Подмножества других классов анализируются и либо относятся к G(L*), либо также безусловно переходят в G(). Такая логика действий, основанная на последовательном от­делении от исходного множества LN подмножеств, безусловно при­надлежащих , обеспечивает алгоритмам, основанным на исполь­зовании предлагаемого метода, линейную вычислительную трудо­емкость их реализации в зависимости от размерности исходного графа.

В основе формируемого метода лежат:

1) условия, которые позволяют на каждой паре подмножеств (L1 и L2, L1 L2 = LN , L1 ∩ L2 = Ø) определить их эквива­лентность и L*;

2) определение классов подмножеств исходного графа со спе­циальными свойствами;

3) операции анализа подмножеств различных классов с целью безусловного отнесения этих подмножеств или их частей к .

Рассмотрим условия, позволяющие на каждой паре подмно­жеств L1 и L2 проверить их соответствие условиям (10.32)—(10.34), т. е. определить эквивалентность этих подмножеств критическому множеству и множеству без дефицита.

Введем в рассмотрение остов графа модели G (LN) = {Ф (LN), σ (LN)} и будем его обозначать g(LN)={Ф (LN), σLn}. Данный остов представляет собой древовидный двудольный граф с верши­нами-связями Ф(LN) и вершинами-переменными σLn. Здесь каж­дое множество σL(L≤LN) представляет собой совокупность вершин-переменных, соединенных с вершинами-связями на древо­видном графе g (L).

Определим на множестве вершин-отношений остовного графа функцию дефицита:

d(g(L))=|L|-|σL| при L LN. (10.35) Поскольку из определений для G (L) и g(L) следует, что

σ (L) σL при L LN (10.36)

то

d(g(L))≥d(G(L)) при L LN . (10.37)

Приступим теперь непосредственно к формированию названных условий. Они следуют из следующего утверждения.

Если на исходном графе G(LN)={Ф(LN), σ(LN)} построена пара основных деревьев g (L1) = {Ф (L1, σL1} и g (L2) = {Ф (L2, σL2}:

L1 L2 = LN; (10.38)

L1 ∩ L2 ≠Ø; (10.39)

σL1 σL2 = σ Ln = σ (LN); (10.40) . σL1 ∩ σL2 = Ø, (10.41)

таких, что

d(g (L')) < 0 при L' L1 (10.42)

d (g (L2)) ≥ 0; (10.43)

σL1 ∩ σ(L2) = Ø, (10.44)

то

L1 = L*; (10.45)

L2 = . (10.46)

Покажем справедливость дан­ного утверждения.

Предположим, что указанная пара остовов построена. Тогда из неравенств (10.37) и (10.43) непосред­ственно следует, что d(G (L')) < 0 при L' L1, т. е. L1 — есть множество без дефицита L*.

Из выражений (10.40), (10.41), (10.44) и очевидного условия

σ (L1 ) σ (L2) = σ (LN),

следующего, в частности, из соотношений (10.36) и (10.40), можно получить

σ L2 =σ (L2)

Тогда d (g (L2))=d(G(L2)) и согласно неравенству (10.37) d(G(L2)) ≥ 0, т. е. L2 является критическим множеством .

Теперь покажем, что если условия (10.45), (10.46) выполняются, то построенные на L1 и L2 остовы всегда удовлетворяют условиям (10.42)—( 10.43).

По определению, при условиях (10.44), (10.45) d(G (L'))<0 при

L' L1 и d (G (L2)) ≥0.

Из неравенств (10.37) и d(G (L2)) ≥ 0 непосредственно следует, что

d (g (L2)) ≥ 0.

Ha L1 будем строить остов, исходя из условия максимизации его дефицита, т. е. вершины σ (L1 )∩ σ (L2) будем считать отнесенными в

g (L2):

σ (L1 )∩ σ (L2) σ L2; (10.47)

σ Ll = σ (L1 )\ σ (L2). (10.48)

Предположим, что в данных условиях найдется подмножество

L' L, на котором d(g (L')) ≥ 0. Данное предположение равносильно, учитывая (10.47), тому, что d(G(L2 L')) ≥ d (G (L2)). Это противоречит исходному условию (10.45), что делает данное предположение неверным и доказывает истинность неравенства (10.42).

Таким образом, задача разделения исходного множества LN на множество вершин без дефицита — L* и критическое множе­ство — , т. е. на множества, удовлетворяющие условиям (10.32)— (10.34), может быть сведена к построению на исходном графе пары остовов, удовлетворяющих условиям (10.38)—( 10.44).

Само по себе построение пары остовов на исходном графе мо­дели, удовлетворяющих условиям (10.38)—( 10.43), не представляет проблем. Однако в общем случае здесь не будет выполняться усло­вие (10.44) (рис. 10.9). На достижение выполнения этого условия и на­правлен рассматриваемый метод.

Рис. 10.9. Членение остова информа­ционного графа на критическое мно­жество и множество без дефицита (— — — — — ребра, удовлетворяю­щие условию (10.44); —. —. — — ребра, не удовлетворяющие условию (10.44); □ — вершины-переменные; ○ — вер­шины-связи)

В основу предлагаемого формирования g(L1) и g(L2) положим их представление как совокупностей остовов определенных, рас­сматриваемых ниже классов.

10.1.2.4. Основные операторы решения задачи