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(NE^2)`, где `N` и `E` количество узлов и ребер соответственно. `'Goldberg'` — Алгоритм по умолчанию. Использует алгоритм Голдберга, который использует общий метод, известный как нажатие перед потоком. Временной сложностью является `O(N^2sqrt(E))`, где `N` и `E` количество узлов и ребер соответственно.

Описание

Совет

Дополнительные сведения о функциях теории графов см. в Функциях Теории графов.

[MaxFlow, FlowMatrix, Cut] = graphmaxflow(G, SNode, TNode)вычисляет максимальный поток ориентированного графа G от узла SNode к узлу TNode. Введите G N на n разреженная матрица, которая представляет ориентированного графа. Ненулевые записи в матричном G представляйте мощности ребер. Выведите MaxFlow максимальный поток и FlowMatrix разреженная матрица со всеми значениями потока для каждого ребра. FlowMatrixXY) поток от узла 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' — Алгоритм по умолчанию. Использует алгоритм Голдберга, который использует общий метод, известный как нажатие перед потоком. Временной сложностью является O(N^2*sqrt(E)), где N и E количество узлов и ребер соответственно.

Примеры

свернуть все

Вычислите максимальный поток

Скрипт Open Live Script

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

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

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 является матрицей 2D строки, потому что существует два возможных решения минимальной проблемы сокращения.

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

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] Эдмондс, J. и Карп, R.M. (1972). Теоретические улучшения алгоритмического КПД для сетевых проблем потока. Журнал ACM 19, 248-264.

[2] Голдберг, A.V. (1985). Новый Алгоритм Потока Max. Технический отчет MIT MIT/LCS/TM-291, Лаборатория для Информатики, MIT.

[3] Siek, J.G., Ли, L-Q и Lumsdaine, A. (2002). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).

Представленный в R2006b

Документация