5.7. Асимптотически минимальная энергия

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

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

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

где

Относительная энергия будет равна

где обозначает полное число пар связей в соединителе принадлежащем с.

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

Если мы интерпретируем как то, что является подграфом то тип соединения — это частично упорядоченное множество. Вспомним, что поскольку конечно и каждая образующая имеет конечную арность (см. разд. 5.3), то арности должны быть равномерно ограничены некоторой константой Предположим, далее, что выполнено следующее условие (см. Kelley 1955 и определение 5.7.1 ниже).

Условие 5.7.1. Сеть, ассоциированная с 2, стремится к бесконечности.

Теперь введем необходимые определения.

Определение 5.7.1. Последовательность стремится к бесконечности, если для любого справедливо неравенство опот и конфинальна (см. Примечания А).

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

Разумеется, множество ограничено и непусто. Однако, как показано в работе (Hwang 1978), о нем можно сказать и еще кое-что.

Теорема 5.7.1. Множество компактно.

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

Мы покажем, что множество замкнуто, а поскольку мы уже знаем, что оно ограничено, это гарантирует компактность.

Без потери общности будем предполагать, что и

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

при и . Выберем, далее,

при Это можно сделать, поскольку

конфинальна. Так как последовательность

конфинальна, то конфинальна также и Следовательно, при что и требовалось доказать.

Для того чтобы продвинуться дальше, вспомним, что в разд. 3.8 первого тома было показано, что при "линейный" множество является выпуклым. Поскольку относительная энергия в (5.7.4) представляет собой линейную функцию от

то выпуклость — это как раз то свойство, которое желательно установить.

Чтобы это сделать, введем бинарную операцию о из 2 в 2, такую, что:

Условие 5.7.2. Бинарная операция о обладает следующими свойствами:

1. Она коммутативна и ассоциативна.

2.

3. Если то , т. е. она монотонная.

Нам также потребуется:

Определение 5.7.3. Тип соединения 2 называется однородным по отношению к бинарной операции , если

1. Для любых существует натуральное число такое, что копий (см. Примечания Б) - это подграф графа

2. Для любых

Замечание. В выражениях (5.7.12) — (5.7.14) мы воспользовались обозначениями, аналогичными (5.7.3): это количество связей в о, в то время как обозначает количество образующих.

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

Пример 1. Пусть тип соединения "линейный" и соединение, принадлежащее типу "линейный", число образующих равно Определим операцию . Она удовлетворяет условиям определения 5.7.3.

Пример 2. Пусть тип соединения "квадратная решетка" и - соединение размера . Определим как соединение размерами соответственно. Если выбрать то (5.7.2) принимает вид

Выражение (5.7.13) превращается в

и наконец (5.7.14) сводится к

Пример 3. Предполагая тип соединения однородным в смысле определения 5.7.3, Harary считать прямым произведением графов (см. Нагагу 1969) и определим на бинарную операцию

Тогда однородно по отношению к новой бинарной операции, доказательство предоставляется читателю.

Теперь мы готовы сформулировать еще один результат, взятый из работы (Hwang 1978).

Теорема 5.7.2. Если 2 однородный, то множество выпуклое.

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

Отсюда следует, что

Последнее можно преобразовать к виду

Применим теперь соотношения (5.7.12) и (5.7.14), пользуясь коммутативностью бинарной операции. Таким образом для отношения в числителе (5.7.21) получаем

Рассмотрим, далее, копиями копиями . Тогда (5.7.21) приблизительно равно

вектору объединенной конфигурации. Следовательно,

Вспомнив из доказательства теоремы 5.7.1, что множество F замкнуто, мы почти непосредственно приходим к выводу о том, что выпуклое (см. Примечания В), что и требовалось доказать.

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

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