Strongly Connected Component (4) 썸네일형 리스트형 133. 2-SAT 충족 가능성 문제(SAT, Satisfiability Problem)는 Boolean 변수들(True 또는 False 중 한 가지 값을 가질 수 있음)로 이루어진 식의 값이 True가 되게 하는 변수들의 값 조합이 존재하는지를 알아내는 문제이다. 이러한 식은 불 연산식(Boolean Expression)이라고 부르며 다음과 같은 두 가지의 형태로 나타낼 수 있다. 식에서 $\neg$, $\wedge$, $\vee$ 기호는 각각 NOT, AND, OR 연산자와 같은 의미를 가지며 $\neg$ 연산자의 우선순위가 가장 높다.CNF(Conjunctive Normal Form): $f = (x_1 \vee x_2) \wedge (\neg x_3 \vee x_1 \vee x_4) \wedge (\neg x_2 \.. 132. Tarjan's Algorithm 타잔 알고리즘(Tarjan's Algorithm)은 그래프의 SCC를 전부 구하는 또 다른 알고리즘으로, 다음과 같은 방법으로 작동한다. 1. 아직 방문하지 않은 정점 하나를 골라 그 정점에서 DFS를 실행한다. 2. 새로운 정점을 방문할 때마다 그 정점의 방문 순서를 저장한다. 이를 우선순위(값이 작을수록 높음)로 간주하고, 정점마다 그 정점에서 도달할 수 있는 정점들의 우선순위 값 중 가장 높은 것을 저장한다. 이때 이미 SCC로 묶인 정점의 우선순위는 무시한다. 3. 어떤 정점의 DFS가 종료될 때, 그 정점에서 도달할 수 있는 정점들 중 우선순위가 가장 높은 정점이 자신일 경우 스택에 쌓인 정점을 자신이 나올 때까지 전부 뽑고, 그 정점들을 하나의 SCC로 묶는다. 4. 모든.. 131. Kosaraju's Algorithm 먼저 임의의 정점 $v$가 주어졌을 때 $v$를 포함하는 SCC 하나를 구하는 방법을 살펴본다.$v$에서 이동할 수 있는 정점들과 $v$로 이동할 수 있는 정점들의 교집합을 구하면 그 집합에 속한 정점들이 한 SCC로 묶이게 된다. $v$에서 이동할 수 있는 정점들은 DFS로 쉽게 구할 수 있고, $v$로 이동할 수 있는 정점들은 간선들을 전부 뒤집은 다음 DFS를 실행하면 구할 수 있다. 두 번의 DFS에서 모두 방문한 정점들은 $v$와 같은 SCC에 속한다. 따라서 다음과 같은 방법으로 그래프의 SCC를 전부 구할 수 있다. (그래프에 존재하는 정점의 수가 $n$이라고 가정한다.) 1. 아직 SCC로 묶이지 않은 정점 중 하나를 선택해서 그 정점에서 DFS를 실행한다. 2. 그래프의 간선을.. 130. Strongly Connected Component 유향 그래프에 존재하는 어떤 컴포넌트는 다음과 같은 조건을 만족할 경우 강결합 컴포넌트(Strongly Connected Component, SCC)라고 부른다. 컴포넌트에 속하는 임의의 두 정점 $u$와 $v$에 대해 $u$에서 $v$로 가는 경로와 $v$에서 $u$로 가는 경로가 모두 존재한다. 컴포넌트에 속하는 임의의 정점 $u$와 컴포넌트에 속하지 않는 임의의 정점 $v$에 대해 $u$에서 $v$로 가는 경로가 존재하지 않거나, $v$에서 $u$로 가는 경로가 존재하지 않는다. 그래프를 강결합 컴포넌트끼리 분리하면 같은 컴포넌트에 속한 정점들 사이에는 모두 경로가 존재하고, 다른 컴포넌트에 속한 정점들 사이에는 그렇지 않다. 따라서 같은 강결합 컴포넌트에 속한 정점들끼리 묶어서 새로운 그래프를 만.. 이전 1 다음
