2.2. Структура связей

Состав конечной конфигурации с будем определять как

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

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

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

Введем формальное определение понятия типа соединения.

Определение 2.2.1. Тип соединения представляет собой объединение множеств где всякое множество есть множество графов, заданных на вершинах.

Для рассматриваем все графы в которые можно получить как объединение множеств посредством добавления множества соединений а между двумя исходными графами.

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

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

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

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

Приведем в качестве примеров несколько важнейших типов соединений.

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

Если то выбрать — «линейный порядок»: это означает, что у всех образующих выходная связь образующей соединена со входной связью образующей

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

— «частичный порядок» означает, что соединения образуют частичный порядок, если принимаются во внимание направления стрелок. Иногда мы будем сталкиваться с такими типами соединений, для которых означает, что соединения, относящиеся к любому подмножеству конфигурации, также входят в 2. В таких случаях будем говорить о монотонном типе соединений 2. Роль конфигураций различных типов и работа с ними станут яснее при обсуждении конкретных случаев, которое проводится в разд. 2.3-2.9. Читатель может пропустить несколько отвлеченное обсуждение, проводимое в данном разделе, и обратиться непосредственно к разд. 2.3, вернувшись после ознакомления с приведенными в нем конкретными примерами к рассмотрению в общем виде в разд. 2.2.

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

Если, например, 2 — «линейный порядок», то монотонное расширение включает непересекающиеся множества, каждое из которых является линейно упорядоченным.

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

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

Если для конфигурации с заданы

то ее регулярность определяется взаимным соответствием соединенных связей. Последнее определяется отношением согласования или отношением связи зависящим от двух соответствующих связей и записываемым как

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

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

Определение 2.2.2. Конфигурация с, имеющая структуру является регулярной в том и только том случае, если выполняется для любого соединения .

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

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

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

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

Утверждение (2.2.4) совместимо с утверждением (2.2.3), так как, согласно определению 1.1.1, преобразования подобия не затрагивают структуру связей.

Поскольку каждое соединение включает две связи, справедливо

а также аналогичные соотношения для входных и выходных связей.

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

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

Отсюда следует, что в том и только том случае, если

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

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

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

Теорема 2.2.1

(i) Применение преобразований подобия к регулярным конфигурациям приводит к получению регулярных конфигураций, т. е. Если

(iii) Рассмотрим соединения , такие, что допустимы в смысле корректности типа соединения; в таком случае обе конфигурации у и у являются регулярными или обе нерегулярными и совпадают, если .

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

Для доказательства утверждения заметим, что преобразование подобия не затрагивает соединений. На основе соотношения (2.2.3) имеем

Следовательно, равенство в утверждении справедливо.

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

ответ будет одним и тем же, и поэтому обе конфигурации либо регулярны, либо нерегулярны. Следовательно, в таком ограниченном смысле имеет место ассоциативность.

Если для двух регулярных конфигураций справедливы условия

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

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

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

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

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

или, объединив -структуру и отношение связи в правило

получаем набор из трех элементов:

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

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