Главная > Лекции по теории образов: Регулярные структуры
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
След.
Макеты страниц

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

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

3.2. Координаты конфигураций

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

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

Преобразования координат, обеспечивающие выполнение этого условия, образуют некоторую группу, обозначаемую как

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

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

В процессе анализа глобальной регулярности мы систематически используем ионятие соединения» (см. т. 1, разд. 2.1). Для определенности отметим, что образующие, подлежащие соединению, располагают остовами (глобальной связностью), принадлежащими некоторому заданному множеству Используя произвольную совокупность остовов часть которых могут быть идентичны, формируем некую комбинацию посредством соединения между собой связей без каких-либо ограничений, за исключением, естественно, требования, чтобы ориентация «выходная - > входная» соблюдалась, если регулярность является ориентированной. В случае симметрической регулярности даже такое ограничение отсутствует.

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

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

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

Остов комбинации можно представить как структуру связей соединения индексы классов образующих:

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

эта информация представляется посредством некоторой системы координат, причем снова координаты нельзя определить однозначно, если

Тип соединения обычно оказывается чрезмерно «широким» для описания встречающихся нам глобальных регулярностей, и мы сузим его до некоторого подмножества, которое будет обозначаться через 2 или, если мы захотим выделить семейство остовов, через Приведем несколько примеров, проиллюстрировав их схемами, приведенными на рис. 3.2.1, причем маленькие ноперечпые штрихи изображают связи. Для простоты примем, что значения а везде одни и те же, в противном случае эти значения следовало бы указать на рисунке.

На рис. 3.2.1(a) тип соединения 2 — «линейный», а Г такое же, как на рис. 3.1.3(a). В связи с линейностью упорядочения естественно задавать координаты образующих посредством их нумерации при помощи нижнего индекса начиная «слева», и связей при помощи

Отметим, что локальных условий оказывается недостаточно. Исключается, например, возможность соединения самой «правой» связи на рисунке с самой «левой».

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

ясны позже.

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

На рис. 3.2.1(в) «квадратная решетка», остов с топологически эквивалентен некоторому подмножеству плоской решетки пар целых чисел, а множество остовов образующих задано так, как это показано на рис. 3.2.1(в). Важно иметь в виду, что для описания этого типа соединения 2 локальных условий недостаточно: не допускаются, например, циклы. Одна из возможных систем координат могла бы выглядеть следующим образом. Рассмотрим все самые «западные» вершины образующих и выберем самую «южную» из них. Присвоим ей координаты

Рис. 3.2.1 (см. скан)


(0, 0) и будем продолжать, прибавляя единицу к первой или второй координатам. Вершины связей получают координаты или как показано на рисунке.

Если снова допускается наличие не соединенных между собой подкомпонент, то соответствующий тип соединения будет обозначаться как (квадратная решетка); в этом случае также

потребуется какая-то метка для обозначения соединенных подкомпонент.

Рис. 3.2.1 (г) иллюстрирует случай «дерево»; множество остовов образующих Г такое же, как на рис. 3.1.3(б). Разумная система координат в данном случае могла бы помечать «самую верхнюю» вершину образующей через (0), образующие следующего слоя — через и т. д., как показано на рисунке. Связи можно пронумеровать, используя координату главной вершины, из которой она исходит, в сочетании с координатой связи того отдельного остова, которому она принадлежит.

В случае «лес» (дерево) следует выполнить очевидные модификации.

На рис. «полный», так что все у имеют бесконечную арность — показать все связи мы не в состоянии. В этом примере мы имеем дело с симметрической регулярностью. Если главным вершинам не соответствуют различные значения а, то "их нельзя различать. Если же, однако, они помечены, то внутренние связи определяются двумя вершинами, соответствующими каждой связи.

На рис. 3.2.1(e) представлен случай «частично упорядоченное множество», Г такое же, как на рис. 3.1.3(в). В данном случае мы ставим в соответствие главным вершинам значения X, выбираемые из некоторого частично упорядоченного множества, совместимого со связностью графа. Поскольку главные вершины определены (однозначно или неоднозначно), связи можно пометить при помощи двух главных вершин и координат соответствующих отдельных остовов.

Крайний случай представляет тип соединения когда в регулярную конфигурацию могут вводиться лишь изолированные образующие. Этот крайний случай в некотором смысле противоположен случаю «полный».

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

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

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

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

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

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

Если заданы два пространства конфигураций , то можно построить их объединение и непосредственно ввести другие теоретико-множественные операции. Подпроизведением мы будем понимать новое пространство конфигураций где обеспечивает соединение связей в соответствии с и связей в соответствии с Новое отношение связей сводится к отношению на связях и к отношению на связях

Рассмотрим пример такого произведения, положив «линейный», как в так и в . На рис. 3.2.2 образующие произведения индексируются с помощью пар причем индекс используется для образующих для образующих Две связи образующей помечаются индексами (соответственно левая, правая), а связи образующей индексами (соответственно верхняя, нижняя). Существуют и другие варианты этой конфигурации, обладающие более «извилистой» схемой, но такой же регулярностью произведения.

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

Регулярность предстает перед нами в двух формах: локальной и глобальной. Может оказаться, что одна из них или даже обе тривиальны. Пространство конфигураций локально свободно, если отношение связей и оно глобально свободно, если тип соединения «все». Если свободно как локально, так и глобально, то этот факт выражается с помощью записи «свободное», что отличается от терминологии, принятой в

Рис. 3.2.2

1
Оглавление
email@scask.ru