Максимальный поток в графике
mf = maxflow(G,s,t)mf = maxflow(G,s,t,algorithm)[mf,GF] = maxflow(___)[mf,GF,cs,ct] = maxflow(___)mf = maxflow(G,s,t) s и t. Если график, G не взвешен (то есть, G.Edges не содержит переменный Weight), то maxflow обрабатывает все края графика как наличие веса, равного 1.
mf = maxflow(G,s,t,algorithm) G является ориентированным графом.
[mf,GF] = maxflow(___) GF, с помощью любого из входных параметров в предыдущих синтаксисах. GF формируется с помощью только края в G, которые имеют ненулевые значения потока.
[mf,GF,cs,ct] = maxflow(___) cs и ct, представляя минимальное сокращение, сопоставленное с максимальным потоком.
Создайте и постройте график взвешенного графика. Взвешенные края представляют пропускные способности.
s = [1 1 2 2 3 4 4 4 5 5]; t = [2 3 3 4 5 3 5 6 4 6]; weights = [0.77 0.44 0.67 0.75 0.89 0.90 2 0.76 1 1]; G = digraph(s,t,weights); plot(G,'EdgeLabel',G.Edges.Weight,'Layout','layered');
Решите, что максимум вытекает из узла 1 к узлу 6.
mf = maxflow(G,1,6)
mf = 1.2100
Создайте и постройте график. Взвешенные края представляют пропускные способности.
s = [1 1 2 2 3 3 4];
t = [2 3 3 4 4 5 5];
weights = [10 6 15 5 10 3 8];
G = digraph(s,t,weights);
H = plot(G,'EdgeLabel',G.Edges.Weight);
Найдите максимальное значение потока между узлом 1 и узлом 5. Задайте 'augmentpath', чтобы использовать алгоритм Форда-Фалкерсона и использовать два выходных параметров, чтобы возвратить график ненулевых потоков.
[mf,GF] = maxflow(G,1,5,'augmentpath')mf = 11
GF =
digraph with properties:
Edges: [6x2 table]
Nodes: [5x0 table]
Подсветите и маркируйте график ненулевых потоков.
H.EdgeLabel = {};
highlight(H,GF,'EdgeColor','r','LineWidth',2);
st = GF.Edges.EndNodes;
labeledge(H,st(:,1),st(:,2),GF.Edges.Weight);
Создайте и постройте график взвешенного графика. Вес ребра представляет пропускные способности.
s = [1 1 2 3 3 4 4 5 5]; t = [2 3 3 2 5 5 6 4 6]; weights = [0.77 0.44 0.67 0.69 0.73 2 0.78 1 1]; G = digraph(s,t,weights); plot(G,'EdgeLabel',G.Edges.Weight,'Layout','layered')
Найдите максимальный поток и минимальное сокращение графика.
[mf,~,cs,ct] = maxflow(G,1,6)
mf = 0.7300
cs = 3×1
1
2
3
ct = 3×1
4
5
6
Постройте график минимального сокращения, с помощью узлов cs в качестве источников и узлов ct как приемники. Подсветите узлы cs, столь же красные и узлы ct как зеленый. Обратите внимание на то, что вес края, который соединяет эти два набора узлов, равен максимальному потоку.
H = plot(G,'Layout','layered','Sources',cs,'Sinks',ct, ... 'EdgeLabel',G.Edges.Weight); highlight(H,cs,'NodeColor','red') highlight(H,ct,'NodeColor','green')
