【月刊組合せ論 Natori】マトロイドに入門しよう【2024 年 7 月号】

月刊組合せ論 Natori は面白そうな組合せ論のトピックを紹介していく企画です。今回は競技プログラミングにも登場するマトロイドに入門していきます。タイトルの「入門しよう」には、筆者と共に入門しようという気持ちが込められています。つまり筆者も素人です。

ベクトル空間 #

ベクトル $\vec{a}=(1,-1,0), \vec{b}=(0,1,-1),\vec{c}=(3,-2,-1),\vec{d}=(1,1,1)$ を考えます。$\vec{c}$ は $\vec{c}=3\vec{a}+\vec{b}$ と表せる一方、$\vec{d}$ は $p\vec{a}+q\vec{b}$ の形で表すことができません。このような関係を表す概念として、線形独立と線形従属があります。

ベクトルの集合 $X=\{\vec{x}_1,\ldots,\vec{x}_n\}$ が線形独立であるとは、$a_1\vec{x}_1+\cdots+a_n\vec{x}_n=\vec{0}$ ならば $a_1=\cdots=a_n=0$ が成り立つことをいいます。そうでないとき $X$ は線形従属であるといいます。例えば $\{\vec{a},\vec{b},\vec{d}\}$ は線形独立ですが、$\{\vec{a},\vec{b},\vec{c}\}$ は $3\vec{a}+\vec{b}-\vec{c}=\vec{0}$ をみたすので線形従属です。

$X$ が線形独立ならば、部分集合 $Y\subset X$ も線形独立です。さらに次の性質が成り立ちます。

証明: もしすべての $x\in X\setminus Y$ について $Y\cup\{x\}$ が線形従属であったとすると、$X$ の元はすべて $Y$ の元の線形結合として表せる。$Y$ を基底とする部分空間の次元は $|Y|$ で、$|X|>|Y|$ であることから $X$ は線形従属となる。これは矛盾である。

グラフ #

グラフは頂点と辺からなるものです。厳密にはグラフ $G$ は頂点集合 $V(G)$ と辺集合 $E(G)$ の組で、$E(G)$ は $V(G)$ の非順序対 $\{x,y\}$ からなります。ここでは $x\ne y$ とします。

グラフ $G$ のサイクルとは、頂点の列 $(v_1,v_2,\ldots,v_n)$ (ただし $n\ge 3$ とする) であって $\{v_1,v_2\},\{v_2,v_3\},\ldots,\{v_{n-1},v_n\},\{v_n,v_1\}$ が辺であるものをいいます。森とは、サイクルをもたない部分グラフのことをいいます。

証明: すべての $e\in E(X)\setminus E(Y)$ について $Y\cup\{e\}$ が森ではないと仮定する。また $V(X)=V(Y)=V(G)$ とする。$r(X)$ を $X$ の連結成分の個数とするとき、$r(X)=|V(X)|-|E(X)|$ より $r(X)<r(Y)$ が成り立つ。一方、$e=\{u,v\}\in E(X)$ に対して、頂点 $u,v$ は $Y$ の同じ連結成分に属する。このことから $r(X)\ge r(Y)$ となる。これは矛盾である。

マトロイド #

マトロイドはベクトル空間とグラフに対する上述の性質を抽象化したものです。

$E$ を有限集合、$\mathcal{I}$ を $E$ の部分集合からなる集合とします。$(E,\mathcal{I})$ がマトロイドであるとは

1. $\emptyset\in \mathcal{I}$
2. $X\in \mathcal{I}, Y\subset X$ ならば $Y\in \mathcal{I}$
3. $X,Y\in \mathcal{I}, |X|>|Y|$ ならばある $x\in X\setminus Y$ について $Y\cup\{x\}\in \mathcal{I}$

をみたすことをいいます。$X\in \mathcal{I}$ であるとき、$X$ は独立であるといいます。

1, 2 をみたす場合、$(E,\mathcal{I})$ は独立性システムであるといいます。

ランク関数 #

マトロイド $(E,\mathcal{I})$ に対してランク関数 $r\colon 2^E\to \mathbb{Z}_+$ を $r(X)=\max\{|Y| \mid Y\subseteq X, Y\in \mathcal{I}\}$ により定めます。すると

• $0\le r(X)\le |X|$
• $Y\subseteq X$ ならば $r(Y)\le r(X)$
• $r(X)+r(Y)\ge r(X\cup Y)+r(X\cap Y)$

が成り立ちます。最初の 2 つは明らかです。三番目の不等式は劣モジュラ性と呼ばれています。

逆を考えることもできます。$E$ は有限集合で関数 $r\colon 2^E\to \mathbb{Z}_+$ は上の 3 つの条件をみたすとします。

$$ \mathcal{I}=\{X\subseteq E\mid r(X)=|X|\} $$

とおくと、$(E,\mathcal{I})$ はマトロイドになります。証明は省略します。

このように、マトロイドはランク関数によって導入することもできます。他にも様々なマトロイドの特徴づけが知られています。次のセクションではアルゴリズムによってマトロイドを特徴づける話を紹介します。

貪欲法 #

「マトロイドは貪欲法」というフレーズを聞いたことがある人もいるかもしれません。実は、貪欲法が上手く動くこととマトロイドであることが同値になります。これを正確に述べます。

$(E,\mathcal{I})$ を独立性システムとします。各 $e \in E$ に対して重み $w(e)\in\mathbb{R} _ {\ge 0}$ が定まっているとします。求めたいものは、極大独立集合 $B$ であって重みの和 $\sum_{e\in B}w(e)$ が最小となるものです。この問題に対して、次のような貪欲法を考えます。

$w(e_1)\le\cdots\le w(e_n)$ となるように $E$ の元に $e_1,\ldots,e_n$ と名前を付けます。まず $B=\emptyset$ とします。$i=1,2,\ldots,n$ の順に次の操作を行います。

• $B\cup\{e_i\}\in\mathcal{I}$ ならば $B$ に $e_i$ を加える。

最終的な $B$ が出力です。

このアルゴリズムは本当に最小コストの極大独立集合を出力するでしょうか？

なお極大独立集合のことは基ともいいます。基の要素数は等しいことが知られており、以下の証明でも用いられます。

まずはマトロイドならば貪欲法が上手く動くことを示します。貪欲法の出力が $B=\{x_1,\ldots,x_r\}$ で、$x_1,\ldots,x_r$ の順に加えられたとします。もちろん $w(x_1)\le\cdots\le w(x_r)$ です。$B^{\prime}=\{y_1,\ldots,y_r\}\in\mathcal{I}$ ($w(y_1)\le\cdots\le w(y_r)$) が最適解であるとします。このとき任意の $i$ に対して $w(x_i)\le w(y_i)$ が成り立つことを示します。そうでないと仮定すると、$w(x_k)>w(y_k)$ となる $k$ が存在します。このような $k$ のうち最小のものをとり、$S=\{x_1,\ldots,x_{k-1}\}, T=\{y_1,\ldots,y_k\}$ を考えます。$|T|=|S|+1$ なので、マトロイドの性質よりある $j \ (1\le j\le r)$ について $S\cup\{y_j\}\in\mathcal{I}$ となります。しかし $w(y_j)\le w(y_k)<w(x_k)$ なので、貪欲法の動かし方と合いません。

次に貪欲法が上手く動くならばマトロイドであることを示します。マトロイドでないとすると、ある独立集合 $A,B$ は $|A|=|B|+1$ をみたすが、任意の $a\in A\setminus B$ について $B\cup\{a\}$ が独立ではありません。重みを

$$ w(x)=\begin{cases} w_1 & x\in A\cap B \\ w_2 & x\in B\setminus A \\ w_3 & x\in A\setminus B \\ w_4 & \text{otherwise} \end{cases} $$

とします。まず $w_1<w_2<w_3<w_4$ とします。貪欲法は、まず $A\cap B$ の元をすべて選び、$B\setminus A$ の元をすべて選びます。仮定より $A\setminus B$ の元は選びません。$B$ は極大独立集合でないので、$X\setminus (A\cup B)$ から選ばれます。$m$ を極大独立集合の要素数としたとき、コストは

$$ |A\cap B|w_1+|B\setminus A|w_2+(m-|B|)w_4 $$

となります。これが最適でないことを示したいので、$A,B$ の役割を変えて得られるコスト

$$ |A\cap B|w_1+|A\setminus B|w_3+(m-|A|)w_4 $$

の方が小さいようにしたいです。この不等式は

$$ w_4>|A\setminus B|w_3-|B\setminus A|w_2 $$

と変形できます。これが成り立つように $w_1,w_2,w_3,w_4$ を具体的に定めることができますが、これは読者の演習問題とします。

また、最小を最大に置き換えても類似の定理が成り立ちます。

競技プログラミングにおける具体例 #

競技プログラミングにおいてマトロイドが現れる例をいくつか紹介します。

代表的な例は最小全域木です。マトロイドはグラフの一般化だったことを思い出すと、サイクルのないグラフのうち辺の数が極大なものが基 (極大独立集合) です。グラフが連結であるとすると、基は全域木です。するとマトロイドに対する貪欲法を用いることで最小全域木が求められます。このアルゴリズムにはクラスカル法という名前がついています。

他にも、 AtCoder Beginner Contest 236 F - Spices がマトロイドの考え方で解けます。その他のマトロイドが現れる問題はぜひ詳しい人に聞いてみてください。

競技プログラミングとマトロイドに関する記事は色々あります。いくつかピックアップして紹介します。

• 競技プログラミングとマトロイド
• クリスマスですし、罰金付きスケジューリング問題でマトロイドと貪欲法の基本に入門します！
• マトロイドのお勉強（JSC2019予選 [E] Card Collector）

おわりに #

マトロイドの基礎を紹介しました。筆者も素人なので、詳しい人からのコメントをお待ちしております。

高度な話題も、勉強が進めば記事にしたいと思っています。

今後も月刊組合せ論 Natori では組合せ論の様々な話題をお届けする予定なので、応援のほどよろしくお願いいたします。

参考文献 #

• Pitsoulis, Leonidas S. Topics in matroid theory. SpringerBriefs in Optimization. Springer. (2014).
• When Greedy Algorithms are Perfect: the Matroid