Минимальная бисекция: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
Разрез (S, S’) называется бисекцией графа G, если обе его стороны имеют одинаковую мощность, а именно – |S| = |S’| = n/2. Обозначим за b(G) минимальную стоимость бисекции G. | Разрез (S, S’) называется бисекцией графа G, если обе его стороны имеют одинаковую мощность, а именно – |S| = |S’| = n/2. Обозначим за b(G) минимальную стоимость бисекции G. | ||
Задача 1 (Минимальная бисекция) | |||
Дано: неориентированный граф G с неотрицательными весами ребер. | |||
Требуется: найти бисекцию (S, S) графа G с минимальной стоимостью. | |||
Это определение имеет одно существенное отличие от определения классической задачи о минимальном разрезе (см, например, [ ] и ссылки в этой работе): в нем имеется ограничение на обе стороны разреза. В результате задача о минимальной бисекции (MINIMUM-BISECTION) является NP-полной [ ], тогда как задача о минимальном разрезе (MINIMUM-CUT) может быть решена за полиномиальное время. | |||