ainta's profile image

ainta

September 17, 2019 23:30

Counting the number of topologies on a finite set

algorithm , mathematics , topology , problem-solving

Topology

수학에서, topological space란 다음 조건을 만족하는 집합 \(X\)와 \(X\)의 subset들의 collection \(\tau\)에 대해 ordered pair \((X, \tau)\) 를 말한다.

  1. \[\phi, X \in \tau\]
  2. Any arbitrary union of members of \(\tau\) still belongs to \(\tau\). (\(\tau\)의 원소들의 합집합은 \(\tau\)의 원소이다)
  3. The intersection of any finite number of members of \(\tau\) still belongs to \(\tau\). (\(\tau\)의 원소 유한개의 교집합은 \(\tau\)의 원소이다)

이때 \(\tau\)의 원소들을 open set이라 하고, \(\tau\)를 topology on \(X\)라 한다.

Counting the number of topology

만약 \(X\)가 유한집합이라면, topology on \(X\)의 개수도 당연히 유한할 것이다. 이 개수를 어떻게 counting할 수 있을까?

더 나아가, \(X\)의 어떤 subset들의 집합 \(A = \left\{a_1, a_2, .., a_n \right\}\)에 대해, \(A\)의 원소들을 모두 open set으로 가지는 topology의 개수를 효율적으로 구할 수 있을까?

이를 실제로 모든 topology를 구하지 않고 개수만 세는 것은 쉽지 않다. 그렇다면, 모든 topology를 나열하는 것을 빠르게 할 수 있을까?

다음은 필자가 Open cup, Grand Prix of Daejeon에 낸 문제이다.

문제 링크

topological space의 정의에서, 만약 \(X\)가 유한 개의 원소로 이루어져 있다면, 2번 조건 및 3번 조건을 각각 임의의 원소들의 합집합, 유한개 원소들의 교집합이 아닌 단 두 개의 원소의 합집합/교집합으로 바꿔도 같은 정의이다. 따라서, 문제에서 구하는 good set의 정의는 \(X = \left\{ 0, 1, ... , k-1 \right\}\) 일 때, topology on \(X\)의 정의와 거의 일치한다. 공집합과 전체집합을 포함한다는 조건이 빠져 있는데, 이는 쉽게 처리할 수 있다.

그렇다면, 다음 문제를 해결하는 것으로 충분하다 : \(X = \left\{ 0, 1, ... , k-1 \right\}\)의 어떤 subset들의 집합 \(A = \left\{a_1, a_2, .., a_n \right\}\)에 대해, \(A\)의 원소들을 모두 open set으로 가지는 topology의 개수를 효율적으로 구할 수 있을까?

그래프 \(G = (V, E)\) 가 \((u, v), (v,w) \in E\)이면 \((u, w) \in E\)를 만족할 때, \(G\)를 transitive digraph라고 한다. 놀랍게도, \(n\)개의 원소로 이루어진 집합 \(X\)에서 topology on \(X\)와 \(n\)개의 vertex로 이루어진 transitive digraph들은 일대일 대응 관계에 있다.

\(X = \left\{ 0, 1, ... , k-1 \right\}\) 에서의 Topology \(T\)에 대해, 그래프 \(f(T) = (V, E)\) 를 다음과 같이 정의하자 : 서로 다른 ​\(u, v\)에 대해, ​\(T\)의 ​\(u\)를 원소로 가지는 모든 open set들이 ​\(v\) 역시 원소로 가질 때만 ​\((u, v) \in E\).

이 때, \(f(T)\)가 transitive digraph인 것은 정의에 의해 자명하다.

\(V = \left\{ 0, 1, ... , k-1 \right\}\)인 transitive digraph \(G = (V, E)\)에 대해, \(V\)의 부분집합들의 집합 \(g(G)\)를 다음과 같이 정의하자.

\(A \subset V\)인 \(A\)에 대해, \(A\)에서 \(A^C\)로 가는 간선이 없는 경우에만 \(A \in g(G)\).

\(g(G)\)가 \(V\)에서의 topology임은 topology가 될 조건 1, 2, 3을 이용해 간단히 보일 수 있고, \(f(g(G)) = G\) 및 \(g(f(F))=F\)가 성립하므로 \(f, g\)는 topology와 transitive digraph의 bijection이다. 따라서, 둘은 일대일 대응 관계에 있다.

