График::Создает MST
Блокноты MuPAD® будут демонтированы в будущем релизе. Используйте live скрипты MATLAB® вместо этого.
Live скрипты MATLAB поддерживают большую часть функциональности MuPAD, хотя существуют некоторые различия. Для получения дополнительной информации смотрите, Преобразовывают Notebook MuPAD в Live скрипты MATLAB.
Graph::minimumSpanningTree(G, <SearchFor = Weights | Costs>, <ReturnAsTable>)
Graph::minimumSpanningTree(G) создает минимальное дерево охвата Graph G согласно весам ребер и возвращает График, состоящий только из них. Тот же результат был бы достигнут с помощью Graph::minimumSpanningTree(G, SearchFor = Weights)
Graph::minimumSpanningTree(G, SearchFor = Costs) создает минимальное дерево охвата согласно затратам на ребра и возвращает График, состоящий только из них.
Graph::minimumSpanningTree(G, ReturnAsTable) создает минимальное дерево охвата согласно весам ребер и возвращает список с двумя объектами. Первой является таблица, состоящая из используемых ребер и их весов. Второй объект является номером, содержащим сумму всего веса ребра. (Тот же результат может быть достигнут с помощью: Graph::minimumSpanningTree(G, SearchFor=Weights, ReturnAsTable).)
Graph::minimumSpanningTree(G, SearchFor=Costs, ReturnAsTable) создает минимальное дерево охвата согласно затратам на ребра и возвращает список с двумя объектами. Первой является таблица, состоящая из используемых ребер и их затрат. Второй объект является номером, содержащим сумму всех затрат ребра.
Следующий график G будет использоваться во всех примерах. Для получения дополнительной информации на формате G, смотрите Graph. (Взгляните на ребро [c, f]. Это ребро ответственно за различные выходные параметры или Costs, или Weights был выбран.)
G := Graph([a, b, c, d, e, f, g, h, i],
[[a, b], [a, h], [b, h], [b, c], [c, d], [d, f], [d, e],
[f, e], [h, g], [g, f], [c, i], [h, i], [g, i], [c, f]],
EdgeWeights = [4, 8, 11, 8, 7, 14, 9, 10, 1, 2, 2, 7, 6, 4],
EdgeCosts = [4, 8, 11, 8, 7, 14, 9, 10, 1, 2, 2, 7, 6, 12]):Мы построим этот график и все графики, выведенные от него с помощью Graph::plotGridGraph со следующими опциями:
plotOptions :=
VerticesPerLine=7,
VertexOrder = [
None, b, None, c, None, d, None,
a, None, i, None, None, None, e,
None, h, None, g, None, f, None]:plot(Graph::plotGridGraph(G, plotOptions))
Теперь мы используем этот График, чтобы создать минимальное дерево охвата согласно весам ребер и взглянуть, какие ребра использовались:
Graph::minimumSpanningTree(G, SearchFor = Weights, ReturnAsTable), Graph::minimumSpanningTree(G, ReturnAsTable)
Оба вызова возвращают точно те же таблицы. Это ожидалось и только показать, что это незначительно, если дополнительный SearchFor=Weights не использован.
Теперь мы хотим получить минимальное дерево охвата, возвращенное как График, таким образом, мы можем взглянуть, как оно похоже
weightMST := Graph::minimumSpanningTree(G):
plot(Graph::plotGridGraph(weightMST, plotOptions,
EdgeColor = RGB::Green))
Существует два способа отобразить оба графика одновременно:
plot(
Graph::plotGridGraph(G, plotOptions, EdgeColor = RGB::Black),
Graph::plotGridGraph(weightMST, plotOptions,
EdgeColor = RGB::Green)
)
edgesWeightMST := Graph::getEdges(weightMST):
plot(Graph::plotGridGraph(G, plotOptions,
EdgeColor = RGB::Black,
SpecialEdges = edgesWeightMST,
SpecialEdgeColor = RGB::Green))
Возможно, вместо весов существует интерес к получению MST для затрат на ребра.
G := Graph([a, b, c, d, e, f, g, h, i],
[[a, b], [a, h], [b, h], [b, c], [c, d], [d, f], [d, e],
[f, e], [h, g], [g, f], [c, i], [h, i], [g, i], [c, f]],
EdgeWeights = [4, 8, 11, 8, 7, 14, 9, 10, 1, 2, 2, 7, 6, 4],
EdgeCosts = [4, 8, 11, 8, 7, 14, 9, 10, 1, 2, 2, 7, 6, 12]):Graph::minimumSpanningTree(G, SearchFor = Costs, ReturnAsTable)
Графический вывод этого дерева охвата так же легок как выше:
costMST := Graph::minimumSpanningTree(G, SearchFor = Costs):
plot(Graph::plotGridGraph(costMST, plotOptions,
EdgeColor = RGB::Blue))
Чтобы объединить оба дерева охвата, мы используем различные ширины строки, чтобы избежать одного графика, полностью покрываемого другим:
plot(
plot::Group2d(
Graph::plotGridGraph(costMST, plotOptions,
EdgeColor = RGB::Blue),
LineWidth = 2.5
),
plot::Group2d(
Graph::plotGridGraph(G, plotOptions,
EdgeColor = RGB::Black),
Graph::plotGridGraph(weightMST, plotOptions,
EdgeColor = RGB::Green),
PointSize = 5,
LineWidth = 1
)
)
|
|
Может или быть |
|
Если не использовано, График возвращен, в противном случае список, содержащий таблицу и сумму весов/затрат ребра. |
График, состоящий из MST. Только если ReturnAsTable был задан, список, содержащий таблицу и номер, возвращен. Таблица содержит ребра или с весами или с затратами на каждое ребро, и номер является суммой всех ребер.