conncomp

그래프의 연결성분(Connected Component)

구문

bins = conncomp(G)

bins = conncomp(G,Name,Value)

[bins,binsizes] = conncomp(___)

설명

bins = conncomp(G)는 그래프 G의 연결성분을 bins로 반환합니다. Bin 번호는 그래프에 포함된 각 노드가 속하는 성분을 나타냅니다.

• G가 무방향 그래프인 경우 두 노드를 연결하는 경로가 있으면 이 두 노드는 동일한 성분에 속합니다.

• G가 유방향 그래프인 경우 두 노드를 양방향으로 연결하는 경로가 있으면 이 두 노드는 동일한 강한 성분에 속합니다.

bins = conncomp(G,Name,Value)는 하나 이상의 이름-값 쌍의 인수로 지정된 추가 옵션을 사용합니다. 예를 들어, conncomp(G,'OutputForm','cell')은 연결성분을 설명하는 셀형 배열을 반환합니다.

[bins,binsizes] = conncomp(___)는 연결성분의 크기도 반환합니다. binsizes(i)는 성분 i의 노드 개수를 지정합니다.

예제

그래프의 성분 구하기

3개의 연결성분을 갖는 무방향 그래프를 생성하고 플로팅합니다. 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 객체 | digraph 객체

입력 그래프로, graph 객체 또는 digraph 객체로 지정됩니다. 무방향 그래프를 생성하려면 graph를 사용하고 유방향 그래프를 생성하려면 digraph를 사용하십시오.

예: G = graph(1,2)

예: G = digraph([1 2],[2 3])

이름-값 인수

선택적 인수 쌍을 Name1=Value1,...,NameN=ValueN으로 지정합니다. 여기서 Name은 인수 이름이고 Value는 대응값입니다. 이름-값 인수는 다른 인수 뒤에 와야 하지만, 인수 쌍의 순서는 상관없습니다.

R2021a 이전 릴리스에서는 쉼표를 사용하여 각 이름과 값을 구분하고 Name을 따옴표로 묶으십시오.

예: bins = conncomp(G,'OutputForm','cell')

OutputForm — 출력값 유형

'vector' (디폴트 값) | 'cell'

출력값 유형으로, 'OutputForm'과 함께 'vector'나 'cell'이 쉼표로 구분되어 지정됩니다.

옵션	출력값
'vector'(디폴트 값)	bins는 각각의 노드가 속하는 연결성분을 나타내는 숫자형 벡터입니다.
'cell'	bins는 셀형 배열이고, bins{j}는 성분 j에 속하는 모든 노드의 노드 ID를 포함합니다.

Type — 연결성분 유형

'strong' (디폴트 값) | 'weak'

참고

'Type' 옵션은 digraph를 사용하여 생성된 유방향 그래프에 대해서만 지원됩니다.

연결성분 유형으로, 'Type'과 함께 'strong'(디폴트 값)이나 'weak'가 쉼표로 구분되어 지정됩니다.

옵션	결과
'strong'(디폴트 값)	두 노드를 양방향으로 연결하는 경로가 있는 경우에만 이 두 노드가 동일한 연결성분에 속합니다.
'weak'	간선 방향을 무시하고 두 노드를 연결하는 경로가 있는 경우 이 두 노드는 동일한 연결성분에 속합니다.

예: bins = conncomp(G,'Type','weak')는 유방향 그래프 G의 약한 연결성분을 찾습니다.

출력 인수

bins — 연결성분

벡터 | 셀형 배열

연결성분으로, 벡터 또는 셀형 배열로 반환됩니다. 그래프에 포함된 노드의 연결성분에 따라 Bin 번호가 각 노드에 할당됩니다.

• OutputForm이 'vector'(디폴트 값)이면 bins는 각 노드가 속하는 연결성분(Bin)을 나타내는 숫자형 벡터입니다.

• OutputForm이 'cell'이면 bins는 셀형 배열이고, bins{j}는 성분 j에 속하는 모든 노드의 노드 ID를 포함합니다.

binsizes — 각 연결성분의 크기

벡터

각 연결성분의 크기로, 벡터로 반환됩니다. binsizes(i)는 성분 i의 요소 개수를 반환합니다. binsizes의 길이는 연결성분의 개수 max(bins)와 같습니다.

세부 정보

약한 연결성분

간선 방향을 무시하고 두 노드를 연결하는 경로가 있는 경우 이 두 노드는 동일한 약한 연결성분에 속합니다. 두 개의 약한 연결성분 사이에는 간선이 없습니다.

강한 성분과 약한 성분이라는 개념은 무방향 그래프에서는 차이가 없으므로 유방향 그래프에만 적용됩니다.

강한 연결성분

두 노드를 양방향으로 연결하는 경로가 있는 경우 이 두 노드는 동일한 강한 연결성분에 속합니다. 2개의 강한 연결성분 사이에는 간선이 있을 수 있지만, 이러한 연결 간선은 절대로 순환에 포함될 수 없습니다.

강한 연결성분의 Bin 번호의 경우, Bin 번호가 더 작은 성분에서 Bin 번호가 더 큰 성분으로 두 성분 점을 연결하는 간선이 있을 수 있기 때문입니다.

강한 성분과 약한 성분이라는 개념은 무방향 그래프에서는 차이가 없으므로 유방향 그래프에만 적용됩니다.

확장 기능

C/C++ 코드 생성

MATLAB® Coder™를 사용하여 C 코드나 C++ 코드를 생성할 수 있습니다.

사용법 관련 참고 및 제한 사항:

• 셀형 배열 출력값을 지정하는 이름-값 인수 'OutputForm','cell'은 지원되지 않습니다.

스레드 기반 환경
MATLAB®의 backgroundPool을 사용해 백그라운드에서 코드를 실행하거나 Parallel Computing Toolbox™의 ThreadPool을 사용해 코드 실행 속도를 높일 수 있습니다.

버전 내역

R2015b에 개발됨

참고 항목

graph | digraph | subgraph