Вычислите максимальный поток в объекте биографика
[
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