1. 概要 Undirected Vertex Geography は，無向グラフ上で駒を動かす $2$ 人ゲームです．各手番では，現在駒がある頂点から隣接する頂点に駒を移動させます．ただし，選べる頂点は，一度も駒が置かれたことがない頂点に限ります．動けなくなったプレイヤの負…

1. 概要 本記事では，Color-Coding という手法について解説します． Color-Coding とは $k$ 個のものを選ぶというような存在判定問題や最適化問題において，それぞれのものにランダムな色を割り当てるという手法です．特に，比較的小さな $k$ について「ちょ…

1. 概要 無向単純グラフに対して，同じ頂点に接続する $2$ 辺が同じ色を持たないように，辺に色を割り当てることを辺彩色（edge coloring）といいます．辺彩色に必要な色数の最小値をそのグラフの辺彩色数（edge-chromatic number，chromatic index）といい…

1. 概要 単純無向グラフにおいて，各頂点の次数を並べてできる列 $d = (\deg(1),\deg(2),\ldots,\deg(n))$ を次数列といいます． 本記事では，$d=(d_1,d_2,\ldots,d_n)$ が単純無向グラフの次数列となるための必要十分条件を与える $\text{Erd\H{o}s--Gallai…

1. 概要 本記事では，オイラーツアーテクニック について解説します． オイラーツアーテクニックは 論文 3 において導入されたテクニックです．これは木の情報を，頂点全体や辺全体を特定の方法で $1$ 列に並べることによって表現するものです．このテクニッ…

1. 概要 本記事では，グラフに関する用語について整理します． グラフ理論は数学分野の中でも，同じ用語が文献によって少し違った意味で使われているといったことが特に多く見られる分野です．本記事ではその中でも標準的と思われる定義を採用し，定義揺れが…

1. 概要 本記事では，根付き木の HLD（重軽分解）について解説します． HLD は根付き木の辺を heavy edge，light edge の $2$ 種に分けて扱うことで，木の頂点全体をいくつかのパスに分解するものです． HLD は，木に対するさまざまな計算に幅広く使えるテク…

1. 概要 根付き木における $2$ 頂点 $u, v$ に対して， $u$ から $v$ へのパスが通る，深さ最小の頂点を $u,v$ の LCA といい， $\mathrm{LCA}(u,v)$ と書きます． LCA の計算については，オイラーツアーテクニック などでも触れました．本記事ではそれより…

1. 概要 任意の相異なる $2$ 頂点 $u,v$ について，$u\to v$ または $v\to u$ のどちらか一方が必ず存在するような単純有向グラフをトーナメントといいます．これは $N$ 人が総当たり戦をしたときの勝敗を，「勝った人から負けた人へ辺を張る」ことで表した…

1. 概要 本記事では，Union-Find の計算量が $\mathrm{O}\left(N+Q\alpha(N)\right)$ であるという事実を証明します． この事実は競技プログラミングユーザーの多くが知っている非常に有名なものだと思いますが，Union-Find の基礎的な動作原理や，計算量 $\…