bctree
블록-절단 트리(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')
그래프를 생성하고 플로팅합니다.
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: [6×1 table]
Nodes: [7×3 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입니다.
입력 인수
출력 인수
세부 정보
그래프의 이중 연결성분은 최대로 이중 연결된 부분 그래프입니다. 그래프에 절단 정점이 없다면 그래프가 이중으로 연결된 것입니다.
그래프를 이중 연결성분으로 분해하면 그래프의 연결성을 측정하는 데 도움이 됩니다. 모든 연결 그래프를 이중 연결성분 트리, 이른바 블록-절단 트리(Block-Cut Tree)로 분해할 수 있습니다. 트리의 블록은 절단 정점인 공유 정점에서 연결됩니다.
아래 그림은 다음을 나타냅니다.
(a) 11개 노드를 가지는 무방향 그래프.
(b) 그래프의 이중 연결성분 5개(원본 그래프의 절단 정점이, 이 정점이 속한 각 성분에 대해 색으로 구분되어 있음).
(c) 그래프의 블록-절단 트리. 각 이중 연결성분에 대한 노드(큰 원)와 각 절단 정점에 대한 노드(여러 색으로 구분된 더 작은 원)가 포함됩니다. 블록-절단 트리에서 간선은 각 절단 정점을 이 정점이 속한 각 성분에 연결합니다.
확장 기능
버전 내역
R2016b에 개발됨
