반응형
1. 단절선(Articulation Bridge)이란?
단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말합니다.
2. 단절선(Articulation Bridge)동작 원리?
단절선(Articulation Bridge)의 동작 원리는 단절점(Articulation Point)의 동작 원리와 비슷합니다.
https://rudalsd.tistory.com/113
[ 알고리즘 ] 단절점(Articulation Point)
1. 단절점(Articulation Point)이란? 단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 정
rudalsd.tistory.com
단절점(Articulation Point)과의 차이점은 루트노드가 사라진 것과 부모 노드를 제외한 나머지 노드들이 우회 간선을 이용해서도 현재 노드에 도착하면 안되므로 등호가 빠진 것입니다.
반응형
'알고리즘' 카테고리의 다른 글
| [ 알고리즘 ] 이분 매칭(Bipartite Matching) (0) | 2023.05.24 |
|---|---|
| [ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence) (0) | 2022.10.24 |
| [ 알고리즘 ] 단절점(Articulation Point) (0) | 2022.08.26 |
| [ 알고리즘 ] 강한 연결 요소 추출 알고리즘(Strongly Connected Component) (0) | 2022.07.23 |
| [ 알고리즘 ] 위상 정렬 알고리즘(Topological Sort Algorithm) (0) | 2022.07.19 |