Применение метода ветвей и границ для решения задачи дихотомического разрезания гиперграфа

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