Минимальная бисекция

Материал из WEGA
Версия от 23:10, 24 августа 2016; Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Бисекция графа == Постановка задачи == Обзор Минимальна…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Ключевые слова и синонимы

Бисекция графа

Постановка задачи

Обзор

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