conncomp

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

Синтаксис

bins = conncomp(G)
bins = conncomp(G,Name,Value)
[bins,binsizes] = 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)

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

свернуть все

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

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

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

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

Укажите необязательные аргументы в виде пар ""имя, значение"", разделенных запятыми. Имя (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 является 'vector' (значение по умолчанию), то bins является числовым вектором, указывающим, который соединил компонент (интервал), каждый узел принадлежит.

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

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

Больше о

свернуть все

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

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

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

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

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

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

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

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

| |

Введенный в R2015b

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