Exponenta Banner

maxflow

Максимальный поток в графике

свернуть все на странице

Синтаксис

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.

пример

mf = maxflow(G,s,t,algorithm) задает максимальный алгоритм потока, чтобы использовать. Этот синтаксис только доступен, если G является ориентированным графом.

пример

[mf,GF] = maxflow(___) также возвращает объект ориентированного графа, GF, с помощью любого из входных параметров в предыдущих синтаксисах. GF формируется с помощью только ребра в G, которые имеют ненулевые значения потока.

пример

[mf,GF,cs,ct] = maxflow(___) дополнительно возвращает входные и выходные идентификаторы узла, cs и ct, представляя минимальное сокращение, сопоставленное с максимальным потоком.

Примеры

свернуть все

Скрипт Open Live Script

Создайте и постройте взвешенный график. Взвешенные ребра представляют пропускные способности.

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
Скрипт Open Live Script

Создайте и постройте график. Взвешенные ребра представляют пропускные способности.

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);

Скрипт Open Live Script

Создайте и постройте взвешенный график. Вес ребра представляет пропускные способности.

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(1,2)

Пример: G = digraph([1 2],[2 3])

Пара узла, заданная в качестве отдельных аргументов индексов узла или имен узла, чтобы указать на исходный узел и целевой узел. Эта таблица показывает различные способы относиться к узлам или их индексами узла или их именами узла.

ЗначениеПример
Скалярный индекс узла1
Имя узла вектора символов'A'
Представьте скалярное имя узла в виде строки"A"

Пример: mf = maxflow(G,'A','B')

Пример: mf = maxflow(G,1,10)

Типы данных: double | char | string

Максимальный алгоритм потока, заданный как одна из записей в таблице.

Примечание

Можно только задать опции algorithm не по умолчанию с ориентированным графом.

ОпцияОписание
'searchtrees' (значение по умолчанию)

Использует алгоритм Бойков-Кольмогорова. Вычисляет максимальный поток путем построения двух деревьев поиска, сопоставленных с узлами s и t.

'augmentpath'

Использует алгоритм Форда-Фалкерсона. Вычисляет максимальный поток итеративно путем нахождения увеличивающегося пути в остаточном ориентированном графе.

Ориентированный граф не может иметь никаких параллельных ребер противоположного направления между теми же двумя узлами, если вес одного из тех ребер не является нулем. Таким образом, если график содержит ребро [i j], то это может содержать противоположное ребро [j i], только если вес [i j] является нулем, и/или вес [j i] является нулем.

'pushrelabel'

Вычисляет максимальный поток путем продвижения избыточного потока узла его соседям и затем перемаркировки узла.

Ориентированный граф не может иметь никаких параллельных ребер противоположного направления между теми же двумя узлами, если вес одного из тех ребер не является нулем. Таким образом, если график содержит ребро [i j], то это может содержать противоположное ребро [j i], только если вес [i j] является нулем, и/или вес [j i] является нулем.

Пример: mf = maxflow(G,'A','D','augmentpath')

Выходные аргументы

свернуть все

Максимальный поток, возвращенный как скаляр.

Ориентированный граф потоков, возвращенных как объект digraph. GF содержит те же узлы как G, но только содержит те ребра G, которые имеют ненулевой поток. Для мультиграфов с несколькими ребрами между теми же двумя узлами GF содержит одно ребро, отражающее поток через несколько ребер.

Минимальные исходные идентификаторы узла сокращения, возвращенные как индексы узла или имена узла.

  • Если s и t задают числовые индексы узла, то cs и ct также содержат индексы узла.

  • Если s и t задают имена узла, то cs и 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).

Смотрите также

|

Введенный в R2015b

Документация MATLAB
Поддержка