Вычислите максимальный поток в объекте биографика
[MaxFlow, FlowMatrix, Cut] = maxflow(BGObj, SNode, TNode)
[...] = maxflow(BGObj, SNode, TNode, ...'Capacity', CapacityValue, ...)
[...] = maxflow(BGObj, SNode, TNode, ...'Method', MethodValue, ...)
BGObj | Объект биографика, созданный biograph (конструктор объектов). |
SNode | Узел в ориентированном графе, представленном матрицей смежности N на N, извлеченной из объекта биографика, BGObj. |
TNode | Узел в ориентированном графе, представленном матрицей смежности N на N, извлеченной из объекта биографика, BGObj. |
CapacityValue | Вектор-столбец, который задает пользовательские мощности для ребер в матрице смежности N на N. Он должен иметь одну запись для каждого ненулевого значения ( ребра) в матрице смежности N на N. Порядок пользовательских мощностей в векторе должен совпадать с порядком ненулевых значений в матрице смежности N на N, когда она пройдена по столбцу. По умолчанию maxflow получает информацию о пропускной способности из ненулевых значений в матрице смежности N на N. |
MethodValue | Вектор символов, которая задает алгоритм, используемый для поиска минимального покрывающего дерева (MST). Варианты:
|
Совет
Для получения вводной информации о функциях теории графиков, см. «Функции теории графиков».
[ вычисляет максимальное течение ориентированного графа, представленного матрицей смежности N на N, извлеченной из объекта биографика, MaxFlow, FlowMatrix, Cut] = maxflow(BGObj, SNode, TNode)BGObj, из узла SNode к узлу TNode. Ненулевые значения в матрице определяют емкость ребер. Выходные MaxFlow является максимальным потоком и FlowMatrix является разреженной матрицей со всеми значениями потока для каждого ребра. FlowMatrix(X, Y) - поток из узла X к узлу Y. Выходные Cut является логическим вектором-строкой, указывающим узлы, подключенные к SNode после вычисления минимального среза между SNode и TNode. Если существует несколько решений задачи минимального разреза, то Cut является матрицей.
Совет
Алгоритм, который определяет Cut, все минимальные вырезы, имеет временную сложность O (2 , где N является числом узлов. Если эта информация не нужна, используйте ^ N)maxflow способ без третьего выхода.
[...] = maxflow вызывает (BGObj, SNode, TNode ... 'PropertyName', PropertyValue, ...)maxflow с необязательными свойствами, которые используют пары имя/значение свойства. Можно задать одно или несколько свойств в любом порядке. Каждый PropertyName должны быть заключены в одинарные кавычки и нечувствительны к регистру. Эти имена свойства/пары значения свойств следующие:
[...] = maxflow( позволяет задать пользовательскую емкость для ребер. BGObj, SNode, TNode, ...'Capacity', CapacityValue, ...)CapacityValue является вектором-столбцом, имеющей одну запись для каждого ненулевого значения (ребра) в матрице смежности N на N. Порядок пользовательских мощностей в векторе должен совпадать с порядком ненулевых значений в матрице, когда она пройдена по столбцу. По умолчанию graphmaxflow получает информацию о емкости из ненулевых значений в матрице.
[...] = maxflow( позволяет вам задать алгоритм, используемый для поиска минимального покрывающего дерева (MST). Варианты:BGObj, SNode, TNode, ...'Method', MethodValue, ...)
'Edmonds' - Использует алгоритм Эдмондса и Карпа, реализация которого основана на изменении, называемой алгоритмом маркировки. Сложность во времени O(N*E^2), где N и E являются числом узлов и кромками соответственно.
'Goldberg' - Алгоритм по умолчанию. Использует алгоритм Голдберга, который использует родовой метод, известный как preflow-push. Сложность во времени O(N^2*sqrt(E)), где N и E являются числом узлов и кромками соответственно.
[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).
allshortestpaths | biograph | conncomp | graphmaxflow | isdag | isomorphism | isspantree | minspantree | shortestpath | topoorder | traverse
