Минимальное дерево охвата графика
T = minspantree(G)
T = minspantree(G,Name,Value)
[T,pred]
= minspantree(___)
возвращает минимальное дерево охвата, T
= minspantree(G
)T
, для графика G
.
дополнительные опции использования заданы одним или несколькими Аргументами пары "имя-значение". Например, T
= minspantree(G
,Name,Value
)minspantree(G,'Method','sparse')
использует алгоритм Краскэла для вычисления минимального дерева охвата.
Создайте и постройте график куба со взвешенными ребрами.
s = [1 1 1 2 5 3 6 4 7 8 8 8];
t = [2 3 4 5 3 6 4 7 2 6 7 5];
weights = [100 10 10 10 10 20 10 30 50 10 70 10];
G = graph(s,t,weights);
p = plot(G,'EdgeLabel',G.Edges.Weight);
Вычислите и постройте минимальное дерево охвата графика сверху графика. T
содержит те же узлы как G
, но подмножество ребер.
[T,pred] = minspantree(G); highlight(p,T)
Создайте и постройте график, который имеет несколько компонентов.
s = {'a' 'a' 'a' 'b' 'b' 'c' 'e' 'e' 'f' 'f' 'f' 'f' 'g' 'g'}; t = {'b' 'c' 'd' 'c' 'd' 'd' 'f' 'g' 'g' 'h' 'i' 'j' 'i' 'j'}; G = graph(s,t); p = plot(G,'Layout','layered');
Найдите минимальный лес охвата для графика, запускающегося в узле i
. Подсветите получившийся лес в графике. Имена узла графика перенесены в минимальный древовидный граф охвата.
[T,pred] = minspantree(G,'Type','forest','Root',findnode(G,'i')); highlight(p,T)
Используйте вектор узлов-предшественников, pred
, чтобы создать направленную версию минимального леса охвата. Все ребра в этом дереве направлены далеко от корневых узлов в каждом компоненте (узлы i
и a
).
rootedTree = digraph(pred(pred~=0),find(pred~=0),[],G.Nodes.Name); plot(rootedTree)
G
Введите графикgraph
Введите график, заданный как объект graph
. Используйте graph
, чтобы создать объект неориентированного графа.
Пример: G = graph(1,2)
Укажите необязательные аргументы в виде пар ""имя, значение"", разделенных запятыми.
Имя (Name) — это имя аргумента, а значение (Value) — соответствующее значение.
Name
должен появиться в кавычках. Вы можете задать несколько аргументов в виде пар имен и значений в любом порядке, например: Name1, Value1, ..., NameN, ValueN.
[T,pred] = minspantree(G,'Method','sparse')
'Method'
— Минимальный алгоритм связующего дерева'dense'
(значение по умолчанию) | 'sparse'
Минимальный алгоритм связующего дерева, заданный как пара, разделенная запятой, состоящая из 'Method'
и одна из опций в таблице.
Опция | Описание |
---|---|
'dense' (значение по умолчанию) | Алгоритм Прима. Этот алгоритм запускается в корневом узле и добавляет ребра в дерево при пересечении графика. |
'sparse' | Алгоритм Краскэла. Эти виды алгоритма все ребра в развес, и затем добавляют их в дерево, если они не создают цикл. |
'Root'
— Корневой узел1
(значение по умолчанию) | индекс узла | имя узлаКорневой узел, заданный как пара, разделенная запятой, состоящая из 'Root'
и индекса узла или имени узла. Корневым узлом по умолчанию является 1
.
Если 'Method'
является 'dense'
(значение по умолчанию), то корневой узел является стартовым узлом.
Если 'Method'
является 'sparse'
, то корневой узел используется только, чтобы вычислить pred
, вектор узлов-предшественников.
Можно задать корневой узел в любом из этих форматов:
Значение | Пример |
---|---|
Скалярный индекс узла | 1 |
Имя узла вектора символов | 'A' |
Представьте скалярное имя узла в виде строки | "A" |
Ввод
Тип минимального дерева охвата'tree'
(значение по умолчанию) | 'forest'
Тип минимального дерева охвата, заданного как пара, разделенная запятой, состоящая из 'Type'
и одна из опций в таблице.
Опция | Описание |
---|---|
'tree' |
Только одно дерево возвращено. Дерево содержит корневой узел. |
'forest' |
Лес минимальных деревьев охвата возвращен. Другими словами, задайте |
T
Минимальное дерево охватаgraph
Минимальное дерево охвата, возвращенное как объект graph
.
pred
Узлы-предшественникиУзлы-предшественники, возвращенные как вектор индексов узла. pred(I)
является индексом узла предшественника узла I
. Условно, pred(rootNode) = 0
. Если Type
является 'tree'
, то pred(I) = NaN
для всех узлов I
, которые не находятся в том же компоненте как корневой узел.
pred
задает направленную версию минимального дерева охвата со всеми ребрами, направленными далеко от корневого узла.
Для связных графов дерево охвата является подграфом, который соединяет каждый узел в графике, но не содержит циклов. Может быть много деревьев охвата для любого данного графика. Путем присвоения веса каждому ребру различным деревьям охвата присваивают номер для общей массы их ребер. Минимальное дерево охвата является затем деревом охвата, ребра которого имеют наименьшее количество общей массы.
Для графиков с равным весом ребра все деревья охвата являются минимальными деревьями охвата, начиная с пересечения узлов n
требует ребер n-1
.
1. Если смысл перевода понятен, то лучше оставьте как есть и не придирайтесь к словам, синонимам и тому подобному. О вкусах не спорим.
2. Не дополняйте перевод комментариями “от себя”. В исправлении не должно появляться дополнительных смыслов и комментариев, отсутствующих в оригинале. Такие правки не получится интегрировать в алгоритме автоматического перевода.
3. Сохраняйте структуру оригинального текста - например, не разбивайте одно предложение на два.
4. Не имеет смысла однотипное исправление перевода какого-то термина во всех предложениях. Исправляйте только в одном месте. Когда Вашу правку одобрят, это исправление будет алгоритмически распространено и на другие части документации.
5. По иным вопросам, например если надо исправить заблокированное для перевода слово, обратитесь к редакторам через форму технической поддержки.