コミットグラフと祖先関係

リポジトリのコミット全体を頂点集合 $C$、各コミットからその親コミットへの辺の全体を $E$ とする有向グラフ $G = (C, E)$ をコミットグラフという。$G$ は有限 DAG である（定理 3.3 の証明冒頭と同じ議論による）。

$a, b \in C$ に対し、$b$ から $a$ への有向路（長さ $0$ を含む）が存在するとき $a \preceq b$ と書き、$a$ は $b$ の祖先であるという。$a \preceq b$ かつ $a \neq b$ のときは $a \prec b$ と書く。

$c \preceq a$ かつ $c \preceq b$ を満たす $c$ を $a, b$ の共通祖先といい、その全体を $\mathrm{CA}(a,b)$ と書く。$\mathrm{CA}(a,b)$ の $\preceq$ に関する極大元を $a, b$ のマージベースという。