Минимальная бисекция
Материал из WEGA
Ключевые слова и синонимы
Постановка задачи
Обзор
Минимальная бисекция – это базовое представление семейства задач дискретной оптимизации, имеющих дело с разбиением вершин входного графа. Обычно цель заключается в минимизации количества ребер, соединяющих два отдельных фрагмента графа, при сохранении некоторого контроля над разбиением – например,за счет ограничения количества и/или размера фрагментов. (Это описание соответствует реберному разрезу графа; в случае вершинного разреза употребляются схожие ограничение). Целью задачи о минимальной бисекции является разбиение вершин входного графа на два множества равного размера, такое, чтобы количество ребер, соединяющих эти два множества, было насколько возможно малым.