Сокращенный из блока древовидный граф
tree = bctree(G)[tree,ind]
= bctree(G)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.
Двусвязный компонент графика максимально biconnected подграф. График является biconnected, если это не содержит вершин сокращения.
Разложение графика в его двусвязные компоненты помогает измериться, насколько имеющий хорошие связи график. Можно разложить любой связный граф на дерево двусвязных компонентов, названных сокращенным из блока деревом. Блоки в дереве присоединяются в разделяемых вершинах, которые являются вершинами сокращения.
Рисунок изображает:
(a) Неориентированный граф с 11 узлами.
(b) Пять двусвязных компонентов графика, с вершинами сокращения исходного графика, окрашенного для каждого компонента, которому они принадлежат.
(c) Сокращенное из блока дерево графика, который содержит узел для каждого двусвязного компонента (как большие круги) и узел для каждой вершины сокращения (как меньшие разноцветные круги). В сокращенном из блока дереве ребро соединяет каждую вершину сокращения с каждым компонентом, которому это принадлежит.
