bctree
Древовидный граф с блочным графиком
Описание
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) Блочное дерево графика, которое содержит узел для каждого двухсоединенного компонента (как большие круги) и узел для каждой вырезанной вершины (как меньшие многоцветные круги). В дереве вырезов блоков ребра соединяет каждую вершину выреза с каждым компонентом, к которому она принадлежит.
