12.1 강결합성

참조

도서

• 안티 라크소넨, 『알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드』, 인사이트, 2022, p.237

영상

그래프의 강결합성

방향 그래프의 모든 노드에서 다른 모든 노드로 가는 경로가 있는 경우, 이 그래프를 강결합 그래프(strongly connected graph) 라고 한다. 예를 들어 그림 1의 왼쪽 그래프는 강결합 그래프이고 오른쪽 그래프는 강결합 그래프가 아니다. 오른쪽 그래프가 아닌 이유는 한 노드에서 다른 노드로 가는 경로가 없는 경우가 있기 때문인데, 예를 들면 2번 노드에서 1번 노드로 가는 경로가 없다.

• 그림 1. 왼쪽 그래프는 강결합 그래프이고 오른쪽 그래프는 강결합 그래프가 아니다.
  • 

모든 방향 그래프는 강결합 컴포넌트(strongly connected component) 로 나눌 수 있다. 여기에서 강결합 컴포넌트는 모든 노드에서 다른 모든 노드로 가는 경로가 있는 최대 노드 집합을 의미한다. 또한 각 컴포넌트를 노드로 하는 컴포넌트 그래프(component graph) 는 사이클이 없는 그래프로, 원래 그래프의 심층 구조를 나타내는 그래프가 된다. 예를 들어 그림 2에 그래프 하나와 그 그래프의 강결합 컴포넌트, 그리고 대응되는 컴포넌트 그래프가 나와 있다. 컴포넌트는 $A=\{1,2\},B=\{3,6,7\},C=\{4\},D=\{5\}$이다.

컴포넌트 그래프는 DAG로 원래의 그래프보다 처리하기 쉽다. 그래프에 사이클이 없기 때문에 위상 정렬 후 동적 계획법을 이용하여 처리하면 된다.

• 그림 2. 그래프와 강결합 컴포넌트, 컴포넌트 그래프
  • 

활용

• 2-SAT
• Dulmage-Mendelsohn decomposition

코사라주 알고리즘

**코사라주 알고리즘(Korasaju’s algorithm)**은 그래프의 강결합 컴포넌트를 찾는 유용한 방법이다. 이 알고리즘에서는 두 번의 깊이 우선 탐색 과정을 거친다. 첫 번째 탐색에서 그래프의 구조에 따라 노드 리스트를 만들고, 두 번째 탐색에서 강결합 컴포넌트를 구한다.

코사라주 알고리즘의 첫 번째 단계는 깊이 우선 탐색이 처리하는 순서대로 노드 리스트를 만드는 단계이다. 모든 노드를 거치면서 처리하지 않은 노드에 대해 깊이 우선 탐색을 진행한다. 노드의 처리가 끝나면 그 노드를 리스트에 추가한다.

예를 들어 그림 3에 예제 그래프에 대한 처리 순서가 나와 있다. $x/y$ 표기는 노드의 처리가 시각 $x$에 시작되고 시각 $y$에 끝났음을 의미한다. 만들어진 노드 리스트는 $[4,5,2,1,6,7,3]$이 된다.

• 그림 3. 노드의 처리 순서
  • 

코사라주 알고리즘의 두 번째 단계는 강결합 컴포넌트를 찾는 단계이다. 먼저 모든 간선의 방향을 뒤집는다. 이 과정을 통해 두 번째 탐색에서 강결합 컴포넌트를 찾을 수 있게 된다. 그림 4에 예제 그래프의 모든 간선의 방향을 뒤집은 그래프가 나와 있다. 그 다음, 첫 번째 탐색을 통해 만들어진 노드 리스트의 반대 순서대로 노드를 살펴본다. 노드가 컴포넌트에 속하지 않았다면 그 노드에서 새로운 깊이 우선 탐색을 진행하고, 이때 방문한 노드로 새로운 컴포넌트를 만든다. 모든 간선의 방향이 반대이기 때문에 컴포넌트에 속한 노드가 컴포넌트 바깥의 노드로 흐르지는 않는다.

• 그림 4. 간선의 방향을 뒤집은 그래프
  • 

예제 그래프에 대해 알고리즘을 적용한 결과가 그림 5에 나와 있다. 노드를 처리하는 순서는 $[3,7,6,1,2,5,4]$가 된다. 먼저 3번 노드를 처리함으로써 컴포넌트 $\{3,6,7\}$이 만들어진다. 다음으로 7번 노드와 6번 노드는 이미 컴포넌트에 포함되었기 때문에 넘어간다. 그 다음 1번 노드를 처리함으로써 컴포넌트 $\{1,2\}$가 만들어지고, 2번 노드는 넘어간다. 마지막으로 5번 노드와 4번 노드가 각각 컴포넌트 $\{5\}$와 컴포넌트 $\{4\}$가 된다.

