`Graph`::`minimumSpanningTree`

Создает 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) создает минимальное дерево охвата согласно затратам на ребра и возвращает список с двумя объектами. Первой является таблица, состоящая из используемых ребер и их затрат. Второй объект является номером, содержащим сумму всех затрат ребра.

Примеры

Пример 1

Следующий график 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))

Пример 2

Возможно, вместо весов существует интерес к получению 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
  )
)

Параметры

G

Graph

Опции

`SearchFor`	Может или быть `Costs` или `Weights`. Значением по умолчанию является `Weights`
`ReturnAsTable`	Если не использовано, График возвращен, в противном случае список, содержащий таблицу и сумму весов/затрат ребра.

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

График, состоящий из MST. Только если ReturnAsTable был задан, список, содержащий таблицу и номер, возвращен. Таблица содержит ребра или с весами или с затратами на каждое ребро, и номер является суммой всех ребер.

Документация