Максимальный поток в графике
возвращает максимальный поток между узлами 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')
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
объектОриентированный граф потоков, возвращенных как 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. По иным вопросам, например если надо исправить заблокированное для перевода слово, обратитесь к редакторам через форму технической поддержки.