이 알고리즘에서는 깊이 우선 탐색을 두 번 진행하므로 시간 복잡도가 $O(V+E)$이 된다.

• 그림 5. 강결합 컴포넌트 찾기
  • 

연습 코드

#include <iostream>
#include <vector>
using namespace std;
 
int n, m;
 
vector<vector<int>> graph;
vector<vector<int>> inverse_graph;
vector<bool>        visited;
vector<int>         order;      // 첫 번째 DFS 종료 순서
vector<int>         comp_id;    // 각 정점이 속한 SCC 번호
vector<vector<int>> components; // SCC 목록
 
// ----------------------------------
// TODO 1. 첫 번째 DFS
// ----------------------------------
void dfs1(int cur) {
	// 1) 현재 정점 방문 처리
	
	// 2) 원래 그래프(graph)로 DFS 진행
	
	// 3) 탐색이 끝난 뒤 order에 현재 정점 추가
}
 
// ----------------------------------
// TODO 2. 두 번째 DFS
// ----------------------------------
void dfs2(int cur, int id) {
	// 1) 현재 정점 방문 처리
	
	// 2) 현재 SCC 번호(id) 기록
	
	// 3) 현재 SCC 목록에 정점 추가
	
	// 4) 역그래프(revGraph)로 DFS 진행
}
 
// ----------------------------------
// SCC 구성
// ----------------------------------
void build_SCC() {
	// 1. 첫 번째 DFS
	for (int v = 1; v <= n; v++) {
		if (???){ // 방문안한 정점이라면
			??? // 탐색
		}
	}
 
	fill(visited.begin(), visited.end(), false);
	reverse(order.begin(), order.end());
 
	int scc_count = 0;
 
	// 두 번째 DFS
	for (int v: order) {
		if (!visited[v]) {
			??? // 새로운 컴포넌트 시작
			??? // 탐색
			scc_count++;
		}
	}
}
 
// ----------------------------------
// 결과 출력
// ----------------------------------
void print_SCC() {
	cout << "SCC 개수: " << components.size() << '\n';
 
	for (int i = 0; i < (int)components.size(); i++) {
		cout << "SCC #" << i << ": ";
		for (int v: components[i]) {
			cout << v << ' ';
		}
		cout << '\n';
	}
 
	cout << "\n각 정점의 SCC 번호\n";
	for (int v = 1; v <= n; v++) {
		cout << v << " -> " << comp_id[v] << '\n';
	}
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	cin >> n >> m;
 
	graph.assign(n + 1, {});
	inverse_graph.assign(n + 1, {});
	visited.assign(n + 1, false);
	comp_id.assign(n + 1, -1);
 
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
 
		graph[u].push_back(v);
		inverse_graph[v].push_back(u);
	}
 
	build_SCC();
	print_SCC();
 
	return 0;
}

• 정답 ¹

타잔 알고리즘

