biconncomp
그래프의 이중 연결성분(Biconnected Component)
설명
예제
그래프를 생성하고 플로팅합니다. 각 간선이 속한 이중 연결성분을 바탕으로 간선을 색으로 표시합니다.
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);
p.EdgeCData = biconncomp(G);
이 예제에서는 그래프에서 이중 연결성분을 부분 그래프로 추출한 후 원본 그래프의 노드 인덱스를 사용하여 각 부분 그래프의 노드에 레이블을 지정하는 방법을 보여줍니다.
그래프를 생성하고 플로팅합니다.
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)
각 노드가 속하는 이중 연결성분을 기준으로 그래프 노드를 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
그래프에서 절단 정점을 식별한 후 그래프 플롯에서 이러한 정점을 강조 표시합니다.
그래프를 생성하고 플로팅합니다. 각 그래프 간선이 속하는 이중 연결성분을 계산하고, 절단 정점을 식별하는 벡터를 반환하도록 두 번째 출력값을 지정합니다.
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);
[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)
입력 인수
출력 인수
세부 정보
그래프의 이중 연결성분은 최대로 이중 연결된 부분 그래프입니다. 그래프에 절단 정점이 없다면 그래프가 이중으로 연결된 것입니다.
그래프를 이중 연결성분으로 분해하면 그래프의 연결성을 측정하는 데 도움이 됩니다. 모든 연결 그래프를 이중 연결성분 트리, 이른바 블록-절단 트리(Block-Cut Tree)로 분해할 수 있습니다. 트리의 블록은 절단 정점인 공유 정점에서 연결됩니다.
아래 그림은 다음을 나타냅니다.
(a) 11개 노드를 가지는 무방향 그래프.
(b) 그래프의 이중 연결성분 5개(원본 그래프의 절단 정점이, 이 정점이 속한 각 성분에 대해 색으로 구분되어 있음).
(c) 그래프의 블록-절단 트리. 각 이중 연결성분에 대한 노드(큰 원)와 각 절단 정점에 대한 노드(여러 색으로 구분된 더 작은 원)가 포함됩니다. 블록-절단 트리에서 간선은 각 절단 정점을 이 정점이 속한 각 성분에 연결합니다.
확장 기능
버전 내역
R2016b에 개발됨
