바이콘넥트 성분

Biconnected component
An example graph with biconnected components marked
각 색상은 이콘넥트 성분에 해당한다.멀티 컬러 정점은 절단 정점이며, 따라서 복수의 이콘넥트 구성요소에 속한다.

그래프 이론에서, 바이콘넥트 성분(때로는 2-연결 성분으로 알려져 있다)은 최대 바이콘넥트 서브그래프다.연결된 모든 그래프는 그래프의 블록컷 트리라고 불리는 이콘넥트 구성요소의 트리로 분해된다.이 블록들은 절단 정점 또는 분리 정점 또는 연결점이라고 불리는 공유 정점에서 서로 연결되어 있다.특히 절단 정점은 제거가 연결된 구성 요소의 수를 증가시키는 모든 정점이다.

알고리즘

선형 시간 깊이 우선 검색

연결된 비방향 그래프에서 바이코넥트 구성요소를 계산하기 위한 고전적인 순차 알고리즘은 존 홉크로프트와 로버트 타르잔(1973) 때문이다.[1]이것은 선형 시간으로 실행되며, 깊이 우선 검색을 기반으로 한다.이 알고리즘은 알고리즘 도입(2판과 3판 모두)의 문제 22-2로도 윤곽이 잡힌다.

다음과 같은 정보를 유지하면서 깊이 우선 검색을 실행하자는 취지다.

  1. 깊이 첫 번째 검색 트리의 각 꼭지점 깊이(한 번 방문하면)
  2. 각 꼭지점 v에 대해 lowpoint라고 하는 깊이 우선 검색 트리에서 v의 모든 후손(v자체 포함)의 가장 낮은 이웃 깊이.

깊이 우선 검색 시 그 깊이를 유지하는 것이 표준이다.v의 저점은 v의 최소 깊이, v의 모든 이웃(깊이 우선 검색 트리에서 v의 부모 이외의)의 깊이, 깊이 우선 검색 트리에서 v의 모든 하위 항목(v가 깊이 우선 검색 스택에서 튀어나오기 직전)을 방문한 후 계산할 수 있다.

중요한 사실은 비루트 정점 v는 저점(y) ≥ 깊이(v)와 같은 v의 자식 y가 있는 경우에만 두 개의 이코넥트 구성 요소를 분리하는 절단 정점(또는 관절점)이라는 것이다.이 속성은 v의 모든 하위 항목에서 깊이 우선 검색이 반환된 후(즉, v가 깊이 우선 검색 스택에서 튀어나오기 직전에), 그리고 참일 경우 v가 그래프를 서로 다른 2차 연결 구성 요소로 분리하면 테스트할 수 있다.이는 그러한 모든 y(y를 포함하는 구성 요소에는 y의 하위 트리가 포함됨, + v) 중에서 하나의 바이콘 연결 구성 요소를 계산한 다음, 나무에서 y의 하위 트리를 지우는 것으로 나타낼 수 있다.

루트 꼭지점은 별도로 취급해야 한다: DFS 트리에 자녀가 둘 이상 있는 경우에만 절단 정점이다.따라서 루트(루트 포함)의 각 자식 하위 트리에서 하나의 구성요소를 간단하게 구축하면 된다.

가성음

GetArticulationPoints(i, d)     visited[i] := true     depth[i] := d     low[i] := d     childCount := 0     isArticulation := false for each ni in adj[i] do if not visited[ni] then             parent[ni] := i             GetArticulationPoints(ni, d + 1)             childCount := childCount + 1             if low[ni] ≥ depth[i] thenIsarticulation := true low[i] := Min(낮음[i], low[ni], ni]가 부모[i]가 아닌 경우 : : Min(낮음[i], 깊이[ni])가 (부모[i]가 null and IsArticulation) 또는 (부모[i] = null and childCount >가 1인 경우)을 표현점으로 출력한다.

자식과 부모라는 용어는 원래 그래프가 아닌 DFS 트리의 관계를 나타낸다.

절단 정점을 찾기 위한 타르잔 알고리즘의 데모.D는 깊이를, L은 저점을 나타낸다.


기타 알고리즘

위의 알고리즘에 대한 간단한 대안은 DFS-tree에 따라 특별한 귀 분해인 체인 분해법을 사용한다.[2]체인 분해는 이 통과 규칙에 의해 선형 시간으로 계산될 수 있다.C를 G의 연쇄분해가 되게 하라.그 다음 G가 최소 도 2를 가지고 있고 C가1 C에서 유일한 사이클인 경우에만 G가 2-Vertex로 연결된다.이것은 즉시 선형 시간 2-연결성 테스트를 제공하며, 다음과 같은 문구를 사용하여 선형 시간 내에 G의 모든 절단 정점을 나열하도록 확장할 수 있다: 연결된 그래프 G의 정점 v(최소도 2)는 V가 교량에 입사하거나 C - C에서1 주기의 첫 번째 정점일 경우에만 절단 정점이다.컷 정점 리스트는 G의 블록 컷 트리를 선형 시간으로 만드는 데 사용할 수 있다.

