Main Content

biconncomp

그래프의 이중 연결성분(Biconnected Component)

설명

예제

bins = biconncomp(G)는 그래프 G이중 연결성분을 Bin으로 반환합니다. Bin 번호는 그래프에 포함된 각 간선이 속하는 이중 연결성분을 나타냅니다. G의 각 간선은 단일 이중 연결성분에 속하는 반면, G의 노드는 둘 이상의 이중 연결성분에 속할 수 있습니다. 그래프에서 어느 쪽의 노드를 제거해도 연결이 끊기지 않는 경우 두 노드가 동일한 이중 연결성분에 속해 있는 것입니다.

예제

bins = biconncomp(G,'OutputForm',form)form'cell'인 경우 셀형 배열로 출력값을 반환하며, bins{j}는 성분 j에 속하는 모든 노드의 노드 ID를 포함합니다. form의 디폴트 값은 'vector'입니다.

예제

[bins,iC] = biconncomp(___)는 단절점(Articulation Point)이라고도 하는 절단 정점 노드를 나타내는 노드 인덱스 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);

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

p.EdgeCData =  biconncomp(G);

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

이 예제에서는 그래프에서 이중 연결성분을 부분 그래프로 추출한 후 원본 그래프의 노드 인덱스를 사용하여 각 부분 그래프의 노드에 레이블을 지정하는 방법을 보여줍니다.

그래프를 생성하고 플로팅합니다.

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)

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

각 노드가 속하는 이중 연결성분을 기준으로 그래프 노드를 Bin으로 그룹화합니다. 그런 다음, 각 Bin을 순환하면서 각 이중 연결성분에 대한 부분 그래프를 추출합니다. 원래 노드 인덱스를 사용하여 각 부분 그래프의 노드에 레이블을 지정합니다.

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

Figure contains 4 axes objects. Axes object 1 contains an object of type graphplot. Axes object 2 contains an object of type graphplot. Axes object 3 contains an object of type graphplot. Axes object 4 contains an object of type graphplot.

그래프에서 절단 정점을 식별한 후 그래프 플롯에서 이러한 정점을 강조 표시합니다.

그래프를 생성하고 플로팅합니다. 각 그래프 간선이 속하는 이중 연결성분을 계산하고, 절단 정점을 식별하는 벡터를 반환하도록 두 번째 출력값을 지정합니다.

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

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

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

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

입력 인수

모두 축소

입력 그래프로, graph 객체로 지정됩니다. graph를 사용하면 무방향 graph 객체를 생성할 수 있습니다.

예: G = graph(1,2)

출력값 유형으로, 다음 값 중 하나로 지정됩니다.

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

출력 인수

모두 축소

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

  • OutputForm'vector'(디폴트 값)이면 bins는 각 간선이 속하는 연결성분(Bin)을 나타내는 숫자형 벡터입니다. 자가 루프인 간선은 어떠한 이중 연결성분에도 속하지 않으므로 Bin 0에 할당됩니다.

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

절단 정점의 인덱스로, 숫자형 노드 ID로 구성된 벡터로 반환됩니다.

세부 정보

모두 축소

이중 연결성분

그래프의 이중 연결성분은 최대로 이중 연결된 부분 그래프입니다. 그래프에 절단 정점이 없다면 그래프가 이중으로 연결된 것입니다.

그래프를 이중 연결성분으로 분해하면 그래프의 연결성을 측정하는 데 도움이 됩니다. 모든 연결 그래프를 이중 연결성분 트리, 이른바 블록-절단 트리(Block-Cut Tree)로 분해할 수 있습니다. 트리의 블록은 절단 정점인 공유 정점에서 연결됩니다.

아래 그림은 다음을 나타냅니다.

  • (a) 11개 노드를 가지는 무방향 그래프.

  • (b) 그래프의 이중 연결성분 5개(원본 그래프의 절단 정점이, 이 정점이 속한 각 성분에 대해 색으로 구분되어 있음).

  • (c) 그래프의 블록-절단 트리. 각 이중 연결성분에 대한 노드(큰 원)와 각 절단 정점에 대한 노드(여러 색으로 구분된 더 작은 원)가 포함됩니다. 블록-절단 트리에서 간선은 각 절단 정점을 이 정점이 속한 각 성분에 연결합니다.

An undirected graph, the biconnected components of the graph, and the block-cut tree of the graph

절단 정점

단절점(Articulation Point)이라고도 하는 절단 정점은 제거하면 연결성분의 개수가 늘어나는 그래프 노드입니다. 앞의 그림에서 절단 정점은 둘 이상의 색으로 표시된 노드 4, 6, 7입니다.

확장 기능

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

버전 내역

R2016b에 개발됨