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

Входные параметры

свернуть все

Введите график в виде любого graph или digraph объект. Используйте graph создать неориентированного графа или digraph создать ориентированного графа.

Пример: 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

Поддержка

Для просмотра документации необходимо авторизоваться на сайте