Здравствуйте Slayer, Вы писали:

S>Не совсем понятно что значит минимально связанные между собой ?

Допустим граф уже разбит. Тогда в каждой его части есть ребра двух типов: а) внутренние ребра, которые связывают пары вершин, пренадлежащие одному и тому же "куску" (части графа); б) внешние ребра, которые связывают пары вершин, причем вершины пренадлежат разным "кускам" графа. Так вот, число (суммарное по всем парам "кусков" графа) внешних ребер после разбиения графа должно быть минимальным.

E>>Причем число вершин в каждом "куске" графа и суммарный вес не должны превышать заданных значений.

S>Это условие тоже не понятно... Не точно не понятно как ты вообще сможешь так разбить граф, если он уже не разбит?

То есть после разбиения число вершин в каждом "куске" графа не должно превышать некоторое заданное число (одно на все "куски"). Плюс к этому сумма весов в каждом "куске" тоже ограничена сверху занным числом. Таким образом, мы заранее не знаем на сколько частей нужно разбить граф.