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
, не наоборот.
В полном графике вершина может быть разделена от другого только путем сокращения всех ребер, запускающихся в первой вершине:
G1 := Graph::createCompleteGraph(4): Graph::minCut(G1, [1], [4])
В следующем примере, ребре от вершины 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])
|
Вершины, которые должны быть заданы в G |
|
График |
Последовательность, состоя из “значения сокращения” и списка ребер сокращается