biconncomp

Компоненты графа без сочленений

Описание

пример

bins = biconncomp(G) возвращает двусвязные компоненты графика G как интервалы. Числа интервала указывают, какому двусвязному компоненту каждое ребро в графике принадлежит. Каждое ребро в G принадлежит одному двусвязному компоненту, тогда как узлы в G может принадлежать больше чем одному двусвязному компоненту. Два узла принадлежат тому же двусвязному компоненту, если удаление любого узла из графика не отключает их.

пример

bins = biconncomp(G,'OutputForm',form), где form iscell, возвращает выходной параметр как массив ячеек, таким образом что bins{j} содержит идентификаторы узла всех узлов в j компонента. Значение по умолчанию для form isvector.

пример

[bins,iC] = biconncomp(___) дополнительно возвращает индексы узла iC указание, какие узлы являются вершинами сокращения (также названный точками разборчивости).

Примеры

свернуть все

Создайте и постройте график. Окрасьте ребра, на основе которого двусвязного компонента каждое ребро принадлежит.

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,'LineWidth',2);

p.EdgeCData =  biconncomp(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);
plot(G)

Сгруппируйте вершины графика в интервалы, на основе которого двусвязного компонента (компонентов) каждый узел принадлежит. Затем цикл через каждый из интервалов и извлечения подграф для каждого двусвязного компонента. Пометьте узлы в каждом подграфе с помощью их исходных индексов узла.

bincell = biconncomp(G, 'OutputForm', 'cell');
n = length(bincell);

for ii = 1:n
    subplot(2,2,ii)
    plot(subgraph(G, bincell{ii}), 'NodeLabel', bincell{ii});
end

Идентифицируйте вершины сокращения в графике и затем подсветите те вершины в графике графика.

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

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

[edgebins,iC] = biconncomp(G)
edgebins = 1×13

     4     4     4     4     4     3     3     3     3     2     1     1     1

iC = 1×3

     4     6     7

Узлы 4, 6, и 7 являются вершинами сокращения графика G. Используйте highlight увеличить вершины сокращения, на которые ссылаются в iC.

highlight(p, iC)

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

свернуть все

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

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

Тип выхода в виде одного из этих значений:

ОпцияВывод
'vector' (значение по умолчанию)bins числовой вектор, указывающий, какому двусвязному компоненту каждое ребро принадлежит.
'cell'bins массив ячеек и bins{j} содержит идентификаторы узла для всех узлов, которые принадлежат j компонента.

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

свернуть все

Двусвязные компоненты, возвращенные как векторный массив или массив ячеек. Числа интервала присваивают каждое ребро или узел в графике к двусвязному компоненту:

  • Если OutputForm isvector (значение по умолчанию), затем bins числовой вектор, указывающий, который соединил компонент (интервал), каждое ребро принадлежит.

  • Если OutputForm iscell, затем bins массив ячеек, с bins{j} содержа идентификаторы узла для всех узлов, которые принадлежат j компонента.

Индексы вершин сокращения, возвращенных как вектор из числовых идентификаторов узла.

Больше о

свернуть все

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

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

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

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

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

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

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

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

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

Введенный в R2017b