Максимальный поток в графике
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')
