본문 바로가기

분류 전체보기

 (134)
139. Ford-Fulkerson Algorithm 포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm)은 일반적인 방향 그래프에서 최대 유량을 구하는 가장 간단한 알고리즘이다. 최대 유량은 일반적으로 소스에서 간선들을 따라서 싱크로 흘려보낼 수 있는 유량의 최댓값을 의미한다. 이 알고리즘은 다음과 같은 방법으로 작동한다. 1. 모든 간선의 유량을 $0$으로 초기화한다. 2. 소스에서 싱크로 데이터를 보낼 수 있는 경로를 찾는다. 이 경로를 증가 경로(Augmenting Path)라고 한다. 3. 증가 경로 중 더 보낼 수 있는 데이터의 양이 가장 작은 간선을 찾는다. 이 간선에 더 보낼 수 있는 데이터의 양을 $w$라고 하자. 4. 찾은 증가 경로를 통해 $w$의 데이터를 보낸다. 증가 경로에 포함된 모든 간선의 유량이 $w$만큼 증가하고..
138. Network Flow 네트워크 플로우(Network Flow)는 그래프 상의 두 정점 사이에 데이터를 얼마나 많이 흘려보낼 수 있는지를 구하는 분야이다. 일반적으로 네트워크를 생략하고 그냥 플로우라고 부르는 경우가 많다. 이제부터 앞에서 간단하게 소개하고 넘어갔던 간선의 용량이 중요하게 다뤄진다. 플로우에서 나오는 용어들의 정의와 특징은 다음과 같다. 정점 $u$에서 정점 $v$로 가는 방향 간선이 존재하고 이 간선의 용량이 $w$일 때, 최대 $w$만큼의 데이터가 이 간선을 따라 정점 $u$에서 정점 $v$로 이동할 수 있다. 정점 $u$에서 정점 $v$로 가는 간선을 통해 이동하는 데이터의 양이 $k$일 때, $k$를 이 간선의 유량(Flow)이라고 한다. 간선의 유량은 간선의 용량을 넘을 수 없다. 데이터를 처음으로 흘..
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. 모든 정점이 SCC로 묶일..
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$로 가는 경로가 존재하지 않는다. 그래프를 강결합 컴포넌트끼리 분리하면 같은 컴포넌트에 속한 정점들 사이에는 모두 경로가 존재하고, 다른 컴포넌트에 속한 정점들 사이에는 그렇지 않다. 따라서 같은 강결합 컴포넌트에 속한 정점들끼리 묶어서 새로운 그래프를 만..
128. Borůvka's Algorithm 보르부카 알고리즘(Borůka's Algorithm) 또는 솔린 알고리즘(Sollin's Algorithm)은 무향 그래프의 최소 스패닝 트리를 구하는 세 번째 알고리즘이며 다음과 같이 작동한다. 1. 각각의 컴포넌트에 연결된 간선들 중 가중치가 가장 작은 간선을 하나씩 선택한다. 2. 간선을 차례로 최소 스패닝 트리에 추가하는데, 간선이 연결하는 두 정점이 이미 같은 컴포넌트에 존재한다면 추가하지 않는다. 3. 컴포넌트가 하나로 줄어들 때까지 1번과 2번 과정을 반복한다. 이번에도 설명이 짧게 끝났다. 다시 예시를 가지고 살펴보자. 처음에는 정점들이 모두 다른 컴포넌트에 존재하므로, 각 정점과 연결된 간선들 중 가중치가 가장 작은 것 하나를 모두 고른다. $\text{A}: \text{D}(2)\\ \..
127. Prim's Algorithm 프림 알고리즘(Prim's Algorithm)은 무향 그래프의 최소 스패닝 트리를 구하는 두 번째 알고리즘으로, 다음과 같은 방법으로 작동한다. 1. 그래프에서 정점 하나를 임의로 골라서 $v$라고 한다. 2. 연결하는 한쪽 정점이 $v$와 연결된 정점들의 집합에 포함되고 다른 정점은 집합에 포함되지 않는 간선들 중 가중치가 가장 작은 간선 하나를 선택하고 최소 스패닝 트리에 추가한다. 3. 모든 정점이 $v$와 연결될 때까지 2번 과정을 반복한다. 이것도 설명이 짧아서 예시를 같이 살펴보면 편할 것이다. 앞에서 나온 그래프에서 정점 $\text{H}$가 $v$로 선택되었다면 다음과 같이 스패닝 트리가 만들어지게 된다. 먼저 정점 $\text{H}$와 연결된 간선 중 가중치가 가장 작은 간선이 최소 스패..

티스토리툴바