Articulation Point (단절점)을 이용하여 Biconnected Component (이중 연결 요소) 을 어떻게 찾을 수 있을까? 먼저, Biconnected Component의 정의를 살펴보자 Definition of Biconnected Component G' of G : Graph G의 maximal Biconnected Subgraph 1) Maximal 해야하고 2) Biconnected여야 한다. Key Property : G의 Biconnected Component 는 G의 Edge들을 Partitioning할 수 있으며 각각의 Biconnected는 오직 한 의 Articulation Point 만을 공유한다. proof Contradiction. 만약 Graph G의 서로 다..

DFS Tree의 성질을 이용하여 Articulation Point를 찾기 DFS Tree의 성질과 Articulation Point(단절점)의 정의를 활용하여 Graph에서 Articulation Point(단절점)를 찾아보자. Definition of Articulation Point 단절점의 정의 : 어떤 Graph G에 속하는 vertex v에 대하여 vertex v와 vertex v와 incident한(edge의 구성요소로 v를 가지고 있는) edge를 G에서 제거했을 때, G가 disconnected 된다면 vertex v는 G의 Articulation Point가 된다, *Definition of Connected G : G에 속하는 임의의 vertex v, w에 대하여 v에서 w가 reac..