Graph::minCut

Вычисляет минимальное сокращение

Блокноты MuPAD® будут демонтированы в будущем релизе. Используйте live скрипты MATLAB® вместо этого.

Live скрипты MATLAB поддерживают большую часть функциональности MuPAD, хотя существуют некоторые различия. Для получения дополнительной информации смотрите, Преобразуют Notebook MuPAD в Live скрипты MATLAB.

Синтаксис

Graph::minCut(G, q, s)

Описание

Graph::minCut(G,q,s) вычисляет минимальное сокращение G это разделяет q от s, т.е. подмножество T из набора S из ребер G таким образом, что каждый путь от q tos содержит по крайней мере одно ребро в T. Сокращение минимально относительно мощностей ребер.

Graph::minCut(G,q,s) возвращает последовательность, состоящую из значения сокращения (сумма веса ребра ребер сокращения) и список с ребрами сокращения.

Обратите внимание на то, что q разделяется от s, не наоборот.

Примеры

Пример 1

В полном графике вершина может быть разделена от другого только путем сокращения всех ребер, запускающихся в первой вершине:

G1 := Graph::createCompleteGraph(4):
Graph::minCut(G1, [1], [4])

Пример 2

В следующем примере, ребре от вершины q к вершине 1 возможно, использовался также, но его способность ребра выше, чем то из используемого ребра, таким образом, minimality условие устраняет этот выбор:

V := [1, 2, 3, q, s]:
Edge := [[q, 1], [1, 2], [1, 3], [2, 3], [3, s]]:
up := [5, 2, 6, 6, 1]:
G2 := Graph(V, Edge, EdgeWeights = up, Directed):
Graph::minCut(G2, [q], [s])

Нет никакого пути от вершины s к вершине q (или любая другая вершина Графика), таким образом, никакое сокращение не необходимо, чтобы разделить s от q:

Graph::minCut(G2, [s], [q])

Параметры

qS

Вершины, которые должны быть заданы в G

G

График

Возвращаемые значения

Последовательность, состоя из “значения сокращения” и списка ребер сокращается

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