bctree

Сокращенный из блока древовидный граф

Описание

пример

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.

Входные параметры

свернуть все

Введите график, заданный как graph объект. Используйте graph создать объект неориентированного графа.

Пример: G = graph(1,2)

Выходные аргументы

свернуть все

Сокращенный из блока древовидный граф, возвращенный как graph объект. tree содержит узел для каждой вершины сокращения в G и узел для каждого двусвязного компонента в G. Таблица tree.Nodes узлов содержит дополнительные атрибуты узла, чтобы описать то, что представляет каждый узел:

  • tree.Nodes.IsComponent(i) — Значение, равное логическому 1 TRUE) если узел i представляет двусвязный компонент. В противном случае значение равно и логический 0 ложь).

  • tree.Nodes.ComponentIndex(i) — Индекс, указывающий на компонент, представленный узлом i. Значение является нулем если узел i представляет вершину сокращения.

  • tree.Nodes.CutVertexIndex(i) — Индекс, указывающий на вершину сокращения, представленную узлом i. Значение является нулем если узел i представляет двусвязный компонент.

Индексы узла, возвращенные как числовой вектор. ind(i) узел в выходном графике tree это представляет узел i во входном графике G:

  • Если узел i вершина сокращения в графике G, затем ind(i) связанный узел в tree.

  • Если узел i не вершина сокращения, но принадлежит одному из двусвязных компонентов в графике G, затем ind(i) узел в tree представление того двусвязного компонента.

  • Если узел i изолированный узел в графике G, затем ind(i) нуль.

Больше о

свернуть все

Двусвязные компоненты

Двусвязный компонент графика максимально biconnected подграф. График является biconnected, если это не содержит вершин сокращения.

Разложение графика в его двусвязные компоненты помогает измериться, насколько имеющий хорошие связи график. Можно разложить любой связный граф на дерево двусвязных компонентов, названных сокращенным из блока деревом. Блоки в дереве присоединяются в разделяемых вершинах, которые являются вершинами сокращения.

Рисунок изображает:

  • (a) Неориентированный граф с 11 узлами.

  • (b) Пять двусвязных компонентов графика, с вершинами сокращения исходного графика, окрашенного для каждого компонента, которому они принадлежат.

  • (c) Сокращенное из блока дерево графика, который содержит узел для каждого двусвязного компонента (как большие круги) и узел для каждой вершины сокращения (как меньшие разноцветные круги). В сокращенном из блока дереве ребро соединяет каждую вершину сокращения с каждым компонентом, которому это принадлежит.

Сокращение вершин

Также известный как точки разборчивости, вершины сокращения являются вершинами графика, удаление которых увеличивает число связанных компонентов. На предыдущем рисунке вершины сокращения являются теми узлами больше чем с одним цветом: узлы 4, 6, и 7.

Введенный в R2017b

Для просмотра документации необходимо авторизоваться на сайте