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