Bridge 또는 Cut Edge는 제거했을 때 Connected Component 수가 증가하는 무방향 그래프의 간선입니다.
즉, Edge 수준의 Single Point of Failure입니다.
Articulation Point와의 차이
Code
Bridge = 핵심 Edge
Articulation Point = 핵심 Vertex핵심 아이디어
DFS에서:
Code
disc[u]
low[u]를 계산합니다.
DFS Tree Edge (u,v)에 대해:
Code
low[v] > disc[u]이면 (u,v)는 Bridge입니다.
Cycle과 Bridge
무방향 그래프에서 Cycle에 속한 Edge는 Bridge가 아닙니다.
대체 경로가 있기 때문입니다.
활용
- Network Link Reliability
- Data Center Redundancy
- Transportation Networks
- Telecom Links
- Infrastructure Analysis
2-edge-connected
Bridge가 없는 Connected Graph는 2-edge-connected입니다.
복잡도
Code
O(V + E)정리
Bridge Detection은 한 연결의 장애가 네트워크를 분리하는지 찾는 알고리즘이며 Tarjan DFS와 low-link로 선형 시간에 해결할 수 있습니다.