graphmaxflow

Вычислите максимальное течение в ориентированном графе

Синтаксис

[MaxFlow, FlowMatrix, Cut] = graphmaxflow(G, SNode, TNode)
[...] = graphmaxflow(G, SNode, TNode, ...'Capacity', CapacityValue, ...)
[...] = graphmaxflow(G, SNode, TNode, ...'Method', MethodValue, ...)

Аргументы

G N-на-N разреженная матрица, которая представляет ориентированный граф. Ненулевые значения в матричных G представление емкости ребер.
SNodeУзел в G.
TNodeУзел в G.
CapacityValueВектор-столбец, который задает пользовательские мощности для ребер в матрице G. Он должен иметь одну запись для каждого ненулевого значения ( ребра) в матрице G. Порядок пользовательских мощностей в векторе должен совпадать с порядком ненулевых значений в матрице G при прохождении по столбцу. По умолчанию graphmaxflow получает информацию о емкости из ненулевых значений в матрице G.
MethodValueВектор символов, которая задает алгоритм, используемый для поиска минимального покрывающего дерева (MST). Варианты:
  • 'Edmonds' - Использует алгоритм Эдмондса и Карпа, реализация которого основана на изменении, называемой алгоритмом маркировки. Сложность во времени O(N*E^2), где N и E являются числом узлов и кромками соответственно.

  • 'Goldberg' - Алгоритм по умолчанию. Использует алгоритм Голдберга, который использует родовой метод, известный как preflow-push. Сложность во времени O(N^2*sqrt(E)), где N и E являются числом узлов и кромками соответственно.

Описание

Совет

Для получения вводной информации о функциях теории графиков, см. «Функции теории графиков».

[MaxFlow, FlowMatrix, Cut] = graphmaxflow(G, SNode, TNode)вычисляет максимальное течение ориентированного графа G от узла SNode к узлу TNode. Входные G является N-на-N разреженной матрицей, которая представляет ориентированный граф. Ненулевые значения в матричных G представление емкости ребер. Выходные MaxFlow является максимальным потоком и FlowMatrix является разреженной матрицей со всеми значениями потока для каждого ребра. FlowMatrix(X, Y) - поток из узла X к узлу Y. Выходные Cut является логическим вектором-строкой, указывающим узлы, подключенные к SNode после вычисления минимального среза между SNode и TNode. Если существует несколько решений задачи минимального разреза, то Cut является матрицей.

Совет

Алгоритм, который определяет Cut, все минимальные вырезы, имеет временную сложность O (2 ^ N), где N является числом узлов. Если эта информация не нужна, используйте graphmaxflow функция без третьего выхода.

[...] = graphmaxflow (G, SNode, TNode ... 'PropertyName', PropertyValue, ...) вызывает graphmaxflow с необязательными свойствами, которые используют пары имя/значение свойства. Можно задать одно или несколько свойств в любом порядке. Каждый PropertyName должны быть заключены в одинарные кавычки и нечувствительны к регистру. Эти имена свойства/пары значения свойств следующие:

[...] = graphmaxflow(G, SNode, TNode, ...'Capacity', CapacityValue, ...) позволяет задать пользовательскую емкость для ребер. CapacityValue является вектором-столбцом, имеющим одну запись для каждого ненулевого значения (края) в матрице G. Порядок пользовательских мощностей в векторе должен совпадать с порядком ненулевых значений в матрице G при прохождении по столбцу. По умолчанию graphmaxflow получает информацию о емкости из ненулевых значений в матрице G.

[...] = graphmaxflow(G, SNode, TNode, ...'Method', MethodValue, ...) позволяет вам задать алгоритм, используемый для поиска минимального покрывающего дерева (MST). Варианты:

  • 'Edmonds' - Использует алгоритм Эдмондса и Карпа, реализация которого основана на изменении, называемой алгоритмом маркировки. Сложность во времени O(N*E^2), где N и E являются числом узлов и кромками соответственно.

  • 'Goldberg' - Алгоритм по умолчанию. Использует алгоритм Голдберга, который использует родовой метод, известный как preflow-push. Сложность во времени O(N^2*sqrt(E)), где N и E являются числом узлов и кромками соответственно.

Примеры

свернуть все

Этот пример показывает, как вычислить максимальное течение в ориентированном графе.

Создайте ориентированный граф с шестью узлами и восемью ребрами.

cm = sparse([1 1 2 2 3 3 4 5],[2 3 4 5 4 5 6 6],...
     [2 3 3 1 1 1 2 3],6,6)
cm = 
   (1,2)        2
   (1,3)        3
   (2,4)        3
   (3,4)        1
   (2,5)        1
   (3,5)        1
   (4,6)        2
   (5,6)        3

Вычислите максимальный поток в графике от узла 1 до узла 6.

[M,F,K] = graphmaxflow(cm,1,6)
M = 4
F = 
   (1,2)        2
   (1,3)        2
   (2,4)        1
   (3,4)        1
   (2,5)        1
   (3,5)        1
   (4,6)        2
   (5,6)        2

K = 2x6 logical array

   1   1   1   1   0   0
   1   0   1   0   0   0

Заметьте, что K является матрицей с двумя строками, потому что существует два возможных решения задачи минимального выреза.

Просмотр графика с исходными емкостями.

h = view(biograph(cm,[],'ShowWeights','on'))

Figure Biograph Viewer 1 contains an axes. The axes contains 36 objects of type line, patch, text.

Biograph object with 6 nodes and 8 edges.

Просмотрите график с вычисленными максимальными потоками.

view(biograph(F,[],'ShowWeights','on'))

Figure Biograph Viewer 2 contains an axes. The axes contains 36 objects of type line, patch, text.

Показать одно решение задачи минимального выреза в исходном графике.

set(h.Nodes(K(1,:)),'Color',[1 0 0])

Figure Biograph Viewer 1 contains an axes. The axes contains 36 objects of type line, patch, text.

Ссылки

[1] Edmonds, J. and Karp, R.M. (1972). Теоретические улучшения алгоритмической эффективности для задач сетевого потока. Журнал ACM 19, 248-264.

[2] Голдберг, А. В. (1985). Новый алгоритм максимального расхода. MIT Technical Report MIT/LCS/TM-291, Лаборатория компьютерных наук, MIT.

[3] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). Руководство пользователя библиотеки График (Upper Saddle River, NJ: Pearson Education).

Введенный в R2006b
Для просмотра документации необходимо авторизоваться на сайте