Электронный каталог библиотеки МИСИС

Книга (аналит. описание)

Преображенский, А. А.
Оптимальное разбиение графа на К подграфов / А. А. Преображенский, В. Ф. Ходыкин // Труды Московского института стали и сплавов : науч. труды / МИСиС . – М. : Металлургия. - Вып.115: Системные исследования металлургических процессов и производства : Сб.статей / МИСиС . – М. : Металлургия, 1979 . – 20-23 .

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