bctree

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

свернуть все на странице

Синтаксис

tree = bctree(G)
[tree,ind] = bctree(G)

Описание

пример

tree = bctree(G) возвращает сокращенное из блока дерево графика G, такой, что каждый узел в tree представляет или двусвязный компонент или вершину сокращения G. Узел, представляющий вершину сокращения, соединяется со всеми узлами, представляющими двусвязные компоненты, которые содержат ту вершину сокращения.

пример

[tree,ind] = bctree(G) также возвращает вектор числовых индексов узла, сопоставляющих узлы G в узлы tree.

Примеры

свернуть все

Скрипт Open Live Script

Вычислите сокращенное из блока дерево графика, просмотрите получившиеся свойства узла, и затем подсветите вершины сокращения в графике графика.

Создайте и постройте график.

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')

Скрипт Open Live Script

Создайте и постройте график.

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 (false).

  • 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

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