bctree
블록-절단 트리(Block-Cut 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입니다.
입력 인수
출력 인수
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에 개발됨
MATLAB 명령
다음 MATLAB 명령에 해당하는 링크를 클릭했습니다.
명령을 실행하려면 MATLAB 명령 창에 입력하십시오. 웹 브라우저는 MATLAB 명령을 지원하지 않습니다.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)