BCC

BCC

• Biconnected Component : Connected component + Maximal = 연결된 노드에서 노드 집합을 늘릴 수 없을 때까지 늘린것
• Parts of Graph separated by Cut Vertices 
• Two Nodes in a BCC has two completely different Paths connecting them : edge도 node도 겹치지 않음
• Meaning of "Separated" can be confusing
• Cut vertex와 반대의 개념이라고 생각할 수 있음

connected component들은 노드들은 파티션으로 나눔

biconected component는 cut vertex로 나뉘며, 이 cut vertex는 중복되어 들어갈 수 있음

 

여전히 Cut Vertex를 따지면 찾을 수 있다

 

Detecting BCC

• Find Cut Vertices : Cut vertex를 찾으면 가지 않는다
• Does NOT Work : Do DFS, Stop at Cut verteices
• In Cut Vertex Algorithm, each Subtree can be marked as BCC

만약, t가 cut vertex라면, 

sub tree중 t까지 밖에 올라오지 못하는 것이다. 

즉, 이 sub tree를 BCC로 생각하면 된다 (그 아래 BCC가 있다고 하면 이미 올라오면서 끊으면 된다)

t까지 오면 BCC에 t가 속하고 오지 않으면 BCC에 속하지 않는다

 

DFS를 돌리면 이렇게 된다

중간 별들 끼리도 BCC를 이루며, 현재 cut vertex를 기준으로 BCC이다