§ 2.4. Графы
Граф является очень характерным математическим объектом адаптации. Покажем это на примере задачи о его агрегации.
Задача об агрегации графа, которую часто называют задачей о сегментации или разрезании графа, довольно широко распространена в приложениях. Содержание ее состоит в следующем.
Пусть задан граф с вершинами и ребрами, имеющими различные веса, которые, вообще говоря, могут изменяться во времени. Следует так объединить эти вершины в сегменты, чтобы:
а) суммарный вес вершин, попавших в один сегмент, не превышал некоторую постоянную этого сегмента («объем сегмента»),
б) суммарный вес связей между сегментами был мини мальным.
Легко видеть, что число возможных агрегаций графа при за данных объемах сегментов достаточно велико. Из этого множества допустимых вариантов агрегации» следует выбрать наилучший по критерию минимума суммарных связей между сегментами.
Сформулируем эту задачу как задачу дискретного программирования..
Пусть веса вершин графа равны 
веса ребер — 
а объем сегментов — 
Очевидно, что 
Агрегация задается характеристической матрицей 
имеющей 
строк (по числу сегментов) и 
столбцов (по числу вершин графа). Элементами этой матрицы являются двоичные числа
указывающие на принадлежность 
или непринадлежность 
вершины 
сегменту.
Очевидно, что при этом должно выполняться следующее условие:
т. е. каждая вершина агрегируемого графа должна попасть только в один сегмент. В результате матрица (2.4.1) содержит лишь 
единиц, а остальные ее элементы — нули.
Теперь задачу об оптимальной агрегации графа можно записать в виде следующей квадратичной задачи дискретного программирования:
где 
— область допустимых значений матрицы 
а 
характеристическая функция вида
Решение 
этой задачи и является искомой оптимальной агрегацией графа.
Реализация точного решения (2.4.4) связана в той или иной степени с перебором, что не позволяет решать задачи даже средней сложности. Однако применение эвристических процедур эволюционной адаптации дает возможность получать вполне применимые оценки точного решения 
за допустимое время.
Решение рассмотренной задачи об адаптивной агрегации графа будет рассмотрено в § 6.2.
