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