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 |
|
График |
Последовательность, состоя из “значения сокращения” и списка ребер сокращается