Всем доброго времени суток.

Описываю вопрос.

Пусть декартовыми координатами задано множество вершин V. Для каждой пары вершин (v1, v2) из V определно некоторое число
p(v1,v2) — поток от v1 к v2.
Если очень сложно, то p(v1,v2) можно считать равным p(v2,v1). Необходимо построить следующие связи между этими вершинам (читай — граф), где стоимость связи пропорциноальна её длине и её пропускной способности, так, чтобы удовлетворить все потоки с минимальной суммарной суммой стоимостью связей.

Короче — упрощённое проектирование топологии сети, НО по-моему и здесь точного решения за нефакториальное время нет. Пока есть идеи тока танцевать от полного графа алгоритмом Примы или Краскала (Крускала, кого как учили . Но и там куча неясностей. Буду рад любым советам, ссылкам на материалы, и, самое главное, алгоритмам

Заранее спасибо.

Пояснения.
1) Считается, что "поток удовлетворён" если из вершины v1 в вершину v2 можно указать такой путь, где минимальная пропускная способность по всем связям больше или равна p(v1,v2). ИЛИ(!это сложнее, наверное, так что пока отложим!), Что если все вершины генерят заданные потоки, то наша сеть с этим справляется.

2) Для упрощения связи тоже (как и потоки от вершин p(v1,v2)=p(v2,v1) )можно считать двусторонними — то есть пропускная способность в одну сторону равна пропускной способности в другую сторону.

3) Стоимость связи (допустим) вычисляется по ф-ле $$$=k1*length + k2*width; Где length — длина связи, width — её пропускная способность. Коэффициенты считаем данными.