conncomp

Компоненты связного графа

Описание

пример

bins = conncomp(G) возвращает связанные компоненты графика G как интервалы. Числа интервала указывают, какому компоненту каждый узел в графике принадлежит.

  • Если G неориентированный граф, затем два узла принадлежат тому же компоненту, если существует путь, соединяющий их.

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

пример

bins = conncomp(G,Name,Value) дополнительные опции использования заданы одним или несколькими Аргументами пары "имя-значение". Например, conncomp(G,'OutputForm','cell') возвращает массив ячеек, чтобы описать связанные компоненты.

[bins,binsizes] = conncomp(___) также возвращает размер связанных компонентов. binsizes(i) дает количество узлов в i компонента.

Примеры

свернуть все

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

G = graph([1 1 4],[2 3 5],[1 1 1],6);
plot(G)

bins = conncomp(G)
bins = 1×6

     1     1     1     2     2     3

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

s = [1 2 2 3 3 3 4 5 5 5 8 8];
t = [2 3 4 1 4 5 5 3 6 7 9 10];
G = digraph(s,t);
plot(G,'Layout','layered')

str_bins = conncomp(G)
str_bins = 1×10

     4     4     4     4     4     6     5     1     3     2

weak_bins = conncomp(G,'Type','weak')
weak_bins = 1×10

     1     1     1     1     1     1     1     2     2     2

Используйте второй выход conncomp извлечь самый большой компонент графика или удалить компоненты ниже определенного размера.

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

s = [1 2 2 3 3 3 4 5 5 5 8 8 9];
t = [2 3 4 1 4 5 5 3 6 7 9 10 10];
G = digraph(s,t,[],20);
plot(G,'Layout','layered')

Вычислите слабо связанные компоненты и задайте два выходных параметров к conncomp получить размер каждого компонента.

[bin,binsize] = conncomp(G,'Type','weak')
bin = 1×20

     1     1     1     1     1     1     1     2     2     2     3     4     5     6     7     8     9    10    11    12

binsize = 1×12

     7     3     1     1     1     1     1     1     1     1     1     1

Используйте binsize извлекать самый большой компонент из графика. idx логический индекс, указывающий, принадлежит ли каждый узел самому большому компоненту. subgraph функционируйте извлекает узлы, выбранные idx от G.

idx = binsize(bin) == max(binsize);
SG = subgraph(G, idx);
plot(SG)

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

Отфильтруйте любые компоненты в G это имеет меньше чем 3 узла. idx логический индекс, указывающий, принадлежит ли каждый узел компоненту с 3 или больше узлами.

idx = binsize(bin) >= 3;
SG = subgraph(G, idx);
plot(SG)

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

свернуть все

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

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

Пример: G = digraph([1 2],[2 3])

Аргументы в виде пар имя-значение

Задайте дополнительные разделенные запятой пары Name,Value аргументы. Name имя аргумента и Value соответствующее значение. Name должен появиться в кавычках. Вы можете задать несколько аргументов в виде пар имен и значений в любом порядке, например: Name1, Value1, ..., NameN, ValueN.

Пример: bins = conncomp(G,'OutputForm','cell')

Тип выхода в виде разделенной запятой пары, состоящей из 'OutputForm' и любой 'vector' или 'cell'.

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

Примечание

'Type' опция поддерживается только для ориентированных графов, созданных с помощью digraph.

Тип связанных компонентов в виде разделенной запятой пары, состоящей из 'Type' и любой 'strong' (значение по умолчанию) или 'weak'.

ОпцияРезультат
'strong' (значение по умолчанию)Два узла принадлежат тому же связанному компоненту, только если существует путь, соединяющий их в обоих направлениях.
'weak'Два узла принадлежат тому же связанному компоненту, если существует путь, соединяющий их, игнорируя направления ребра.

Пример: bins = conncomp(G,'Type','weak') вычисляет слабо связанные компоненты ориентированного графа G.

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

свернуть все

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

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

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

Размер каждого связанного компонента, возвращенного как вектор. binsizes(i) дает число элементов в i компонента. Длина binsizes равно количеству связанных компонентов, max(bins).

Больше о

свернуть все

Слабо соединенные компоненты

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

Концепции сильных и слабых компонентов применяются только к ориентированным графам, когда они эквивалентны для неориентированных графов.

Строго соединенные компоненты

Два узла принадлежат тому же строго связанному компоненту, если существуют пути, соединяющие их в обоих направлениях. Между двумя строго связанными компонентами могут быть ребра, но эти соединительные ребра никогда не являются частью цикла.

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

Концепции сильных и слабых компонентов применяются только к ориентированным графам, когда они эквивалентны для неориентированных графов.

Смотрите также

| |

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