Поясните основную идею поискового алгоритма бисекции графа, а также алгоритма бисекции графа путем наращивания.
 Ответ 
Идея поискового алгоритма бисекции графа состоит в следующем:
1) задается некоторое исходное разбиение графа на два подграфа;
2) итерационно делается попытка перенести один или несколько узлов из одного подграфа в другой так, чтобы уменьшить критерий оптимальности разбиения.
В качестве критерия оптимальности целесообразно использовать суммарный объем обменов между подграфами при условии, что суммарные вычислительные сложности подграфов примерно равны. Поскольку данный критерий оптимальности является многоэкстремальным, результирующее разбиение графа сильно зависит от исходного приближения. Поэтому обычно приходится решать задачу многократно – для некоторого количества случайных исходных разбиений (по некоторым оценкам достаточно ~10 разбиений).
Идея алгоритма бисекции графа путем наращивания состоит в том, чтобы начать с одного узла и наращивать область вокруг этого первого узла до тех пор, пока не будет получено два удовлетворительных (с точки зрения выбранного критерия оптимальности) подграфа. Данный алгоритм чувствителен к выбору узла, с которого начинается рост графа. Поэтому, как и в предыдущем алгоритме, приходится решать задачу многократно – для некоторого количества случайных исходных узлов