Articulation Point 또는 Cut Vertex는 제거했을 때 Connected Component 수가 증가하는 무방향 그래프의 정점입니다.
즉, 구조적인 Single Point of Failure입니다.
Bridge와의 차이
Code
Articulation Point = 핵심 Vertex
Bridge = 핵심 Edge핵심 값
DFS에서 다음을 사용합니다.
Code
disc[u]
low[u]disc는 최초 방문 시간입니다.
low는 DFS Subtree에서 Back Edge를 통해 도달 가능한 가장 이른 Ancestor의 discovery time입니다.
일반 정점 조건
v가 u의 DFS child일 때:
Code
low[v] >= disc[u]이면 u가 Articulation Point입니다.
Root 조건
DFS Root는 child가 두 개 이상일 때 Articulation Point입니다.
활용
- Critical Router
- Single Point of Failure
- Transportation Network
- Infrastructure Connectivity
- Biconnected Analysis
복잡도
Code
O(V + E)정리
Articulation Point는 한 정점의 장애가 그래프를 분리하는지를 찾는 핵심 개념이며 Tarjan DFS로 선형 시간에 찾을 수 있습니다.