DOJ

해설

색 집합 $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가 합쳐진 횟수가 $r(S)$ 이다. 색이 7개뿐이므로 비어 있지 않은 색 집합은 $2^7-1=127$ 개이며, 따라서 모든 $S$ 에 대하여 $r(S)$ 를 미리 계산해 둘 수 있다.

판정 조건

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

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

가 성립하는 것이다.

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

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

증명 1. Real Stable Polynomial

$r(\{1,2,\dots,7\})<N-1$ 이면 칠할 수 있는 간선만으로는 spanning tree를 만들 수 없으므로 답은 항상 No이며, 이 경우 판정 조건 또한 $S=\{1,2,\dots,7\}$ 에서 실패한다. 따라서 이제 $r(\{1,2,\dots,7\})=N-1$ 이라고 가정한다. 또한 칠할 수 있는 색이 존재하지 않는 간선( $A_e=\emptyset$ )은 어떤 해에도 사용될 수 없으므로 미리 제거하여도 무방하다.

각 간선 $e$ 의 색 집합 $A_e$ 를 이용하여 다음 다항식을 정의한다.

F(x_1,x_2,\dots,x_7)=\sum_{T}\;\prod_{e\in T}\Bigl(\sum_{j\in A_e}x_j\Bigr)

여기서 합은 그래프의 모든 spanning tree $T$ 에 대하여 취한다. 단항식 $x_1^{a_1}x_2^{a_2}\cdots x_7^{a_7}$ 를 생성하는 방법은, spanning tree $T$ 를 하나 택한 뒤 각 간선 $e$ 마다 $A_e$ 에 속한 색 하나를 골라(즉 $\sum_{j\in A_e}x_j$ 에서 한 항을 택하여) 색 $j$ 가 정확히 $a_j$ 번 등장하도록 하는 것과 일대일로 대응한다. 따라서 질의의 답이 Yes인 것은 이 단항식의 계수가 양수인 것과 동치이다.

Definition 1.1. Newton Polytope

다변수 다항식 $p(x_1,\dots,x_k)$ 를 단항식들의 합으로 나타낼 때, 계수가 $0$ 이 아닌 단항식들의 지수 벡터 집합을 $\operatorname{supp}(p)$ 라 한다. 단항식 $x_1^{b_1}\cdots x_k^{b_k}$ 의 지수 벡터는 $(b_1,\dots,b_k)$ 이다. $p$ 의 Newton polytope은 $\operatorname{supp}(p)$ 의 convex hull, 즉

\operatorname{Newt}(p)=\operatorname{conv}\bigl(\operatorname{supp}(p)\bigr)

이다.

먼저 $\operatorname{Newt}(F)\subseteq P$ 임을 보인다. 실제로 만들 수 있는 색 개수 벡터 $b=(b_1,\dots,b_7)$ 는 $b_1+\cdots+b_7=N-1$ 을 만족하며, 모든 $S$ 에 대하여 $\sum_{j\in S}b_j\le r(S)$ 를 만족한다(앞의 필요성 논증과 동일한 이유이다). 따라서 $\operatorname{Newt}(F)$ 는 다음 polytope에 포함된다.

P=\Bigl\{x\in\mathbb{R}_{\ge 0}^7 : x_1+\cdots+x_7=N-1,\ \sum_{j\in S}x_j\le r(S)\text{ for all }S\subseteq\{1,\dots,7\}\Bigr\}

이제 역으로 $\operatorname{Newt}(F)=P$ 임을 보인다. 두 polytope이 모든 선형 목적함수에 대하여 동일한 최댓값을 가지면 서로 일치하므로, 이를 확인하는 것으로 충분하다. 실수 가중치 $c_1,\dots,c_7$ 을 고정하고 $c\cdot b=\sum_j c_jb_j$ 를 최대화하는 경우를 생각한다. 색을 $c_{\pi_1}\ge c_{\pi_2}\ge\cdots\ge c_{\pi_7}$ 이 되도록 정렬하고 $S_t=\{\pi_1,\dots,\pi_t\}$ 로 둔다.

간선 $e$ 가 선택되었을 때 그 간선이 줄 수 있는 최대 기여도는 $\displaystyle\max_{j\in A_e}c_j$ 이며, 이는 다음과 같이 다시 쓸 수 있다.

\max_{j\in A_e}c_j=c_{\pi_7}+\sum_{t=1}^{6}(c_{\pi_t}-c_{\pi_{t+1}})\,[\,A_e\cap S_t\neq\emptyset\,]

여기서 $[\,\cdot\,]$ 은 괄호 안의 명제가 참이면 $1$ , 거짓이면 $0$ 이다. ( $A_e$ 안에서 $\pi$ -순서가 가장 빠른 색이 $\pi_k$ 이면 위 합은 $t\ge k$ 에서만 $1$ 이 되어, telescoping에 의하여 $c_{\pi_k}$ 가 된다.)

이는 간선의 기여도가 중첩된 집합열 $E(S_1)\subseteq E(S_2)\subseteq\cdots\subseteq E(S_7)$ 중 그 간선이 어디까지 속하는지에 의해서만 결정됨을 뜻한다. Kruskal 알고리즘으로 높은 단계의 간선을 먼저 최대한 택하면, $c\cdot b$ 의 최댓값은

c_{\pi_7}(N-1)+\sum_{t=1}^{6}(c_{\pi_t}-c_{\pi_{t+1}})\,r(S_t)

가 된다. 어떤 spanning tree도 $E(S_t)$ 에서 $r(S_t)$ 개를 초과하여 가질 수 없으므로 이 값은 상한이며, Kruskal 알고리즘이 그 상한을 달성한다.

Definition 1.2. Submodular 함수와 base polymatroid

집합 함수 $f:2^U\to\mathbb{R}$ 가 모든 $A\subseteq B$ 에 대하여 $f(A)\le f(B)$ 를 만족하면 증가 함수라 하고, 모든 $A,B\subseteq U$ 에 대하여

f(A)+f(B)\ge f(A\cup B)+f(A\cap B)

를 만족하면 submodular 함수라 한다. $f(\emptyset)=0$ 인 증가 submodular 함수 $f$ 에 대하여

P_f=\{\,x\in\mathbb{R}_{\ge 0}^U : x(U)=f(U),\ x(S)\le f(S)\text{ for all }S\subseteq U\,\}

를 base polymatroid라 한다. 여기서 $x(S)=\sum_{i\in S}x_i$ 이다.

Lemma 1.3. Submodular greedy

$f:2^U\to\mathbb{Z}_{\ge 0}$ 가 $f(\emptyset)=0$ 인 증가 submodular 함수라 하자. 가중치를 $c_{\pi_1}\ge\cdots\ge c_{\pi_k}$ 로 정렬하고 $S_t=\{\pi_1,\dots,\pi_t\}$ 라 하면, base polymatroid $P_f$ 위에서 $c\cdot x$ 의 최댓값은

c_{\pi_k}f(U)+\sum_{t=1}^{k-1}(c_{\pi_t}-c_{\pi_{t+1}})f(S_t)

이다.

임의의 $x\in P_f$ 에 대하여

c\cdot x=c_{\pi_k}x(U)+\sum_{t=1}^{k-1}(c_{\pi_t}-c_{\pi_{t+1}})x(S_t)

이고, $x(U)=f(U)$ 이며 $x(S_t)\le f(S_t)$ 이므로 위 값은 주어진 식 이하이다. 이제 이 상한이 달성됨을 보인다. $S_0=\emptyset$ 로 두고 $x_{\pi_t}=f(S_t)-f(S_{t-1})$ 로 정의하면, 증가성에 의하여 $x_{\pi_t}\ge 0$ 이고 telescoping에 의하여 $x(U)=f(U)$ 이다. 남은 것은 모든 $A\subseteq U$ 에 대하여 $x(A)\le f(A)$ 임을 보이는 것이다. $A_t=A\cap S_t$ 라 하자. $\pi_t\notin A$ 이면 $A_t=A_{t-1}$ 이다. $\pi_t\in A$ 이면 $A_{t-1}\subseteq S_{t-1}$ 이므로 submodular 함수의 diminishing return 성질에 의하여 $f(S_t)-f(S_{t-1})\le f(A_t)-f(A_{t-1})$ , 즉 $x_{\pi_t}\le f(A_t)-f(A_{t-1})$ 이다. 이를 $t$ 에 대하여 모두 더하면 $x(A)\le f(A)$ 를 얻는다. 따라서 이 $x$ 는 $P_f$ 에 속하며 위 상한을 달성한다.

이제 $S\mapsto r(S)$ 가 증가 submodular 함수임을 보인다. 증가성은 명백하다. Submodularity는 다음으로부터 따라온다. matroid의 rank 함수 $\rho$ 는 간선 집합에 대하여 submodular이고, $E(A\cup B)=E(A)\cup E(B)$ , $E(A\cap B)\subseteq E(A)\cap E(B)$ 이므로

r(A)+r(B)=\rho(E(A))+\rho(E(B))\ge \rho(E(A)\cup E(B))+\rho(E(A)\cap E(B))\ge r(A\cup B)+r(A\cap B)

이다. 따라서 Lemma 1.3을 $U=\{1,\dots,7\}$ , $f=r$ 에 적용하면 $P$ 위에서의 선형 목적함수 최댓값 또한 앞에서 구한 값과 정확히 일치한다. 모든 선형 목적함수에 대하여 두 polytope의 최댓값이 일치하므로

\operatorname{Newt}(F)=P

이다.

Definition 1.4. Real Stable Polynomial

복소수 $z$ 의 허수부를 $\operatorname{Im}(z)$ 라 하고, 열린 위쪽 반평면을 $\operatorname{Im}(z)>0$ 인 복소수들의 집합이라 하자. 실계수 다항식 $p(x_1,\dots,x_k)$ 가 real stable이라는 것은, 모든 $j$ 에 대하여 $\operatorname{Im}(z_j)>0$ 일 때 항상 $p(z_1,\dots,z_k)\neq 0$ 임을 뜻한다.

Theorem 1.5. Matrix-Tree Theorem

그래프의 각 간선 $e$ 에 변수 $y_e$ 를 대응시킨다. 각 간선에 임의로 방향을 부여하고 incidence matrix에서 한 행을 제거한 것을 reduced incidence matrix $B$ 라 하면, weighted reduced Laplacian은 $B\operatorname{diag}(y_e)B^{T}$ 이고

\det\bigl(B\operatorname{diag}(y_e)B^{T}\bigr)=\sum_{T}\prod_{e\in T}y_e

이다. 합은 모든 spanning tree $T$ 에 대하여 취한다.

Lemma 1.6. Spanning tree polynomial은 real stable이다

연결 그래프 $G$ 의 spanning tree polynomial을

\tau_G(y)=\sum_{T}\prod_{e\in T}y_e

라 하면, $\tau_G$ 는 real stable이다.

Theorem 1.5에 의하여 $\tau_G(y)=\det(B\operatorname{diag}(y_e)B^{T})$ 이다. 모든 $y_e$ 가 $\operatorname{Im}(y_e)>0$ 를 만족한다고 하자. 만약 $B\operatorname{diag}(y_e)B^{T}$ 가 특이행렬이면 어떤 $z\neq 0$ 에 대하여 $z^{*}B\operatorname{diag}(y_e)B^{T}z=0$ 이다. $u=B^{T}z$ 로 두면 이 값은 $\sum_e y_e\,|u_e|^2$ 이며, 그 허수부는

\sum_e \operatorname{Im}(y_e)\,|u_e|^2

이다. 연결 그래프에서 $B$ 는 full row rank이므로 $z\neq 0$ 이면 $u=B^{T}z\neq 0$ 이고, 어떤 $e$ 에 대하여 $u_e\neq 0$ 이다. 모든 $\operatorname{Im}(y_e)>0$ 이므로 위 허수부는 양수가 되어 가정에 모순이다. 따라서 $\tau_G(y)\neq 0$ 이며, $\tau_G$ 는 real stable이다.

Lemma 1.7. 음이 아닌 선형 대입은 real stability를 보존한다

$p(y_1,\dots,y_m)$ 이 real stable이고, 각 $i$ 에 대하여 $L_i(x_1,\dots,x_k)=\sum_{j} c_{ij}x_j$ 가 음이 아닌 계수를 가지며 적어도 하나의 계수는 양수라고 하자. 그러면 $p(L_1,\dots,L_m)$ 또한 real stable이다.

모든 $x_j$ 가 위쪽 반평면에 있으면 $\operatorname{Im}(L_i)=\sum_j c_{ij}\operatorname{Im}(x_j)>0$ 이므로 각 $L_i$ 또한 위쪽 반평면에 있다. $p$ 가 real stable이므로 이때 $p(L_1,\dots,L_m)\neq 0$ 이다. 따라서 $p(L_1,\dots,L_m)$ 또한 real stable이다.

Lemma 1.6에 의하여 $\displaystyle\sum_{T}\prod_{e\in T}y_e$ 는 real stable이며, 각 $y_e$ 에 $\sum_{j\in A_e}x_j$ 를 대입하여도 Lemma 1.7에 의하여 real stability가 보존된다. 따라서 $F$ 는 real stable이며, $F$ 의 모든 단항식은 차수가 모두 $N-1$ 이다.

Lemma 1.8. Saturated Newton Polytope

$p$ 가 real stable이고 $p$ 의 모든 단항식의 차수가 같으면

\operatorname{supp}(p)=\operatorname{Newt}(p)\cap\mathbb{Z}^k

이다.

Brändén의 정리에 의하여 real stable 다항식의 support는 jump system이다. 모든 support 벡터의 좌표합이 같으면 이 jump system은 $M$ -convex set이 되며, 다음 교환 성질을 갖는다. $\alpha,\beta\in\operatorname{supp}(p)$ 이고 어떤 좌표 $i$ 에 대하여 $\alpha_i>\beta_i$ 이면, 어떤 좌표 $j$ 에 대하여 $\alpha_j<\beta_j$ 이고 $\alpha-e_i+e_j\in\operatorname{supp}(p)$ 이다. 이 성질을 반복하면 $\operatorname{supp}(p)$ 의 convex hull 안의 모든 정수점이 다시 support에 속함을 보일 수 있다. 따라서 $\operatorname{supp}(p)=\operatorname{Newt}(p)\cap\mathbb{Z}^k$ 이다.

Lemma 1.8에 의하여 $F$ 의 support는 $\operatorname{Newt}(F)=P$ 안의 정수점 전체를 포함한다. 따라서 $a_1+\cdots+a_7=N-1$ 과 모든 $S$ 에 대한 $\sum_{j\in S}a_j\le r(S)$ 를 만족하는 정수 벡터 $(a_1,\dots,a_7)$ 는 $P$ 에 속하는 정수점이며, 단항식 $x_1^{a_1}\cdots x_7^{a_7}$ 의 계수가 양수이다. 따라서 조건을 만족하는 spanning tree와 색 배정이 존재한다.

증명 2. Rado's Theorem

간선 집합 위의 독립성을 "사이클을 이루지 않음"으로 정의하면, 독립 집합은 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$ 가 주어졌다고 하자. 각 $i$ 마다 $x_i\in A_i$ 를 택하여 $x_1,\dots,x_m$ 이 모두 서로 다르고 $\{x_1,\dots,x_m\}$ 이 $M$ 에서 독립이 되도록 할 수 있을 필요충분조건은 모든 $I\subseteq\{1,\dots,m\}$ 에 대하여

