단절점 썸네일형 리스트형 단절점(Articulation Point)와 단절선(Bridge) 하나의 컴포넌트로 이루어진 무방향 그래프에서 한 정점을 제거했을 때 그래프가 두개 이상의 컴포넌트로 나누어지는 정점을 단절점이라고 합니다.다음과 같은 무방향 그래프가 있다고 해봅시다. 여기서 빨간색 테두리로 이루어진 정점들중 하나를 지울 경우 컴포넌트가 2개로 나누어지게 됩니다. 이러한 성질을 가지는 정점들을 단절점이라고 부릅니다. 그러면 우리는 단절점을 어떤 방법으로 찾을 수 있을까요? 우선은 단절점을 찾기 위해서 우선 단절점이 가지는 특징을 알아야 됩니다. 아까의 그래프에서 단절점인 빨간정점에 연결된 정점들을 초록정점으로 색칠해봤습니다. 우리는 어떤 정점 A에 연결된 모든 정점들 중 두 정점들 간에 정점 A를 거치지않고 갈 수 있는 우회경로가 존재하지 않는 경우가 존재한다면 정점 A는 단절점으로 판단.. 더보기 이전 1 다음
