Метасистемный подход в управлении - часть 71

 

283 

   

Уточняющая  процедура  для  С-структур 

(или 

КС-процедура). 

Дана  С-

структура 

С

к

∈

&

п

 

и  соответствующий  граф 

r

n

(C

k

). 

Нужно  определить  все 

непосредственные уточнения на множестве. 

1)  исключить одно ребро из графа 

r

n

(C

k

), 

скажем ребро (a, b); 

2)  разделить каждый элемент 

х 

из С

k

, который содержит а

 

и b на два 

элемента 

х

а 

= х - {b} 

и 

x

b

 = x - 

{а}

 и заменить 

х 

из 

C

k 

на 

x

а

 и  

x

b

; 

3)  исключить все избыточные 

х

а

 

и 

x

b

, полученные на шаге 2 и записать 

полученный  результат  в  качестве  непосредственного  уточнения 

C

k

 

в  решетке 

(&

п

,≤

); 

4)  выполнить шаги 1—3 для всех ребер графа 

r

n

(C

k

) 

и остановиться. 

Данная процедура имеет следующие обоснования: 1) имеется взаимно одно-

значное соответствие между множествами 

R

п

 

и 

&

п

 

и, следовательно, любое изме-

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

Пример Г.18. Рассмотрим граф 

1

ρ

 и соответствующую С-структуру 

C

i

 

(ри-

сунок  Г.21,а).  Этот  граф  имеет  шесть  ребер  и,  следовательно,  шесть  непо-
средственных  уточнений  этой  С-структуры.  Они  изображены  на  рисунке 
Г.21,б.  Например,  уточнение  получается  с  помощью  RС-процедуры  следую-
щим образом: 1) из графа 

1

ρ

 исключается ребро (Г,5) и получается граф 

7

ρ

; 

2)  элемент (2, 4, 5} из  C

1

  (единственный  элемент  С

1

  содержащий  и 4 и 5) 

разбивается  на  элементы (2, 5} и {2, 4}; 3) поскольку  элемент {2, 4} 
является  единственным  избыточным  элементом ({2, 4}

⊂

{2, 3, 4}), он 

исключается,  а  полученный  результат  С

7

={{1, 2}, {2, 5}, (2, 3, 4}} 

записывается как непосредственное уточнение С

1

. 

Так  как  элементы  Р-структур  представляют  собой  просто  ребра  со-

ответствующих  графов,  то  процедура  уточнения  Р-структур  (или  RР-
процедура)  совершенно  тривиальна.  Она  состоит  в  исключении  отдель-
ных ребер из заданного графа [смотри шаг 1 RС-процедуры] и интерпретации 
результатов как Р-структур. 

Полезны также процедуры, с помощью которых получаются все непо-

средственные укрупнения для множеств G-, С- и Р-структур. Они нужны для 
определения  полного  структурного  соседства  заданной структуры. Формули-
рование этих процедур мы предоставляем читателю в качестве упражнения 
(смотри  также  рисунок  Г.10).  Примеры такого  соседства для трех этих ти-
пов структур приведены на рисунках Г.22 - Г.2Г. В этих примерах структуры 
обозначены  соответственно  как G, С  и  Р.  Их  непосредственные  уточнения 
помечены нижними индексами, а непосредственные укрупнения - верхними. 
На рисунке Г.22 показано, что в структурное соседство данной G-структуры 
могут входить G-структуры, входящие в другой класс r-эквивалентности (на 
рисунке  Г.22  это  структура 

G

3

).  Чтобы  непосредственные  уточнения  принад-

 

284 

   

лежали  тому  же  классу r-эквивалентности,  можно  слегка  модифицировать 
RG-npoцедуру,  заменив  условие  |

k

S|≥ 2 на  шаге 3 условием  |

  k

S |>2. 

При  

 

 

 

 

 

 

 

 

 
 

 
 

 

 

 
 

 

 

 
 

 

 

Рисунок Г.21.  Пояснение к RС-процедуре:  

а 

— заданный граф и со-

ответствующая С-структура; б — непосредственные уточнения C

1

 

2

ρ

С

2

3

ρ

6

ρ

 

6

C

 

5

ρ

4

ρ

4

C

6

ρ

6

C

 

285 

   

Рисунок Г.22. Структурное соседство G-структуры 

G 

 

этом запрещается изменять элементы, содержащие только две вершины, и, 
следовательно, граф данной r-структуры остается неизменным. 

Представление о непосредственных уточнениях (или укрупнениях) струк-

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

{N

n

} 

соответствующей  решетки  уточнения  за  одинаковое 

число  шагов  уточнения.  Будем  называть  эту  эквивалентность 

эквивалентно-

стью уровня уточнения 

и обозначать 

≡

i

. Так, например, структуры G

1

, G

2

, G

3

 на 

рисунке Г.22 - 

l

-эквивалентные G-структуры из множества &

4

; структуры, по-

казанные  на  рисунке  Г.21,б, - 

l

-эквивалентные  С-структуры  из  множества 

G

5

; структуры 

Р

1

.P

2

, 

Р

3

, 

P

4

 на рисунке Г.24 являются 

l

-эквивалентными 

Р-структурами из множества 

&

Г.

 

Для того чтобы можно было составить представление о скорости роста 

числа структур этих трех типов с ростом 

п, 

а также числа их классов 

i- 

и 

l

-

эквивалентности,  в  таблице  Г.12  приведены соответствующие  данные  для 

п ≤ 7. 

Понятно, что 

                               

,

|

R

|

|,

R

|

|

P

|

|

&

|

/

)

n

(

n

n

n

n

n

2

1

2

−

=

=

=

 

 

286 

   

 

 

Рисуноу Г.23 - Структурное соседство С-структуры 

С 

 
 

 

Рисунок Г.24 - Структурное соседство Р-структуры 

Р