문제의 온라인 버전에서는 정점과 가장자리가 동적으로 추가되지만 제거되지는 않으며, 데이터 구조는 반드시 쌍커넥트 구성요소를 유지해야 한다.Jeffery Westbrook과 Robert Tarjan(1992)은 분리된 데이터 구조를 기반으로 이 문제에 대한 효율적인 데이터 구조를 개발했다.구체적으로는 O(m α(m, n) 총 시간에 n 꼭지 추가와 m 가장자리 추가를 처리하며, 여기서 α는 역아커만 함수다.이 시간이 최적의 시간이라는 것이 증명되었다.

Uzi Vishkin과 Robert Tarjan(1985)은 n + m 프로세서로 O(log n) 시간에 실행되는 CRCW PRAM에 병렬 알고리즘을 설계했다.

관련 구조물

등가관계

임의의 비방향 그래프의 가장자리에 이진 관계를 정의할 수 있는데, 두 에지 e와 f는 e = f 또는 그래프가 e와 f를 모두 통과하는 단순한 주기를 포함하는 경우에만 관련이 있다.모든 가장자리는 그 자체와 관련되며, 가장자리 e는 f가 e와 동일한 방식으로 관련되는 경우에만 다른 가장자리 f와 관련된다.덜 명백하게, 이것은 전이적 관계다: 만약 에지 e와 f를 포함하는 단순한 사이클과 에지 f와 g를 포함하는 또 다른 단순한 사이클이 존재한다면, 이 두 사이클을 결합하여 e와 g를 통한 단순한 사이클을 찾을 수 있다.따라서 이는 동등성 관계이며, 동일한 동등성 등급에 속하는 경우에만 두 가장자리가 서로 관련되는 속성과 함께 가장자리를 동등성 등급으로 분할하는 데 사용할 수 있다.각 동등성 등급의 가장자리에 의해 형성되는 하위 그래프는 주어진 그래프의 이코넥트 성분이다.따라서, 두 개의 결합 구성요소는 그래프의 가장자리를 분할하지만, 서로 정점을 공유할 수 있다.[5]

블록 그래프

주어진 그래프 G의 블럭 그래프는 블럭의 교차 그래프다.따라서 G의 각 블록에 대해 하나의 꼭지점이 있으며, 해당하는 두 블록이 정점을 공유할 때마다 두 꼭지점 사이의 가장자리가 있다.그래프 H는 H의 모든 블록이 완전한 서브그래프일 때 다른 그래프 G의 블록 그래프다.이 속성이 있는 그래프 H를 블럭 그래프라고 한다.[6]

블록컷트리

그래프 G의 절단점, 절단 정점 또는 관절점은 둘 이상의 블록이 공유하는 정점이다.연결된 그래프의 블록 구조와 절단점은 블록 컷 트리 또는 BC 트리라고 불리는 트리로 설명할 수 있다.이 트리는 주어진 그래프의 각 블록과 각 관절점에 대해 꼭지점이 있다.블록의 각 쌍에 대한 블록 컷 트리와 그 블록에 속하는 굴절점이 있다.[7]

그래프, 그리고 블럭컷 트리.
블럭은 b1=[1,2], b3=[2,3,4], b2=[2,5,6,7], b4=[7,8,8,8,8,8,9,10,11],b5=[8,12,13,14,15],b6=[10,16],b7=[10,17,18];
컷포인트는 c1=2, c2=7, c3=8, c4=10이다.

참고 항목

메모들

  1. ^ Hopcroft, J.; Tarjan, R. (1973). "Algorithm 447: efficient algorithms for graph manipulation". Communications of the ACM. 16 (6): 372–378. doi:10.1145/362248.362272.
  2. ^ Schmidt, Jens M. (2013), "A Simple Test on 2-Vertex- and 2-Edge-Connectivity", Information Processing Letters, 113 (7): 241–244, arXiv:1209.0700, doi:10.1016/j.ipl.2013.01.016.
  3. ^ Westbrook, J.; Tarjan, R. E. (1992). "Maintaining bridge-connected and biconnected components on-line". Algorithmica. 7 (1–6): 433–464. doi:10.1007/BF01758773.
  4. ^ Tarjan, R.; Vishkin, U. (1985). "An Efficient Parallel Biconnectivity Algorithm". SIAM J. Comput. 14 (4): 862–874. CiteSeerX 10.1.1.465.8898. doi:10.1137/0214061.
  5. ^ 타르잔&비슈킨(1985)은 이 동등성 관계의 정의를 하라리(1969년)와 동일하다고 믿지만, 하라리는 명시적인 용어로 묘사하지 않는 것 같다.
  6. ^ Harary, Frank (1969), Graph Theory, Addison-Wesley, p. 29.
  7. ^ 하라리(1969), 페이지 36.

참조

외부 링크