\rho\Bigl(\bigcup_{i\in I}A_i\Bigr)\ge |I|

가 성립하는 것이다.

색 $j$ 로 칠할 수 있는 간선들의 집합을 $E_j$ 라 하자(즉 $E_j=E(\{j\})$ ). 각 색 $j$ 마다 정확히 $a_j$ 개의 간선을 선택하되, 선택된 간선들은 전체적으로 서로 다르고 사이클을 이루지 않아야 한다.

각 색 $j$ 에 대하여 " $E_j$ 에서 간선 하나를 선택한다"는 요구사항을 $a_j$ 개 생성한다. Theorem 2.1을 적용하면, 모든 요구사항을 서로 다른 간선으로 만족하면서 전체가 독립(forest)이 되도록 할 수 있을 필요충분조건은, 요구사항들의 임의의 부분집합에 대하여 해당 요구사항들이 선택할 수 있는 간선들의 합집합의 rank가 요구사항의 개수 이상인 것이다.

요구사항들의 부분집합 하나를 택하고, 거기에 등장하는 색들의 집합을 $S$ 라 하자. 해당 요구사항들이 선택할 수 있는 간선들의 합집합은 $\displaystyle\bigcup_{j\in S}E_j=E(S)$ 이고 그 rank는 $r(S)$ 이다. 주어진 색 집합 $S$ 에 대하여 가장 강한 제약은 $S$ 에 속한 색의 요구사항을 모두 포함하는 경우에 발생하며, 이때 요구사항의 개수는 $\sum_{j\in S}a_j$ 이다. 따라서 Theorem 2.1의 조건은 정확히 "모든 $S$ 에 대하여 $\sum_{j\in S}a_j\le r(S)$ "와 동치이다.

이 조건이 성립하면 각 색 $j$ 에서 정확히 $a_j$ 개의 간선을 선택하여 전체가 forest가 되도록 할 수 있다. $a_1+\cdots+a_7=N-1$ 이므로 선택된 간선은 총 $N-1$ 개이고, 정점이 $N$ 개인 그래프에서 $N-1$ 개의 간선을 갖는 forest는 연결되어 있어야 하므로 spanning tree이다. 따라서 조건을 만족하는 spanning tree와 색 배정이 존재한다.

구현과 시간복잡도

정리하면, 한 질의의 답이 Yes이기 위한 필요충분조건은 두 가지이다. 첫째, $a_1+a_2+\cdots+a_7=N-1$ 이어야 한다. 둘째, 모든 색 집합 $S\subseteq\{1,2,\dots,7\}$ 에 대하여 $\sum_{j\in S}a_j\le r(S)$ 이어야 한다.

따라서 각 질의마다 먼저 합이 $N-1$ 인지 확인하고, 그렇지 않으면 No를 출력한다. 이후 $127$ 개의 색 집합을 모두 검사하여, 하나라도 위배되면 No를, 모두 만족하면 Yes를 출력한다.

$\sum_{j\in S}a_j$ 는 bitmask DP로 한 번에 구할 수 있다. 색 $j$ 를 비트 $j$ 에 대응시키고, $S$ 에서 임의의 색 $x$ 하나를 제거하면 $\text{need}[S]=\text{need}[S\setminus\{x\}]+a_x$ 이므로, 질의 하나당 $O(2^7)$ 에 모든 $S$ 에 대한 $\text{need}[S]$ 를 구할 수 있다.

전체 시간복잡도는 $O(2^7M\,\alpha(N)+2^7Q)$ 이다. 첫 번째 항은 $127$ 개의 색 집합 각각에 대하여 DSU로 $r(S)$ 를 전처리하는 비용이며, 두 번째 항은 각 질의에서 모든 색 집합을 검사하는 비용이다.

Solution by Claude Opus 4.8

레인보우 스패닝 트리

해설