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