Вычислите максимальное течение в ориентированном графе
[
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). Варианты:
|
Совет
Для получения вводной информации о функциях теории графиков, см. «Функции теории графиков».
[
вычисляет максимальное течение ориентированного графа 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(
позволяет вам задать алгоритм, используемый для поиска минимального покрывающего дерева (MST). Варианты:G
, 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).
graphallshortestpaths
| graphconncomp
| graphisdag
| graphisomorphism
| graphisspantree
| graphminspantree
| graphpred2path
| graphshortestpath
| graphtopoorder
| graphtraverse
| maxflow