• 한번의 DFS로 찾는 방법
• 26. 강한 결합 요소(Strongly Con.. : 네이버블로그

함축

함축

$$P\to Q\equiv \neg P\vee Q$$

즉, “$P$이면 $Q$이다”는 “$P$가 아니거나 $Q$이다”와 같다.

• 숙제를 하면, 과자를 받는다 $\equiv$ 숙제를 안했거나, 과자를 받았다.
  • T, T → T
  • T, F → F (숙제를 했는데, 과자를 안 준 경우만 거짓)
  • F, T → T
  • F, F → T

Link to original

2-SAT 문제

• 연습 문제
  • 티비 쇼 게임 - JUNGOL
• 참고
  • 2-SAT (알고리즘)
  • 참고자료 - TV Show Game

2SAT 문제에서는 다음과 같은 논리식을 다룬다.

$$(a_1\vee b_1)\wedge (a_2\vee b_2)\wedge \cdots \wedge (a_m\vee b_m)$$

여기에서 $a_i$와 $b_i$는 논리 변수 $(x_1,x_2,\dots ,x_n)$, 또는 논리 변수의 부정 $(\neg x_1,\neg x_2,\dots ,\neg x_n)$이다. $\wedge$와 $\vee$는 논리곱(and) 및 논리합(or) 연산을 의미하는 기호이다. 각 변수에 값을 할당하여 식을 참으로 만드는 조합을 찾거나, 그러한 조합이 없음을 찾는 것이 목표이다.

예를 들어 다음 식을 살펴보자.

$$L_1=(x_2\vee \neg x_1)\wedge (\neg x_1\vee \neg x_2)\wedge (x_1\vee x_3)\wedge (\neg x_2\vee \neg x_3)\wedge (x_1\vee x_4)$$

이 식은 값이 다음과 같을 경우에 참이다.

$$\{\begin{array}{l}{x}_1=\mathrm{false}\\ x_2=\mathrm{false}\\ x_3=\mathrm{true}\\ x_4=\mathrm{true}\end{array}$$

하지만 다음 식은 값을 어떻게 할당하든 항상 거짓이다.

$$L_2=(x_1\vee x_2)\wedge (x_1\vee \neg x_2)\wedge (\neg x_1\vee x_3)\wedge (\neg x_1\vee x_3)\wedge (\neg x_1\vee \neg x_3)$$

그 이유는 $x_1$의 값을 모순 없이 정할 수 없기 때문이다. $x_1$이 거짓이라면 $x_2$와 $\neg x_2$가 모두 참이어야 해서 불가능하고, $x_1$이 참이라면 $x_3$와 $\neg x_3$가 모두 참이어야 해서 역시 불가능하다.

2SAT 문제에서 제시되는 식을 함의 그래프(implication graph)로 나타낼 수 있다. 이때 노드는 변수 $x_i$ 및 부정형 $\neg x_i$에 대응되며, 간선은 변수 간의 관계를 표현한다. 각각의 항 $(a_i\vee b_i)$에 대해 $\neg a_i\to b_i$와 $\neg b_i\to a_i$의 두 간선을 만든다. 이는 $a_i$가 참이 아닐 경우 $b_i$가 참이어야 함을 의미하며, 반대의 경우도 마찬가지이다. 예를 들어 그림 6에 $L_1$의 함의 그래프가 나와 있으며, 그림 7에는 $L_2$의 함의 그래프가 나와 있다.

• 그림 6. $L_1$의 함의 그래프

  • 

• 그림 7. $L_2$의 함의 그래프

  • 

수식이 참이 되도록 모든 변수에 값을 할당하는 것이 가능한지 여부는 함의 그래프의 구조에 따라 결정된다. 가능한 경우는 $x_i$ 노드와 $\neg x_i$ 노드가 같은 강결합 컴포넌트에 속하는 일이 없는 경우와 동치이다. 같은 강결합 컴포넌트에 속한 노드가 있으면 $x_i$ 노드에서 $\neg x_i$ 노드로 가는 경로, 그리고 $\neg x_i$ 노드에서 $x_i$ 노드로 가는 경로가 모두 있다는 의미이다. 따라서 $x_i$와 $\neg x_i$가 모두 참이어야 하지만 이는 불가능하다.

예를 들어 $L_1$의 함의 그래프에서는 $x_i$와 $\neg x_i$가 같은 강결합 컴포넌트에 속하는 경우가 없으므로 해가 존재한다. $L_2$의 함의 그래프에서는 모든 노드가 같은 강결합 컴포넌트에 속하므로 해가 존재하지 않는다.

해가 존재하는 경우, 변수의 값은 컴포넌트 그래프의 모든 노드를 위상 정렬 역순으로 방문하면서 찾을 수 있다. 단계마다 처리하지 않은 컴포넌트로 향하는 간선이 없는 컴포넌트를 처리한다. 컴포넌트의 변수에 값이 할당되지 않았다면, 그 컴포넌트에 속한 변수들에 따라 그 값을 결정하고, 이미 값이 할당된 변수는 그 값을 유지한다. 이 과정을 모든 변수에 값이 할당될 때까지 진행한다.

그림 8에 $L_1$의 컴포넌트 그래프가 나와 있다. 각 컴포넌트는 $A=\{\neg x_4\}$, $B=\{x_1,x_2,\neg x_3\}$, $C=\{\neg x_1,\neg x_2,x_3\}$, $D=\{x_4\}$이다. 해를 찾기 위해 먼저 컴포넌트 $D$를 처리하며, $x_4$의 값은 참이 된다. 다음으로 컴포넌트 $C$를 처리하고, $x_1$과 $x_2$의 값은 거짓, $x_3$의 값은 참이 된다. 모든 변수에 값이 할당되었으므로 컴포넌트 $A$와 $B$를 처리할 때는 변수의 값이 바뀌지 않는다.

• 그림 8. $L_1$의 컴포넌트 그래프
  • 

이 방법이 성립하는 이유는 함의 그래프가 특별한 구조로 되어 있기 때문이다. $x_i$ 노드에서 $x_j$ 노드로 가는 경로, 그리고 $x_j$ 노드에서 $\neg x_i$ 노드로 가는 경로가 모두 있다면 $x_i$ 노드가 참이 될 수 없다. 그 이유는 $\neg x_j$ 노드에서 $\neg x_i$ 노드로 가는 경로도 있어서 $x_i$와 $x_j$가 모두 거짓이 되기 때문이다.

더 어려운 문제는 3SAT 문제인데, 이는 논리식의 각 항이 $(a_i\vee b_i\vee c_i)$의 형태로 되어 있는 경우이다. 이 문제는 NP-하드로, 효율적인 알고리즘이 알려지지 않았다.

2-SAT 구현 절차

•   절 (a ∨ b)
    	↓
    간선 ¬a -> b, ¬b -> a 생성
    	↓
    함의 그래프 완성
    	↓
    SCC 분해
    	↓
    x와 ¬x가 같은 SCC에 있는지 확인
    	↓
    있으면 불가능
    없으면 가능
    	↓
    컴포넌트 DAG의 위상 순서를 이용해 값 배정 

Footnotes

1. #include <iostream>
   #include <vector>
   #include <algorithm>
   using namespace std;
   	
   int n, m;
   	
   vector<vector<int>> graph;
   vector<vector<int>> inverse_graph;
   vector<bool>        visited;
   vector<int>         order;      // 첫 번째 DFS 종료 순서
   vector<int>         comp_id;    // 각 정점이 속한 SCC 번호
   vector<vector<int>> components; // SCC 목록
   	
   // ----------------------------------
   // TODO 1. 첫 번째 DFS
   // ----------------------------------
   void dfs1(int cur) {
       // 1) 현재 정점 방문 처리
       visited[cur] = true;
   	
       // 2) 원래 그래프(graph)로 DFS 진행
       for (int nxt : graph[cur]) {
           if (!visited[nxt]) {
               dfs1(nxt);
           }
       }
   	
       // 3) 탐색이 끝난 뒤 order에 현재 정점 추가
       order.push_back(cur);
   }
   	
   // ----------------------------------
   // TODO 2. 두 번째 DFS
   // ----------------------------------
   void dfs2(int cur, int id) {
       // 1) 현재 정점 방문 처리
       visited[cur] = true;
   	
       // 2) 현재 SCC 번호(id) 기록
       comp_id[cur] = id;
   	
       // 3) 현재 SCC 목록에 정점 추가
       components[id].push_back(cur);
   	
       // 4) 역그래프(inverse_graph)로 DFS 진행
       for (int nxt : inverse_graph[cur]) {
           if (!visited[nxt]) {
               dfs2(nxt, id);
           }
       }
   }
   	
   // ----------------------------------
   // SCC 구성
   // ----------------------------------
   void build_SCC() {
       // 1. 첫 번째 DFS
       for (int v = 1; v <= n; v++) {
           if (!visited[v]) { // 방문 안 한 정점이라면
               dfs1(v);       // 탐색
           }
       }
   	
       fill(visited.begin(), visited.end(), false);
       reverse(order.begin(), order.end());
   	
       int scc_count = 0;
   	
       // 2. 두 번째 DFS
       for (int v : order) {
           if (!visited[v]) {
               components.push_back({}); // 새로운 컴포넌트 시작
               dfs2(v, scc_count);       // 탐색
               scc_count++;
           }
       }
   }
   	
   // ----------------------------------
   // 결과 출력
   // ----------------------------------
   void print_SCC() {
       cout << "SCC 개수: " << components.size() << '\n';
   	
       for (int i = 0; i < (int)components.size(); i++) {
           cout << "SCC #" << i << ": ";
           for (int v : components[i]) {
               cout << v << ' ';
           }
           cout << '\n';
       }
   	
       cout << "\n각 정점의 SCC 번호\n";
       for (int v = 1; v <= n; v++) {
           cout << v << " -> " << comp_id[v] << '\n';
       }
   }
   	
   int main() {
       ios::sync_with_stdio(false);
       cin.tie(nullptr);
   	
       cin >> n >> m;
   	
       graph.assign(n + 1, {});
       inverse_graph.assign(n + 1, {});
       visited.assign(n + 1, false);
       comp_id.assign(n + 1, -1);
   	
       for (int i = 0; i < m; i++) {
           int u, v;
           cin >> u >> v;
   	
           graph[u].push_back(v);
           inverse_graph[v].push_back(u);
       }
   	
       build_SCC();
       print_SCC();
   	
       return 0;
   }

   ↩