Исключение циклических потоков из графа

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

Например, если у меня есть граф с вершинами A, B и C с потоками 1 из A → B, 2 из B → C и 3 из C → A, тогда я могу переписать это без потока из A → B, 1 из B → C и 2 из C → A. Количество ребер в графе уменьшилось с 3 до 2, и результирующий граф является ациклическим.

Какой алгоритм (ы), если есть, решает эту проблему?

5
задан templatetypedef 20 March 2011 в 19:06
поделиться