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

 

279 

   

С-структуру  из  &

п

 

и  одну 

Р-

структуру  из 

P

п

. 

Таким  образом,  С-  и  Р-

структуры могут рассматриваться как два 

канонических представления 

клас-

сов 

r

-эквивалентности G-структур.  Каждый  класс r-эквивалентности,  пред-

ставленный графом, описывается двумя каноническими структурами - наиме-
нее уточненной С-структурой и наиболее уточненной Р-структурой. Взаимно 
однозначное  соответствие  между 

R

п 

и 

G

п

 

(или 

P

п

) 

индуцирует  булеву  ре-

шетку на 

G

п

 

(или на 

P

n

), изоморфную естественной булевой решетке, опреде-

ленной на 

P

n

.  

Например,  на  рисунке  Г.16  показаны  решетка (&

3

,≤)  и  взаимно 

изоморфные булевы решетки, определенные на 

R

3

, G

3

, P

3

 и &

3

/

r

3

.  

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Рисунок  Г.16 – Решетка (&

3

,≤)  и  булевы  решетки,  определенные  на 

R

3

, 

G

3

, P

3

, &

3

/

r

3 

Для описания больших решеток полезно определить отношение эквива- 

лентности 

≡

i

 

на множествах &

n

 следующим образом: 

 

 

 

280 

   

 

Рисунок Г.17 – Решетка (&

3

, ≤ ) и гомоморфное отображение &

3

→&

3

/

i

 

j

i

i

G

G

≡

 тогда и только тогда, когда G

i

, G

j

∈

&

n

 и G

i

, G

j

 

изоморфны (то 

есть  когда  одна  структура  может  быть  получена  из  другой  только  переста-
новкой целых чисел из 

N

n

, 

напоминаем, что каждое целое число соответствует 

узлу).

 

Будем 

≡

i

 называть i - эквивалентностью и обозначать через 

&

n

/i 

мно-

жество  классов  эквивалентности  изоморфных  структур  (или  перестановоч-
ных классов эквивалентности), определенных на &

п

. 

Пример,  демонстрирующий  смысл i-эквивалентности,  приведен  на  ри-

сунке Г.17, где обозначенные полужирным шрифтом 

G

k

 (k

∈N

5

) 

показы-

вают  классы  эквивалентности  в  &

3

/

i. 

На  рисунке  Г.17,а  показана 

решетка (&

3

/i, ≤). Это та же самая решетка, что и на рисунке Г.16, но уп-

рощенная, так как на ней не различаются изоморфные структуры. Сделано 
это за счет удаления меток входов в блоки на схеме и включения только од-
ной схемы для каждого перестановочно эквивалентного класса. Структуры 
в каждом классе легко определяются перестановкой целых 1, 2, 3 для входов в 
блоки. Упрощенная решетка на рисунке Г.17,в является гомоморфным образом 
решетки,  изображенной  на  рисунке  Г.16.  Гомоморфное  отображение,  являю-
щееся основой данного упрощения, показано на рисунке Г.17д 

G

1

=C

1

G

2

=P

1

G

3

C

2

P

2

G

4

C

3

P

3

G

5

C

4

P

4

&

3

&

3

/

i

 

G

1

G

1 

G

2

G

2

 

G

4

G

3

 

G

7

G

4

 

G

9

G

5

 

G

8

G

6

G

5

G

3

а) 

б) 

 

281 

   

На рисунке Г.18 показана более сложная решетка 

(&

4

/i, ≤ 

). Перестановоч-

ные классы эквивалентности G-структур снова выделены жирным шрифтом, 

равно как С-структуры и Р-структуры, сгруппированные по классам r-

эквивалентности. Каждому такому классу соответствует граф 

k

ρ

 и две ка-

нонические структуры 

C

k

 

и 

P

k

 (k

∈N

11

). 

Для того чтобы более ярко проде-

монстрировать общие свойства этой решетки, на рисунке Г.19 перестано-

вочные классы С-структур обозначены только их идентификаторами и выде-

лены классы r-эквивалентности 

 

Рисунок Г.18. Решетка с указанием классов r-эквивалентности и 

канонических G- и Р-структур 

 

282 

   

 

Рисунок Г.19 – Упрощенная схема ре-         Рисунок Г.20 – Решетка (&

4

/

i

, ≤ ) 

шетки (&

4

/

i

, ≤), полностью показан- 

ной на рисунке Г.18 

На рисунке Г.20 изображена решетка (&

4

/

i

, ≤), являющаяся подрешеткой 

(

G

4

/

i

,  ≤).  Число  около  каждой  схемы  указывает  на  число  различных  С-

структур,  входящих  в  перестановочный  класс  эквивалентности,  показанный 
на этой схеме; числа, помещенные около дуг, указывают на число непосред-
ственных уточнений С-структуры из данного перестановочного класса экви-
валентности  в  другой  класс.  Как  уже  объяснялось  выше,  эта  решетка  изо-
морфна решеткам, определенным на 

R

4

/

i, P

4

/

i

 и (&

4

/

i)

. 

В  то  время  как  полные  решетки (&

n

,  ≤)  представляют  основу  для  ло-

кального  уровня  вычислений  в  задаче  реконструкции,  решетки (&

n

,  ≤)  и  их 

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

k

∈

&

n

 (n

∈

N) все непосредственные уточнения 

в  решетке (&

n

,  ≤).  Ниже  приводится  одна  такая  процедура,  использую-

щая представление С-структур в виде графов.