4551
правка
Минимальная бисекция: различия между версиями
Материал из WEGA
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 10: | Строка 10: | ||
(Алгоритм аппроксимации по двум критериям разбивает вершины на два множество, каждое из которых содержит не более 2/3 вершин, и его значение (т.е. количество ребер, соединяющих множества) сравнивается со значением наилучшего разбиения на множества равного размера). | (Алгоритм аппроксимации по двум критериям разбивает вершины на два множество, каждое из которых содержит не более 2/3 вершин, и его значение (т.е. количество ребер, соединяющих множества) сравнивается со значением наилучшего разбиения на множества равного размера). | ||
== Разрезы и бисекции == | |||
Пусть G = (V, E) – неориентированный граф, имеющий n = |V| вершин. Для простоты предположим, что n четно Для подмножества S вершин положим S = V n S. Разрез (S, S’), также называемый сечением, определяется как множество всех ребер, имеющих одну конечную точку в S, а другую – в S’. Говорится, что эти ребра пересекают разрез, а множества S и S’ называются сторонами разреза. | |||
Будем предполагать, что ребра графа G имеют неотрицательные веса. (В невзвешенной версии будем предполагатьвеса всех ребер единичными). Стоимость разреза (S, S’) определяется как сумма весов всех ребер, пересекающих разрез. | |||
Разрез (S, S’) называется бисекцией графа G, если обе его стороны имеют одинаковую мощность, а именно – |S| = |S’| = n/2. Обозначим за b(G) минимальную стоимость бисекции G. | |||