그러면 이제 주어진 subset들을 포함하는 good set들을 구하는 대신에, \(g(G)\)가 주어진 모든 subset을 포함하는 transitive digraph의 개수를 세는 것으로 문제를 해결할 수 있다. backtracking으로 빠른 시간내에 모든 답을 열거할 수 있는데, 그래프의 edge를 \((0,1), (1,0), (0,2), (2,0), (1,2), (2,1), ..., (k-3, k-1), (k-1, k-3), (k-2, k-1), (k-1, k-2)\)와 같이 \(max(u,v)\)가 작은 순서대로 추가할지 말지 결정하면서 backtracking을 하면 bitmask를 이용하는 경우 edge 하나를 추가할 지 말지 결정하고 다음 가지로 뻗어나가는 것까지 \(O(1)\) 시간에 처리 가능하다.

총 시간복잡도를 생각해 보면, 크기가 \(m\)인 집합의 topology 개수를 \(T_m\)이라 하면 backtracking에서 하는 연산은 \(\sum_{i=1}^k T_i \times i\) 개의 \(O(1)\) 연산임을 알 수 있다.

\(\left\{T_1, T_2, T_3, T_4, T_5, T_6, T_7\right\}\) = \(\left\{1, 4, 29, 355, 6942, 209527, 9535241\right\}\) 이고 \(\sum_{i=1}^k T_i \times i \le 7 \times 10^7\)이므로, 빠른 시간 (1초) 이내에 조건을 만족하는 모든 good set을 탐색할 수 있다.

다음은 이 문제를 해결하는 코드이다.

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int w[8], AY[8], AN[8], BY[8], BN[8], res, cnt, E[8][8];
struct Edge {
	int a, b;
}Ed[60];
void DFS(int pv) {
	if (pv == cnt) {
		res++;
		return;
	}
	int x = Ed[pv].a, y = Ed[pv].b;
	if (!(AY[x] & BY[y])) { // (x,y) 간선을 추가하지 않는 경우
		AN[x] ^= (1 << y);
		BN[y] ^= (1 << x);
		DFS(pv + 1);
		AN[x] ^= (1 << y);
		BN[y] ^= (1 << x);
	}
	if (!(AN[x] & AY[y]) && !(BY[x] & BN[y]) && E[x][y]) { // (x,y) 간선을 추가하는 경우
		AY[x] ^= (1 << y);
		BY[y] ^= (1 << x);
		DFS(pv + 1);
		AY[x] ^= (1 << y);
		BY[y] ^= (1 << x);
	}
}
void Do(int n) {
	int i, j;
	for (i = 0; i < n; i++)AN[i] = BN[i] = 0, AY[i] = BY[i] = (1 << i);
	cnt = 0;
	for (i = 0; i < n; i++)for (j = 0; j < i; j++) {
		Ed[cnt++] = { j,i }; //ED에 있는 directed edge들의 순서대로 backtracking에서 간선을 추가할지 말지 선택한다.
		Ed[cnt++] = { i,j };
	}
	DFS(0);
}
int v[256], K, m;
void Calc(int LB, int MB) {
	int i, j, k, sz;
	vector<int>T;
	for (j = 0; j < K; j++) {
		if (((LB^MB) >> j) & 1) T.push_back(j); // LB에는 포함되지 않고 MB에는 포함되는 원소가 실제로 고려할 대상들이다.
	}
	sz = T.size();
	for (i = 0; i < sz; i++)for (j = 0; j < sz; j++)E[i][j] = 1;
	for (i = 0; i < (1 << K); i++) {
		if (!v[i])continue;
		if ((i&LB) != LB)return;
		if ((i&MB) != i)return;
		for (j = 0; j < sz; j++)for (k = 0; k < sz; k++)if (((i >> T[j]) & 1) && !((i >> T[k]) & 1)) E[k][j] = 0;
	}
	Do(sz);
}
int main() {
	int i, a, j, k;
	scanf("%d%d", &K, &m);
	for (i = 0; i < m; i++) {
		scanf("%d", &a);
		v[a] = 1;
	}
	for (i = 0; i < (1 << K); i++) {
		for (j = 0; j < (1 << K); j++) {
			if ((i&j) != i)continue;
			Calc(i, j); //topology에서 공집합 및 전체집합 포함 조건이 빠져있는데, i가 공집합에 해당하고 j가 전체집합에 해당하는 경우를 탐색하겠다는 뜻이다. 즉, good set 중 최소원소가 i고 최대원소가 j인 것의 개수를 구한다.
		}
	}
	printf("%d\n", res);
}