График::Вычисляет максимальный поток через график
Блокноты 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, максимум вытекает из одной вершины к другому, состоит из отправки одного модуля через каждую из остающихся вершин и один непосредственно, который делает три модуля в целом:
G1 := Graph::createCompleteGraph(4): Graph::maxFlow(G1, [1], [4])
Как более комплексный пример, следующий график показывает, что эта функция также находит потоки через несколько ребер, в отличие от 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 является количеством вершин в Графике.