| |
Шарифов, Ф. А.
Разрезы в неориентированных графах. II [Текст] / Ф. А. Шарифов, Л. Ф. Гуляницкий
// Кибернетика и системный анализ. – 2020. – Т. 56, № 5. – С. 70-79.
Предложены два алгоритма преобразования текущей базы полиматроида в новую для улучшения значения целевой функции. Установлена эквивалентность задачи максимального разреза на заданном графе и задачи нахождения минимального разреза, отделяющего источник и сток в сети, построенной относительно некоторой базы расширенного полиматроида. Сформулированы необходимые и достаточные условия оптимальности решения задачи максимального разреза на неориентированных графах в терминах теории потоков. |
