bctree

블록-절단 트리(Block-Cut Tree) 그래프

구문

tree = bctree(G)

[tree,ind] = bctree(G)

설명

tree = bctree(G)는 그래프 G의 블록-절단 트리를 반환하며, tree의 각 노드는 G의 이중 연결성분이나 절단 정점을 나타냅니다. 절단 정점을 나타내는 노드는 이 절단 정점을 포함하는 이중 연결성분을 나타내는 모든 노드에 연결됩니다.

[tree,ind] = bctree(G)는 G의 노드를 tree의 노드에 매핑하는 숫자형 노드 인덱스로 구성된 벡터도 반환합니다.

예제

그래프의 블록-절단 트리(Block-Cut Tree) 계산하기

그래프의 블록-절단 트리를 계산하고, 결과로 생성되는 노드 속성을 확인한 후 그래프 플롯에서 절단 정점을 강조 표시합니다.

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

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

그래프의 블록-절단 트리를 계산하고 노드 속성을 확인합니다.

tree = bctree(G);
tree.Nodes

ans=7×3 table
    IsComponent    ComponentIndex    CutVertexIndex
    ___________    ______________    ______________

       true              1                 0       
       true              2                 0       
       true              3                 0       
       true              4                 0       
       false             0                 4       
       false             0                 6       
       false             0                 7       

절단 정점을 나타내는 노드에 대해 빨간색 다이아몬드 마커를 사용하여 블록-절단 트리를 플로팅합니다. 원형 노드는 원본 그래프의 이중 연결성분을 나타냅니다.

p2 = plot(tree,'MarkerSize',9);
highlight(p2,5:7,'Marker','d','NodeColor','r')

블록-절단 트리(Block-Cut Tree)의 노드 인덱스 반환하기

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

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

그래프의 블록-절단 트리 tr을 계산하고, 노드 인덱스를 반환하도록 두 번째 출력값 ix를 지정합니다.

[tr,ix] = bctree(G)

tr = 
  graph with properties:

    Edges: [6x1 table]
    Nodes: [7x3 table]

ix = 1×10

     4     4     4     5     3     6     7     1     1     2

각 인덱스 ix(j)는 블록-절단 트리에서 입력 그래프의 노드 j를 나타내는 노드를 가리킵니다. 예를 들어, tr의 노드 4는 G에서 노드 1, 2, 3을 포함하는 성분을 나타냅니다. 따라서 ix에서 처음 3개 항목은 모두 4입니다.

입력 인수

G — 입력 그래프

graph 객체

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

예: G = graph(1,2)

출력 인수

tree — 블록-절단 트리(Block-Cut Tree) 그래프

graph 객체

블록-절단 트리 그래프로, graph 객체로 반환됩니다. tree는 G의 각 절단 정점에 대한 노드와 G의 각 이중 연결성분에 대한 노드를 포함합니다. 노드 테이블 tree.Nodes는 각 노드가 나타내는 항목을 설명하는 추가 노드 특성을 포함합니다.

• tree.Nodes.IsComponent(i) — 노드 i가 이중 연결성분을 나타내는 경우 값은 논리값 1(true)입니다. 그렇지 않을 경우, 값은 논리값 0(false)입니다.

• tree.Nodes.ComponentIndex(i) — 노드 i가 나타내는 성분을 가리키는 인덱스입니다. 노드 i가 절단 정점을 나타내는 경우 값은 0입니다.

• tree.Nodes.CutVertexIndex(i) — 노드 i가 나타내는 절단 정점을 가리키는 인덱스입니다. 노드 i가 이중 연결성분을 나타내는 경우 값은 0입니다.

ind — 노드 인덱스

벡터

노드 인덱스로, 숫자형 벡터로 반환됩니다. ind(i)는 출력 그래프 tree에서 입력 그래프 G의 노드 i를 나타내는 노드입니다.

• 노드 i가 그래프 G의 절단 정점이면 ind(i)는 tree에서 연결된 노드입니다.

• 노드 i가 절단 정점이 아니지만 그래프 G의 이중 연결성분 중 하나에 속하면 ind(i)는 tree에서 해당 이중 연결성분을 나타내는 노드입니다.

• 노드 i가 그래프 G에서 고립된(Isolated) 노드이면 ind(i)는 0입니다.

세부 정보

이중 연결성분

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

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

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

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

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

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

절단 정점

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

확장 기능

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

버전 내역

R2016b에 개발됨

참고 항목

biconncomp | condensation

도움말 항목

• 유방향 그래프와 무방향 그래프
• 너비 우선 탐색(Breadth-First Search)과 깊이 우선 탐색(Depth-First Search) 시각화하기