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'` - Алгоритм по умолчанию. Использует алгоритм Голдберга, который использует общий метод, известный как prelow-push. Сложность времени `O(N^2sqrt(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' - Алгоритм по умолчанию. Использует алгоритм Голдберга, который использует общий метод, известный как prelow-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] Эдмондс, Дж. и Карп, Р.М. (1972). Теоретические улучшения алгоритмической эффективности для проблем сетевого потока. Журнал ACM 19, 248-264.

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

[3] Сиек, Дж. Г., Ли, L-Q, и Люмсдейн, А. (2002). Руководство пользователя и справочное руководство библиотеки Boost Graph (Upper Saddle River, NJ: Pearson Education).

См. также

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

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