Минимальная бисекция: различия между версиями

Пусть G = (V, E) – неориентированный граф, имеющий n = |V| вершин. Для простоты предположим, что n четно Для подмножества S вершин положим <math>\bar{S} = V \backslash S \;</math>. [[Разрез]] <math>(\bar{S}, S) \;</math>, также называемый [[сечение|сечением]], определяется как множество всех ребер, имеющих одну конечную точку в <math>S \;</math>, а другую – в <math>\bar{S} \;</math>. Говорится, что эти ребра пересекают разрез, а множества <math>S \;</math> и <math>\bar{S} \;</math> называются сторонами разреза.

Будем предполагать, что ребра графа G имеют неотрицательные веса. (В невзвешенной версии будем предполагать веса всех ребер единичными). Стоимость разреза (S, S’) определяется как сумма весов всех ребер, пересекающих разрез.