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, представляющий минимальный разрез, сопоставленный с максимальным потоком.

Примеры

свернуть все

Открыть 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');

Figure contains an axes. The axes contains an object of type graphplot.

Определите максимальный поток от узла 1 до узла 6.

mf = maxflow(G,1,6)
mf = 1.2100
Открыть 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);

Figure contains an axes. The axes contains an object of type graphplot.

Найдите максимальное значение потока между узлом 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);

Figure contains an axes. The axes contains an object of type graphplot.

Открыть 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')

Figure contains an axes. The axes contains an object of type graphplot.

Найдите максимальный поток и минимальный разрез графика.

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

Figure contains an axes. The axes contains an object of type graphplot.

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

свернуть все

Входной график, заданный как 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

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

Примечание

Вы можете задать только nondefault 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

Поддержка

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