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