Сокращенный из блока древовидный граф
tree = bctree(G)[tree,ind] = bctree(G)tree = bctree(G) G, такой, что каждый узел в tree представляет или двусвязный компонент или вершину сокращения G. Узел, представляющий вершину сокращения, соединяется со всеми узлами, представляющими двусвязные компоненты, которые содержат ту вершину сокращения.
[tree,ind] = bctree(G) G в узлы tree.
Вычислите сокращенное из блока дерево графика, просмотрите получившиеся свойства узла, и затем подсветите вершины сокращения в графике графика.
Создайте и постройте график.
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) Сокращенное из блока дерево графика, который содержит узел для каждого двусвязного компонента (как большие круги) и узел для каждой вершины сокращения (как меньшие разноцветные круги). В сокращенном из блока дереве край соединяет каждую вершину сокращения с каждым компонентом, которому это принадлежит.
