Main Content

conncomp

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

설명

예제

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)

Figure contains an axes object. The axes object contains an object of type graphplot.

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

Figure contains an axes object. The axes object contains an object of type graphplot.

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

Figure contains an axes object. The axes object contains an object of type graphplot.

각 성분의 크기를 가져오려면 약한 연결성분을 계산하고 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)

Figure contains an axes object. The axes object contains an object of type graphplot.

binsizes를 이와 유사하게 사용하는 예로는 크기를 기준으로 하여 성분을 골라내는 경우가 있습니다. 이 절차는 가장 큰 성분을 추출하는 것과 유사하지만, 이 경우에는 각 노드가 크기 요건을 충족하는 모든 성분에 속할 수 있습니다.

G에서 3개 미만의 노드를 갖는 모든 성분을 필터링합니다. idx는 각 노드가 3개 이상의 노드를 갖는 성분에 속하는지를 나타내는 논리형 인덱스입니다.

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

Figure contains an axes object. The axes object contains an object of type graphplot.

입력 인수

모두 축소

입력 그래프로, 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'이 쉼표로 구분되어 지정됩니다.

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

참고

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

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

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

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

출력 인수

모두 축소

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

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

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

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

세부 정보

모두 축소

약한 연결성분

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

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

강한 연결성분

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

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

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

확장 기능

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

버전 내역

R2015b에 개발됨

참고 항목

| |