Сокращенный из блока древовидный граф
возвращает сокращенное из блока дерево графика tree
= bctree(G
)G
, таким образом, что каждый узел в tree
представляет или двусвязный компонент или вершину сокращения G
. Узел, представляющий вершину сокращения, соединяется со всеми узлами, представляющими двусвязные компоненты, которые содержат ту вершину сокращения.
Вычислите сокращенное из блока дерево графика, просмотрите получившиеся свойства узла, и затем подсветите вершины сокращения в графике графика.
Создайте и постройте график.
s = [1 1 2 2 3 4 4 5 6 6 7 7 8]; t = [2 3 3 4 4 5 7 6 7 10 8 9 9]; G = graph(s,t); p = plot(G);
Вычислите сокращенное из блока дерево графика и просмотрите свойства узла.
tree = bctree(G); tree.Nodes
ans=7×3 table
IsComponent ComponentIndex CutVertexIndex
___________ ______________ ______________
true 1 0
true 2 0
true 3 0
true 4 0
false 0 4
false 0 6
false 0 7
Постройте сокращенное из блока дерево с помощью красных ромбовидных маркеров в узлах, которые представляют вершины сокращения. Круговые узлы представляют двусвязные компоненты в исходном графике.
p2 = plot(tree,'MarkerSize',9); highlight(p2,5:7,'Marker','d','NodeColor','r')
Создайте и постройте график.
s = [1 1 2 2 3 4 4 5 6 6 7 7 8]; t = [2 3 3 4 4 5 7 6 7 10 8 9 9]; G = graph(s,t); p = plot(G);
Вычислите сокращенный из блока древовидный tr
из графика, и задают второй выход ix
возвратить индексы узла.
[tr,ix] = bctree(G)
tr = graph with properties: Edges: [6x1 table] Nodes: [7x3 table]
ix = 1×10
4 4 4 5 3 6 7 1 1 2
Каждый индекс ix(j)
указывает на узел в сокращенном из блока дереве, которое представляет узел j
во входном графике. Например, узел 4 в tr
представляет компонент в G
это содержит узлы 1, 2, и 3, таким образом, первые три записи в ix
все 4.
G
— Введите графикgraph
объектВведите график, заданный как graph
объект. Используйте graph
создать объект неориентированного графа.
Пример: G = graph(1,2)
tree
— Сокращенный из блока древовидный графgraph
объектСокращенный из блока древовидный граф, возвращенный как graph
объект. tree
содержит узел для каждой вершины сокращения в G
и узел для каждого двусвязного компонента в G
. Таблица tree.Nodes
узлов содержит дополнительные атрибуты узла, чтобы описать то, что представляет каждый узел:
tree.Nodes.IsComponent(i)
— Значение, равное логическому 1
TRUE
) если узел i
представляет двусвязный компонент. В противном случае значение равно и логический 0
ложь
).
tree.Nodes.ComponentIndex(i)
— Индекс, указывающий на компонент, представленный узлом i
. Значение является нулем если узел i
представляет вершину сокращения.
tree.Nodes.CutVertexIndex(i)
— Индекс, указывающий на вершину сокращения, представленную узлом i
. Значение является нулем если узел i
представляет двусвязный компонент.
ind
— Индексы узлаИндексы узла, возвращенные как числовой вектор. ind(i)
узел в выходном графике tree
это представляет узел i
во входном графике G
:
Если узел i
вершина сокращения в графике G
, затем ind(i)
связанный узел в tree
.
Если узел i
не вершина сокращения, но принадлежит одному из двусвязных компонентов в графике G
, затем ind(i)
узел в tree
представление того двусвязного компонента.
Если узел i
изолированный узел в графике G
, затем ind(i)
нуль.
Двусвязный компонент графика максимально biconnected подграф. График является biconnected, если это не содержит вершин сокращения.
Разложение графика в его двусвязные компоненты помогает измериться, насколько имеющий хорошие связи график. Можно разложить любой связный граф на дерево двусвязных компонентов, названных сокращенным из блока деревом. Блоки в дереве присоединяются в разделяемых вершинах, которые являются вершинами сокращения.
Рисунок изображает:
(a) Неориентированный граф с 11 узлами.
(b) Пять двусвязных компонентов графика, с вершинами сокращения исходного графика, окрашенного для каждого компонента, которому они принадлежат.
(c) Сокращенное из блока дерево графика, который содержит узел для каждого двусвязного компонента (как большие круги) и узел для каждой вершины сокращения (как меньшие разноцветные круги). В сокращенном из блока дереве ребро соединяет каждую вершину сокращения с каждым компонентом, которому это принадлежит.
Также известный как точки разборчивости, вершины сокращения являются вершинами графика, удаление которых увеличивает число связанных компонентов. На предыдущем рисунке вершины сокращения являются теми узлами больше чем с одним цветом: узлы 4, 6, и 7.
У вас есть модифицированная версия этого примера. Вы хотите открыть этот пример со своими редактированиями?
1. Если смысл перевода понятен, то лучше оставьте как есть и не придирайтесь к словам, синонимам и тому подобному. О вкусах не спорим.
2. Не дополняйте перевод комментариями “от себя”. В исправлении не должно появляться дополнительных смыслов и комментариев, отсутствующих в оригинале. Такие правки не получится интегрировать в алгоритме автоматического перевода.
3. Сохраняйте структуру оригинального текста - например, не разбивайте одно предложение на два.
4. Не имеет смысла однотипное исправление перевода какого-то термина во всех предложениях. Исправляйте только в одном месте. Когда Вашу правку одобрят, это исправление будет алгоритмически распространено и на другие части документации.
5. По иным вопросам, например если надо исправить заблокированное для перевода слово, обратитесь к редакторам через форму технической поддержки.