Теория и практика параллельных вычислений
Постановка задачи оптимального разделения графов
Пусть дан взвешенный неориентированный граф G=(V,E), каждой вершине ?V и каждому ребру eE которого приписан вес. Задача оптимального разделения графа состоит в разбиении его вершин на непересекающиеся подмножества с максимально близкими суммарными весами вершин и минимальным суммарным весом ребер, проходящих между полученными подмножествами вершин.
Следует отметить возможную противоречивость указанных критериев разбиения графа – равновесность подмножеств вершин может не соответствовать минимальности весов граничных ребер и наоборот. В большинстве случаев необходимым является выбор того или иного компромиссного решения. Так, в случае невысокой доли коммуникаций может оказаться эффективной оптимизация веса ребер только среди решений, обеспечивающих оптимальное разбиение множества вершин по весу.
Далее для простоты изложения учебного материала будем полагать веса вершин и ребер графа равными единице.
