Максимальный расход на графике
mf = maxflow(G,s,t)s и t. Если график G невзвешенный (то есть G.Edges не содержит переменную Weight), то maxflow рассматривает все рёбра графа как имеющие вес, равный 1.
Создание и печать взвешенного графика. Взвешенные кромки представляют пропускную способность потока.
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')
