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

Представим остов g (LN) исходного графа модели в виде не­которой совокупности остовов {gq (Фq, σq)} :

(10.49)

При этом ребра между этими остовами при их построении вначале рассматривать не будем.

Обозначим терминальные вершины некоторого остова gq (Фq, σq)

через Tq = {tgi}i=1,2.....Nqt (где Nqt — множество тер­минальных вершин на gq), а вершины, являющиеся точками вет­вления на этом дереве, — через Vq = {vqi} i=1,2.....Nqv (где Nqv — множество точек ветвления на gq).

Введем в рассмотрение совокупности остовов следующих четы­рех классов:

1) совокупность остовов класса А, обозначаемую далее

gA (Фа, σа) = {gai}, y которых:

- все терминальные вершины соответствуют переменным модели

(ТА σа );

- ветвление происходит только в вершинах, соответствующих связям модели (VA Фа);

2) совокупность остовов класса В, обозначаемую далее

gB (ФB, σB) = {gbi} , y которых:

- все терминальные вершины соответствуют переменным модели

(ТB σB);

- ветвление происходит только в вершинах, соответствующих переменным модели (VB ФB);

3) совокупность остовов класса С, обозначаемую далее,

gC (ФC, σC) = {gci} , y которых:

- все терминальные вершины, кроме одной, соответствуют пере­менным модели (| ТC ∩ ФC | = 1);

- ветвление происходит только в вершинах, соответствующих переменным модели (VC σC );

4) совокупность остовов класса D, обозначаемую далее

gD (ФD, σD) = {gdi} , y которых:

- функция дефицита всегда нулевая (d (gD) = 0);

- переменные, входящие в состав связей ФD, не содержатся в gA и gB:

σ(LD)∩(σA σB) = Ø. (10.50)

Определим значения функции дефицита на остовах различных классов. Как следует из построения , значение функции дефи­цита на остовах этого класса всегда отрицательно и, в частности,

d()=1-N at (i= 1, 2,...,NA).

При этом дефицит на gA, представляющем объединение(i =1, 2, ..., NA), определяется в виде

d(gA) = (10.51)

Из определения остовов классов В, С, D следует, что

d() = -1 (i=l, 2,...,NB); (10.52)

d(gB)= =-NB; (10.53)

d() = 0 (i = l,2,... ,NC); (10.54)

d(gC) = = 0; (10.55)

d() = 0 ; (10.56)

d(gD) = = 0. (10.57)

Итак, значения функции дефицита на остовах классов А и В всегда отрицательны, а на остовах классов С и D — нулевые. Данные свойства позволяют рассматривать объединение σА и gB как подмножества множества g (L*):

gA, gB g (L*),

а остовы класса D, учитывая эквивалентность условий (10.44) и (10.50), как подмножества g ():

gD g ().

Остовы класса С далее рассматриваются как переходные. В частности, если на них выполняется условие

σ (LC) ∩ (σА σB)=Ø, (10.58)

то они переходят в состав gD. Если же это условие не выполняе­тся, то они трансформируются в подмножества gB, gA и может быть gD.

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

{σ(0)А ,σ(0)B}= σ (LN)

При этом, в общем случае, найдутся вершины-отношения исход­ного графа, которые не войдут в g(0)A, g(0)B. Обозначим множества таких вершин через Фн(0):

Фн(0)= Ф(LN)/{Ф(0)A, Ф(0)B}.

Основные операции метода в таком случае могут быть сведены к последовательному объединению вершин из Фн(0) с одним из имеющихся остовов. Причем выполнение этих операций должно быть определено таким образом, чтобы в результате получались остовы лишь названных классов. По мере получения остовов класса С на них проверяется условие (10.58), в результате чего они переходят в классы А, В или D. Таким образом, в начале выполнения каждого очередного шага исходный граф представляется остовами трех классов — А, В, D.

Тогда, как результат выполнения конечного числа (|Фн(0)|) таких операций определяются gA и gB, задающие множество без дефицита L*, а также gD, определяющее критическое мно­жество . Здесь же отметим, что при выполнении каждого очеред­ного шага сформированное множество gD может лишь попол­няться за счет перехода в него отдельных частей из gA, gB, т. е. вершины, попавшие в состав остовов класса D, в gA и gB перейти не могут. Данное утверждение следует непосредственно из опре­деления остовов класса D и условия (10.49).

Определим процедуры объединения вершин из Фн с остовами различных классов, составляющие основные операции рассматри­ваемого метода.

Некоторая вершина ФjФн может быть объединена с остовом gqi если σj ∩ σqi ≠Ø. В зависимости от того, с какими классами остовных деревьев может быть объединена та или иная вершина, введем в рассмотрение следующие подмножества Фн:

ФA = {Фa : Фa Фн; |σa ∩ σA|> 1}; (10.59)

ФAB = {Фab : Фab Фн; σab ∩ σA≠Ø ; σab ∩ σB≠Ø }; (10.60)

ФB = {Фb : Фb Фн; |σb ∩ σB|> 1}; (10.61)

ФD = {Фd : Фd Фн; σd σD}; (10.62)

ФE = {Фe : Фe Фн; |σe \ σD|= 1}, (10.63)

где σq — вектор переменных, входящих в связь Фq (q= a, b, ab, d, e).

Учитывая, что каждая связь модели имеет в своем составе не менее двух переменных, а также промежуточный характер остовных деревьев класса С, нетрудно отметить, что Фн всегда может быть представлено его приведенными подмножествами, причем, как правило, неоднозначно.

Учитывая приведенную классификацию элементов Фн и из­ложенный выше метод, определим набор операций по выделению из

g(LN) его подмножеств, удовлетворяющих условиям (10.38)— (10.46). При этом рассмотрим все операции, представляющие практи­ческий интерес, имея в виду, что при реализации конкретных алгоритмов можно использовать не все из этих операций.

Первой рассмотрим операцию объединения некоторой вершины Фа с gA. Эта операция может выполняться различными способами в зависимости от положения элементов:

пa = σa ∩ σA

в структуре gA.

В частности, особого вида операций требуют элементы Фa, переменные которых пересекаются больше, чем с одной терминаль­ной вершиной из gA. Обозначим такого рода элементы ФAt: