레인보우 스패닝 트리

색 집합 $S\subseteq\{1,2,\dots,7\}$에 대하여, $S$에 속한 색 중 적어도 하나로 칠할 수 있는 간선들의 집합을 $E(S)$라 하자. 즉 $E(S)=\{\,e : A_e\cap S\neq\emptyset\,\}$이다. 또한 $r(S)$를 $E(S)$의 간선만 사용하여 만들 수 있는 forest의 최대 간선 수, 즉 $E(S)$ 안에서 사이클 없이 택할 수 있는 간선 수의 최댓값이라 하자.

$r(S)$는 DSU로 계산할 수 있다. 처음에는 모든 정점을 서로 다른 component에 둔다. 간선을 하나씩 보면서, 그 간선이 $S$에 속한 색 중 하나라도로 칠할 수 있으면(즉 $A_e\cap S\neq\emptyset$이면) 양 끝점을 합친다. 이때 실제로 서로 다른 두 component가 합쳐진 횟수가 이다. 색이 7개뿐이므로 비어 있지 않은 색 집합은 개이며, 따라서 모든 에 대하여 를 미리 계산해 둘 수 있다.

판정 조건

spanning tree는 항상 정확히 $N-1$개의 간선을 가지므로, 먼저 $a_1+a_2+\cdots+a_7=N-1$이어야 한다. 이 조건이 성립하지 않으면 답은 이다. 이 조건이 성립한다고 할 때, 답이 이기 위한 필요충분조건은 모든 색 집합 에 대하여

$$\sum_{j\in S}a_j \le r(S)$$

가 성립하는 것이다.

이 조건의 필요성은 다음과 같이 확인된다. 색 집합 $S$에 속한 색으로 칠해야 하는 간선은 총 $\sum_{j\in S}a_j$개이다. 그런데 색이 $S$에 속하도록 칠해진 간선은 모두 에 속해야 하고, spanning tree의 부분집합이므로 그들끼리도 사이클을 이룰 수 없다. 따라서 그 개수는 안의 forest 최대 크기인 를 넘을 수 없다. 즉 를 만족하는 색 집합 가 존재하면 답은 이다.

이제 이 조건이 충분함을 보인다.

증명

간선 집합 위의 독립성을 "사이클을 이루지 않음"으로 정의하면, 독립 집합은 forest이며 그 rank는 해당 간선 집합 내 forest의 최대 크기이다. 이는 곧 graph matroid이다.

Theorem 2.1. Rado's Theorem

matroid $M$의 ground set을 $E$, rank 함수를 $\rho$라 하고, 집합 $A_1,\dots,A_m\subseteq E$가 주어졌다고 하자. 각 마다 를 택하여 이 모두 서로 다르고 이 에서 독립이 되도록 할 수 있을 필요충분조건은 모든 에 대하여

구현과 시간복잡도

정리하면, 한 질의의 답이 Yes이기 위한 필요충분조건은 두 가지이다. 첫째, $a_1+a_2+\cdots+a_7=N-1$이어야 한다. 둘째, 모든 색 집합 에 대하여 이어야 한다.