Graph::maxFlow
Вычисляет максимальный поток через график
Блокноты MuPAD® будут демонтированы в будущем релизе. Используйте live скрипты MATLAB® вместо этого.
Live скрипты MATLAB поддерживают большую часть функциональности MuPAD, хотя существуют некоторые различия. Для получения дополнительной информации смотрите, Преобразуют Notebook MuPAD в Live скрипты MATLAB.
Синтаксис
Graph::maxFlow(G, s, t)
Описание
Graph::maxFlow(G,s,t) вычисляет максимальный поток из s к t в G относительно мощностей ребра. s и t должны быть узлы в G.
Graph::maxFlow(G,s,t) возвращает последовательность, содержащую значение потока, которое является притоком s, который равняется оттоку s, и сам поток в форме таблицы tbl с потоком от вершины v к вершине w tbl[[v,w]].
Примеры
Пример 1
В полном Графике с четырьмя вершинами и мощностями по умолчанию 1, максимум течет из одной вершины к другому, состоит из отправки одного модуля через каждую из остающихся вершин и один непосредственно, который делает три модуля в целом:
G1 := Graph::createCompleteGraph(4): Graph::maxFlow(G1, [1], [4])
Пример 2
Как более комплексный пример, следующий график показывает, что эта функция также находит потоки через несколько ребер, в отличие от Graph::admissibleFlow, который только работает над полностью описанными потоками:
V := [1, 2, 3, s, t]: Edge := [[s, 1], [t, 2], [1, 2], [1, 3], [2, 3], [3, t]]: up := [5, 5, 2, 6, 6, 1]: G2 := Graph(V, Edge, EdgeCosts = up, Directed): Graph::maxFlow(G2, [s], [t])
Параметры
|
График |
|
Выражения (вершины в |
Возвращаемые значения
Перечислите, содержа номер и таблицу
Алгоритмы
Реализованный алгоритм является алгоритмом нажатия перед потоком Голдберга &Tarjan со стратегией выбора FIFO и точной маркировкой расстояния (“Новый подход к проблеме максимального потока”, Журнал ACM 35 (4), 1988).
Временем выполнения является O (n 3), где n является количеством вершин в Графике.