6.2.4. Некоторые обобщения задачи об агрегации графа

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

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

а для задачи оптимального расположения блоков информации на цилиндрах магнитного диска (см. п. 6.2.2.3) она принимает вид

Критерия оптимальности агрегации графа теперь легко записать в форме

где номер сегмента, содержащего вершину графа а — номер сегмента, содержащего вершину Очевидно, что эта принадлежность определяется агрегацией т. е.

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

Задача, которую следует решать при оптимальной агрегации графа, теперь принимает вид

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

Операция первого рода (см. п. 6.2.3.2) преобразует агрегацию согласно (6.2.42) и (6.2.43) таким образом, что критерий качества изменяется на величину

Легко видеть, что при (6.2.92) это выражение вырождается в При функции вида (6.2.93) получаем

Очевидно, что при операцию следует считать успешной, а в противном случае — неудачной.

Теперь рассмотрим операцию второго рода (6.2.47). Она изменяет критерий качества следующим образом (воспользуемся здесь коммутативностью

При имеющей вид характеристической функции (6.2.92), это выражение совпадает с (6.2.49). Аналогично можно записать его для модульного представления (6.2.93). Учет полученных соотношений, определяющих успех или неуспех той или иной операции, в алгоритмах адаптивной агрегации п. 6.2.3.4 не представляет труда. Этим и определяется алгоритм поиска оптимальной агрегации графа с произвольным видом соотношения между сегментами.

Примеры адаптивной агрегации стохастического графа с соотношением вида (6.2.93) между сегментами и марковской моделью состояния среды X приведены в работе [116].