Максимальный поток в графике
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.
Создайте и постройте взвешенный график. Взвешенные ребра представляют пропускные способности.
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')
G
Введите графикgraph
| объект digraph
Входной график, заданный как объект граф или диграф.
Используйте граф для создания неориентированного графа или диграф для создания ориентированного графа.
Пример: G = graph(1,2)
Пример: G = digraph([1 2],[2 3])
s, t
Пара узла (в качестве отдельных аргументов)Пара узла, заданная в качестве отдельных аргументов индексов узла или имен узла, чтобы указать на исходный узел и целевой узел. Эта таблица показывает различные способы относиться к узлам или их индексами узла или их именами узла.
Значение | Пример |
---|---|
Скалярный индекс узла | 1 |
Имя узла вектора символов | 'A' |
Представьте скалярное имя узла в виде строки | "A" |
Пример: mf = maxflow(G,'A','B')
Пример: mf = maxflow(G,1,10)
Типы данных: double
| char
| string
algorithm
— Максимальный алгоритм потока'searchtrees'
(значение по умолчанию) | 'augmentpath'
| 'pushrelabel'
Максимальный алгоритм потока, заданный как одна из записей в таблице.
Можно только задать опции algorithm
не по умолчанию с ориентированным графом.
Опция | Описание |
---|---|
'searchtrees' (значение по умолчанию) |
Использует алгоритм Бойков-Кольмогорова. Вычисляет максимальный поток путем построения двух деревьев поиска, сопоставленных с узлами |
'augmentpath' |
Использует алгоритм Форда-Фалкерсона. Вычисляет максимальный поток итеративно путем нахождения увеличивающегося пути в остаточном ориентированном графе. Ориентированный граф не может иметь никаких параллельных ребер противоположного направления между теми же двумя узлами, если вес одного из тех ребер не является нулем. Таким образом, если график содержит ребро |
'pushrelabel' |
Вычисляет максимальный поток путем продвижения избыточного потока узла его соседям и затем перемаркировки узла. Ориентированный граф не может иметь никаких параллельных ребер противоположного направления между теми же двумя узлами, если вес одного из тех ребер не является нулем. Таким образом, если график содержит ребро |
Пример: mf = maxflow(G,'A','D','augmentpath')
mf
— Максимальный потокМаксимальный поток, возвращенный как скаляр.
GF
— Ориентированный граф потоковдиграф Объект
Ориентированный граф потоков, возвращенных как объект digraph
. GF
содержит те же узлы как G
, но только содержит те ребра G
, которые имеют ненулевой поток. Для мультиграфов с несколькими ребрами между теми же двумя узлами GF
содержит одно ребро, отражающее поток через несколько ребер.
cs
Минимальные исходные идентификаторы узла сокращенияМинимальные исходные идентификаторы узла сокращения, возвращенные как индексы узла или имена узла.
Если s
и t
задают числовые индексы узла, то cs
и ct
также содержат индексы узла.
Если s
и t
задают имена узла, то cs
и ct
также содержат имена узла.
ct
Минимальные целевые идентификаторы узла сокращенияМинимальные целевые идентификаторы узла сокращения, возвращенные как индексы узла или имена узла.
Если s
и t
задают числовые индексы узла, то cs
и ct
также содержат индексы узла.
Если s
и t
задают имена узла, то cs
и ct
также содержат имена узла.
В контексте максимального потока ребра в графике, как рассматривается, имеют способность, как представлено весом ребра. Способность ребра является суммой потока, который может пройти через то ребро. Поэтому максимальный поток между двумя узлами в графике максимизирует объем передачи потока от исходного узла, s
, к целевому узлу, t
, на основе мощностей соединяющихся ребер.
Минимальное сокращение делит узлы ориентированного графа в два набора, cs
и ct
, такой, что сумма весов всех ребер, соединяющих cs
и ct
(вес сокращения), минимизирована. Вес минимального сокращения равен максимальному значению потока, mf
.
Записи в cs
и ct
указывают на узлы G
, сопоставленного с узлами s
и t
, соответственно. cs
и ct
удовлетворяют numel(cs) + numel(ct) = numnodes(G)
.
1. Если смысл перевода понятен, то лучше оставьте как есть и не придирайтесь к словам, синонимам и тому подобному. О вкусах не спорим.
2. Не дополняйте перевод комментариями “от себя”. В исправлении не должно появляться дополнительных смыслов и комментариев, отсутствующих в оригинале. Такие правки не получится интегрировать в алгоритме автоматического перевода.
3. Сохраняйте структуру оригинального текста - например, не разбивайте одно предложение на два.
4. Не имеет смысла однотипное исправление перевода какого-то термина во всех предложениях. Исправляйте только в одном месте. Когда Вашу правку одобрят, это исправление будет алгоритмически распространено и на другие части документации.
5. По иным вопросам, например если надо исправить заблокированное для перевода слово, обратитесь к редакторам через форму технической поддержки.