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

Заранее благодарен за отвен.

P.S. Неплого если алгоримт можно было бы распараллелить.

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

E>Помогите решить следующую задачу.
E> Есть граф, вершины и ребра которого взвешаны целыми числами. Необходимо разбить этот граф на части, минимально связанные между собой.

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

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

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

Уточни условия, плз. И на всякий случай примерчик приведи...

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

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

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

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

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

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