Анотація. Розглянуто задачу знаходження максимального розрізу на графах. Наведено нову модель задачі в термінах бази поліматроїда. Показано, що розв’язок задачі можна знайти гріді алгоритмом після того, як визначено оптимальне лінійне впорядкування вершин .
Ключові слова: максимальний розріз, двочастковий підграф, лінійне впорядкування.
Шарифов Фирдовси Ахун-оглы,
доктор физ.-мат. наук, старший научный сотрудник Института кибернетики им. В.М. Глушкова
НАН Украины, Киев,
fasharifov@gmail.com