Undirected Graph에서는 Connected Component를 구하려면 아무 Vertex나 잡고 DFS를 수행한 결과 생성되는 DFS Tree 가 Connected Component 였다. (Definition of Connected Component of Graph G : G의 maximal 한 connected subgraph) Directed Graph에서는 Connected를 Strongly Connected로 정의하는 것이 일반적이다. 그럼 Strongly Connected란 무엇일까? Definition of Strongly Connected in Directed Graph Directed Graph G에서 G에 속한 서로 다른 두 vertex v, u에 대하여 path v to u..

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..