помогите разобраться с модифицированным алгоритмом Крускала

[DarkWingDuck]

Прошу помощи у тех, кто разбирается в теории графов.

Как известно, чтобы найти максимальный поток в транспортной сети, используется метод Форда-Фалкерсона. Мне нужно решить проблему минимизации потока в сети. Я нашел статью, где это делается с помощью модифицированного алгоритма Крускала, но я не понимаю, верно ли это решение.

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

И есть N процессоров, на которые можно распределить эти задачи. Каждый процессор может выполнять одновременно несколько задач.

Проблема в том, чтобы распределить задачи на процессоры так, чтобы поток данных между процессорами был минимальным. Разумеется, все процессоры должны быть заняты.

Цитата:

В данном примере алгоритма, основанного на построении остовного дерева максимального веса, используется принцип исключения дуг наибольшего веса из неравенства, ограничивающего суммарный поток в сети. Распределяя разные задачи на один и тот же процессор, мы их как бы объединяем, и соединяющая их дуга исключается из суммы межпроцессорных потоков. Следовательно, если мы попытаемся исключить из этой суммы дуги с максимальными потоками, то этим обеспечивается минимизация потока данных в сети.

Рассмотрим задачу построения остовного дерева с максимальной суммой весов дуг (МОД для краткости). Вес дуги (i, j) в данном случае – это поток $f_{ij}$. Любое поддерево МОДа будет называться фрагментом. Заметим, что узел может рассматриваться как фрагмент. Дуга, имеющая один узел во фрагменте, а другой узел – вне этого фрагмента, называется дугой, уходящей от фрагмента.

Утверждение. Пусть L – некоторый заданный фрагмент МОДа, а u = (i, j) – дуга максимального веса, уходящая от фрагмента L, причём узел j не входит в L. Тогда, если к L добавить дугу u и узел j, то получится фрагмент МОДа.

Данное утверждение используется в качестве основы для алгоритмов построения МОД. Идея алгоритма Крускала состоит в том, что берутся несколько произвольных вершин как начальные фрагменты, и затем эти фрагменты увеличиваются путем последовательного добавления уходящих дуг минимального веса. Настанет момент, когда какие-либо пары фрагментов соедининяются дугой, имеющей минимальный вес среди дуг, добавление которых не создаёт цикла. Алгоритм заканчивает работу после N-1 итерации.



На этих принципах основан следующий алгоритм оптимального распределения для графа потоков данных любого вида:

1) Выбрать N задач с максимальной сложностью, где N – число процессоров, пусть это задачи $v_{k_1}, v_{k_2}, \dots, v_{k_N}$.

2) Распределить эти задачи по одной на каждый процессор. Вершины на каждом процессоре (с номерами $V(j)$) будут составлять N начальных фрагментов МОДа.

3) Выбрать наименее загруженный процессор, пусть $P_{j_1}$.

4) Найти ребро максимального веса, уходящее от$j_1$-ого фрагмента, пусть на внешнем конце ребра находится задача $v_{k_i}$.

5) Распределить $v_{k_i}$ на процессор $P_{j_1}$.

6) Переход к шагу 3, если еще не все задачи распределены.

Курсивом я обозначил то, что должно разъяснить идею, но я все равно не до конца понимаю, что здесь происходит.

1. Правильно ли работает алгоритм? И действительно ли он дает сеть с минимальным потоком?
2. Что делать с получившимся максимальным остовым деревом?

Я не понимаю, как задачи распределяются на процессоры. Вот в результате, по идее, мне нужен граф, в вершинах которого процессоры, а ребра графа соответствуют каналам между ними. Плюс рядом с процессорами помечаем, какие задачи на них выполняются, а к ребрам подписываем трафик.

Но как в действительности интерпретировать получившийся после алгоритма граф?

Помогите, пожалуйста, это по идее должно быть просто, но я уже голову себе сломал.