Articulation Points (단절점) 에 관련된 괜찮은 자료가 있어서 올려본다..

connected 된 graph G = (V, E) 에서 임의의 vertex v 를 없앴을 때,
임의의 두 vertex (i, j) 사이의 path 가 없는 경우 v 가 articulation point 가 된다..

각 vertex 가 articulation point 인지 아닌지 구하는 방법은..
DFS 를 통해서 DAG 를 만들었을 때,
자신의 자식 vertex 중에서 자신의 조상 vertex 로 가는 back edge 가 있으면
articulation point 가 아닌것으로 판단한다..
이 방법은 DAG 에서 root 에만 예외가 되는데.. (왜냐하면 root 위에 조상이 없으므로.. -_-)
root 는 자신의 child 가 1개인지 아닌지만 보면 된다..
만약에 child 가 2개 이상이라면 root 를 없앴을 때 graph 가 둘 이상으로 쪼개지기 때문이다..


관련자료:

구현한 코드를 테스트해보고자 한다면..
UVa 315 - Network



추가로 생각해볼 문제..
1) directed graph 일 때는 articulation point 를 어떻게 구할것인가..?
2) 위 방법을 응용하여 bridge 를 구할 수 있을까..? (UVa 796 - Critical Link)



'Problem Solving > Algorithm notes' 카테고리의 다른 글

The Tower of Hanoi  (0) 2011.08.28
Gaussian Prime  (0) 2011.04.03
Floating point number 연산시 Epsilon을 더하는(또는 빼는) 이유..  (2) 2011.03.02
Linear Diophantine Equation  (0) 2011.01.25
점과 선분과의 거리  (2) 2011.01.22
Articulation Points  (0) 2010.11.21
Konig's Theorem  (0) 2010.08.01
Modular Multiplicative Inverse  (0) 2010.06.13
Primality Testing (Miller-Rabin)  (0) 2010.03.23
Modular Exponentiation (Big Mod)  (2) 2010.02.19
KMP (Knuth-Morris-Pratt) Algorithm  (0) 2009.11.15

Leave a Comment


to Top