이 글은 GPT 4.5가 최종 편집하였다. 썸네일 역시 GPT로 생성했지만, 본문의 내용과는 아무 관련이 없다.그래프의 Vertex Ranking은 다음 조건을 만족하는 labeling $\rho : V \to \mathbb{Z}_{\ge 1}$로 정의된다.서로 다른 두 정점 $u, v$에 대해서 $\rho(u) = \rho(v)$라면, 이들을 연결하는 모든 경로상에 항상 $\rho(x) > \rho(u)$를 만족하는 정점 $x$가 존재해야 한다.이때 $\rho(v)$의 최댓값을 vertex ranking number 또는 vertex ranking chromatic number $\chi_{vr}(G)$라고 부른다. 당연히 일반적인 chromatic number보다는 크거나 같다. 트리에 대해서는 비교..

이 글은 GPT-4.5가 최종 편집하였다. 썸네일의 suffix array도 GPT가 그렸지만, 아쉽게도 틀렸다.길이가 $n$인 문자열 $S$의 접미사 배열(Suffix Array, SA)이란, $S$의 모든 접미사(suffix) $S[i\dots]$들을 사전 순으로 정렬했을 때의 시작 인덱스 순열을 말한다. 예를 들어, $S = aba$라면 접미사들을 사전 순으로 정렬했을 때 $a koosaga님의 글을 참고하면 좋다.Inverse Problem어떤 순열 $\sigma$가 주어졌을 때, 이를 접미사 배열로 하는 문자열은 몇 개나 존재할까? SA는 $S[\sigma(0)] \le \dots \le S[\sigma(n-1)]$라는 관계를 나타내므로, 우리는 이 등호가 언제 성립하지 않는지만 판별하면 된다...

Problem statement정점 $n$개인 무방향 그래프 $G$가 주어진다. 정점이 $k$개인 path $P_k$와의 cartesian product $G \square P_{k}$의 cartesian product의 스패닝 트리의 개수를 구하여라. $n \le 500$, $k \le 10^{18}$.Matrix-tree theorem그래프 $G$의 Laplacian 을 $L_{G} := D_{G} - A_{G}$로 쓰자. $L_{G}$는 real symmetric matrix이고, positive semidefinite이므로 양의 실수 고윳값을 갖는다. Connected graph $G$에 대해 $L_{G}$는 rank $n-1$이 되는데, non-zero eigenvalue를 $\lambda_{1..

Correlation clustering은 그래프의 정점들을 cluster들로 분할하는데, 각 간선 $e$에는 두 종류의 weight $w_{e}^{+}$와 $w_{e}^{-}$가 있다. 두 endpoint가 같은 cluster에 있으면 $w_{e}^{+}$점, 다른 cluster에 있으면 $w_{e}^{-}$점을 얻는다. 목표는 점수의 합을 최대화하는 clustering을 찾는 것이다. 이 문제는 NP-hard임이 알려져 있고, Max cut처럼 SDP를 이용한 constant factor approximation이 알려져 있다.이번에도 직관적인 $0.5$-approximation이 있는데, 모든 정점을 한 cluster에 놓거나 / 정점을 다 다른 cluster에 두거나 둘 중 나은 것이 최적해의 절..

https://www.acmicpc.net/problem/25510https://infossm.github.io/blog/2022/08/18/CharPoly/Division-Free Determinant에 대해 위 문제를 내고 글도 썼는데, 최근 훨씬 간단한 알고리즘이 있다고 해서 정리해보려고 한다.원본 글에 달린 것과 동일하게 $\mathcal{O}(n^4)$에 동작하는 division-free characteristic polynomial 알고리즘이다.Algorithm$n \times n$ 행렬 $A = (a_{ij})$에 대해, $A_{i}$를 $i\dots n$번째 행, 열만 따와서 만든 크기 $n-i+1$의 정사각행렬이라고 하자. 당연히 $A_{1} = A$이다.$p_{1}(x) = \det(x..

Lindström–Gessel–Viennot lemma는 DAG의 non-intersecting path를 셀 때 사용할 수 있는 공식이다.$G = (V, E)$에서 $2n$개의 정점 $a_{1}, \cdots, a_{n}$, $b_{1}, \cdots, b_{n}$을 생각하자. 어떤 두 path가 intersecting하다는 것은 둘 사이에 공통된 정점이 있다는 것이다. path tuple $P = (P_{1}, \cdots, P_{n})$에 대해 $P_{i}$가 $a_{i}$를 $b_{\sigma(i)}$로 보내고, $\sigma$가 순열이면 이러한 $P$를 path system이라고 하자. $P$가 non-intersecting이면 non-intersecting path system이라고 부르고, ..