Katu math

数学やアルゴリズムなど

マトロイドの例と構成法

マトロイドの定義周りについて簡単に触れた後，マトロイドの例と，既存のマトロイドから新たなマトロイドを作る方法を見ていきます．各主張の証明は載せていませんが，末尾の参考文献にそのうちの多くが書かれているので，気になる方は参照してみてください．

準備

$\mathbb{Z}_{+}, \mathbb{R}_{+}$ を，それぞれ非負整数全体の集合，非負実数全体の集合とします．

有限集合 $E$ と $E$ の部分集合族 $ \mathcal{F} \subset 2^{E} $ の組 $ \mathcal{M} = (E, \mathcal{F})$ であって，次の条件を満たすものをマトロイドと呼びます．

  1. $\emptyset \in \mathcal{F}$
  2. $X \subset Y , Y\in \mathcal{F}$ なら $X \in \mathcal{F}$
  3. $|X| < |Y|, X \in \mathcal{F}, Y \in \mathcal{F}$ なら，ある $y \in Y\backslash X$が 存在して，$X \cup \{ y \} \in \mathcal{F}$ を満たす

$ \mathcal{F}$ の元を独立集合と呼び，独立集合でない $2^{E}$ の元を従属集合と呼びます．

マトロイドの極大な独立集合を基と呼び，極小な従属集合をサーキットと呼びます．

基とサーキットの性質として，次のようなものが知られています．

基の性質
マトロイド $(E,\mathcal{F})$ の基全体からなる集合を $\mathcal{B}$ とすると，次が成立する．
  • $\mathcal{B} \neq \emptyset$
  • 任意の $B_{1}, B_{2} \in \mathcal{B}$ と任意の $x \in B_{1} \backslash B_{2}$ に対して， $y \in B_{2} \backslash B_{1}$ であって， $(B_{1} \backslash \{ x\} ) \cup \{ y\} \in \mathcal{B}$ を満たすものが存在する．
  • 任意の $B_{1}, B_{2} \in \mathcal{B}$ と任意の $y \in B_{2} \backslash B_{1}$ に対して， $x \in B_{1} \backslash B_{2}$ であって， $(B_{1} \backslash \{ x\} ) \cup \{ y\} \in \mathcal{B}$ を満たすものが存在する．
サーキットの性質
マトロイド $(E,\mathcal{F})$ のサーキット全体からなる集合を $\mathcal{C}$ とおくと，次が成立する．
  • $\mathcal{C} \notin \emptyset $
  • 任意の $C_{1}, C_{2} \in \mathcal{C}$ に対して， $C_{1} \subset C_{2}$ ならば $C_{1} = C_{2}$ である．
  • 任意の $X \in \mathcal{F}$ と 任意の $e\in E$ に対して， $X\cup \{e\}$ に含まれるサーキットは高々1個である．

マトロイド $\mathcal{M} = (E, \mathcal{F})$ に対して，関数 $r: 2^{E} \to \mathbb{Z}_{+}$ であって，任意の $X \in 2^{E}$ に対して $$ r(X) = Xに含まれる独立集合の元数の最大値$$ を満たすものを，$\mathcal{M}$ のランク関数といいます．

ランク関数の性質として，次のようなものが知られています．

ランク関数の性質
マトロイド $(E,\mathcal{F})$ のランク関数を $r$ とすると，任意の集合 $X,Y \subset E$ と $x,y\in E$ に対して次が成立する．
  • $ r(X) \leq |X|$
  • $ X \subset Y$ なら $r(X)\leq r(Y)$
  • $ r(X\cup Y) + r(X \cap Y) \leq r(X) + r(Y) $

特に，3番目の不等式は，マトロイドのランク関数が劣モジュラーであるという重要な性質を表しています．

ここまで，基・サーキット・ランク関数が満たす性質を記しましたが，逆にこれらの性質を満たす集合族や関数からマトロイドを作ることもでき，かつそのようなマトロイドは一意に定まります．例えば，前述した3つの性質を満たす $E$ の部分集合族 $\mathcal{B}$ をとると，$\mathcal{B}$ を基の集合とするマトロイドが一意に定まり，それは $\mathcal{B}$ のある元の部分集合全体を独立集合とするマトロイドです．サーキットやランク関数についても同様です．

最後に，マトロイドに関する次の問題を考えます．

最大重み独立集合問題
マトロイド $(E, \mathcal{F} )$ と重み関数 $c: E \to \mathbb{R}_{+}$ が与えられた時，集合 $F\in \mathcal{F}$ であって $$ \sum_{e\in F} c(e) $$ の値が最大であるようなものを求める
最小重み基問題
マトロイド $(E, \mathcal{F} )$ と重み関数 $c: E \to \mathbb{R}_{+}$ が与えられた時，マトロイドの基 $B$ であって $$ \sum_{e\in B} c(e) $$ の値が最小であるようなものを求める

マトロイド上では，これらの問題はどちらも貪欲的に解くことができます．つまり，最初は空集合を保持し，$E$ の要素を重みの降順(最小重み基問題の場合は昇順)に見ていき，その要素を加えても集合が独立であるならば集合に要素を加えることを繰り返すことで，最適解である独立集合を得ることができます．

マトロイドの例

一様マトロイド

$E$ を $n$ 元集合として，$k$ を $0\leq k \leq n$ を満たす整数とします．$ \mathcal{F} $ を，$E$ の部分集合のうち元数が $k$ 以下であるもの全体からなる集合とすると， $U_{n}^{k} = (E, \mathcal{F} )$ はマトロイドをなします．これを一様マトロイドと呼びます．特に， $k = n$ のとき，$E$ の全ての部分集合が独立集合になり， $U_{n}^{n}$ を自由マトロイドと呼びます．

行列マトロイド

$ M $ を体 $F$ 上の $m \times n$ 行列 として，$E = \{1,2,\ldots, n \}$ とします．$\mathcal{F}$ を，$E$ の部分集合であって，対応する $ M $ の列ベクトルが一次独立であるもの全体からなる集合とすると， $(E,\mathcal{F})$ はマトロイドをなし，これを行列マトロイドといいます．

特に，任意の体 $F$ 上の行列マトロイドとして表せるマトロイドを正則マトロイドといいます．

  • 独立集合の判定は，選んだ列ベクトルからなる行列に対して掃き出し法を適用して列フルランクであるかを確認することで行えます．

  • $ M $ が行フルランクであるとき，マトロイドの基は列ベクトルのなす基底に対応しています．

  • ちなみに，matroidという名称は行列 (matrix) に由来しています．

グラフマトロイド

$G = (V,E)$ を無向グラフとして，$\mathcal{F}$ を，$E$ の部分集合のうち閉路を持たないもの全体からなる集合とすると， $(E, \mathcal{F})$ はマトロイドをなし，これをグラフマトロイドといいます．

  • $G$ が連結である時， グラフマトロイドの基は木です．連結でないなら，グラフマトロイドの基は全域森です．

  • グラフマトロイドのサーキットは単純閉路です．

  • $G$ が連結である時，最小重み基問題は $G$ の最小全域木を求める問題になり，クラスカル法はこれに対する貪欲アルゴリズムです．

  • グラフの接続行列を考えることで，グラフマトロイドは $\mathbb{F}_{2}$ 上の行列マトロイドであることが分かります．さらに，グラフマトロイドは正則マトロイドでもあることが知られています．

bicircularマトロイド

$G = (V,E) $ を無向グラフとして，$\mathcal{F}$ を，$E$の部分集合のうち，その集合のなすどの連結成分も閉路を高々1つしか持たないもの全体からなる集合とすると，$(E, \mathcal{F})$ はマトロイドをなし，これをbicircular マトロイドと呼びます．

gammoid

$G = (V,E) $ を有向(無向)グラフとして， $S, T$ をそれぞれ $V$ の空でない部分集合とします． $\mathcal{F}$ を， $T$ の部分集合 $F$ であって次の条件を満たすもの全体からなる集合とします．

$S$ の各点から $F$ の点への $|F|$ 個のパスであって，どの二つも点素であるものが存在する

このとき， $(E,\mathcal{F})$ はマトロイドをなし，これをgammoidといいます．$T = V$ であるときは，特にstrict gammoidと呼びます．

  • $G$ が無向グラフのとき，「点素である」という条件を「辺素である」としてもマトロイドになります．

横断マトロイド

$G = (V_{1} \cup V_{2} , E)$ を二部グラフとします． $\mathcal{F}$ を，$V_{1}$ の部分集合であって，それに含まれる点を全て含む $G$ のマッチングが存在するようなもの全体からなる集合とすると， $(E,\mathcal{F})$ はマトロイドをなし，これを横断マトロイドと呼びます．

  • マッチングの端点集合を集めたものなので，マッチングマトロイドと呼ぶこともあります．

分割マトロイド

$E = \{1,2,\ldots, n \}$ として， $E_{1},\ldots, E_{m}$ を $E$ の分割とします(つまり，1以上 $n$ 以下の整数はそれぞれ $E_{1},\ldots, E_{m}$ のうちちょうど一つに含まれます) ．また，$ r_{1},\ldots, r_{m}$ を整数とします．$\mathcal{F}$ を，$E$ の部分集合 $F$ であって，各 $i$ に対して $$ |F \cap E_{i}| \leq r_{i} $$ を満たすようなもの全体からなる集合とします．このとき，$(E,\mathcal{F})$ はマトロイドをなし，これを分割マトロイドと呼びます．

カタランマトロイド

$E = \{1,2, \ldots, 2n \}$ として，$\mathcal{F}$ を，$E$ の部分集合 $F$ であって，次の条件を満たすようなもの全体からなる集合とします．

$1$ 以上 $2n$ 以下の任意の整数 $i$ に対して，$i$ 以下の $F$ の元の個数は， $i$ 以下の $E\backslash F$ の元の個数以下である．

このとき， $(E,\mathcal{F})$ はマトロイドをなし，これをカタランマトロイドと呼びます．

  • カタランマトロイドの独立集合は，ある括弧列の左端を含む連続部分列に対応しています． ($F$ の元を ')' に，それ以外の元を '(' に対応させます)

  • カタランマトロイドの基は長さ $2n$ の括弧列に対応しています

  • 商品の単位量ごとの購入と売買，対角線を跨がないグリッド上の経路など，二つの選択のうち一方は他方より多く行えないような構造に適用できます．

ラミナーマトロイド

有限集合 $E$ に対して，集合族 $\mathcal{L} \in 2^{E}$ が次の条件を満たす時，$(E, \mathcal{L})$ はラミナーと呼びます．

任意の二つの集合 $X,Y \in \mathcal{L}$ に対して， $X \backslash Y, Y \backslash X, X \cap Y$ のうちいずれかは空集合である

ラミナー$(E,\mathcal{L})$ と関数 $u : \mathcal{L} \to \mathbb{Z}_{+}$ に対して， $$ \mathcal{F} = \{ F \subset E : すべての L \in \mathcal{L} に対して |F \cap L| \leq u(L) \}$$ と定めると， $(E,\mathcal{F})$ はマトロイドをなし，これをラミナーマトロイドと呼びます．

  • 例えば，根付き木 $G = (V,E)$ の頂点 $v$ に対して，$v$ を根とする部分木の頂点集合を $F(v)$ とすると，$(E, \{ F(v) : v \in V \} )$ はラミナーであり，「各部分木 $T(v)$ との共通部分のサイズが $u(T(v))$ 以下」という条件を満たす $V$ の部分集合全体がラミナーマトロイドをなします．

マトロイドの構成法

マトロイドが与えられた時，それらから新たなマトロイドを作る方法が色々と知られています．

要素数の限定

マトロイド $(E, \mathcal{F})$ と非負整数 $k$ に対して，独立集合の要素数を $k$ 以下に限定して $$ \mathcal{F_{k}} = \{ F \in \mathcal{F} \mid | F | \ \leq k \} $$ と定めると， $(E, \mathcal{F_{k}} ) $ はマトロイドをなします．

制限・縮約

マトロイド $\mathcal{M} = (E, \mathcal{F})$ と $E$ の部分集合 $X$ に対して，独立集合を $X$ に含まれるものに制限して $$ \mathcal{F}|X = \{ F \in \mathcal{F} : F \subset X \} $$ と定めると，$\mathcal{M}|X = (E, \mathcal{F}|X ) $ はマトロイドをなします．これを，マトロイドの $X$ による制限と呼びます．

マトロイド $\mathcal{M} = (E, \mathcal{F})$ と $E$ の独立集合 $S$ に対して， $$ \mathcal{F}\backslash S = \{ F \in E \backslash S : F \cup S \in \mathcal{F} \} $$ と定めると，$\mathcal{M}\backslash S = (E\backslash S, \mathcal{F}\backslash S ) $ はマトロイドをなします．これを，マトロイドの $X$ による縮約と呼びます．

  • マトロイドの制限・縮約は，グラフマトロイドにおいてグラフの辺の開放除去(単純に辺を除去する)・短絡除去(除去する辺の連結部分に含まれる点を1点につぶす)に対応したものになっています．

  • マトロイドの制限と縮約を繰り返して得られるマトロイドを $\mathcal{M}$ のマイナーと呼び，グラフのマイナーのように，どのようなマイナーを持つかでそのマトロイドを特徴付けることができます(例えば，マトロイドが $\mathcal{F}_{2}$ 上の 行列マトロイドであることは，そのマトロイドが一様マトロイド $U_{4}^{2}$ をマイナーに持たないことと同値であることが 知られています*1 )．

双対

マトロイド $\mathcal{M} = (E, \mathcal{F})$ の基全体からなる集合を $\mathcal{B}$ とします．$\mathcal{F}^{\star}$ を， $$ \mathcal{F}^{\star} = \{ F \subset E : F \cap B = \emptyset を満たす B \in \mathcal{B} が存在する \}$$ と定めると，$(E,\mathcal{F}^{\star})$ はマトロイドをなし，これを $(E,\mathcal{F})$ の双対といいます．

別の言い方をすると，マトロイドの双対とは，元のマトロイドの基の補集合を基とするようなマトロイドのことです．よって，2回双対をとると元のマトロイドに戻ります．

  • マトロイドのランク関数を $r$ ，その双対マトロイドのランク関数を $r^{\star}$ とすると，$F \subset E$ に対して $$ r^{\star}(F) = |F| + r(E\backslash F) - r(E) $$ を満たします．よって，元のマトロイドにおいてランクを求められるなら，双対マトロイドでのランクは容易に得られます．
  • 行列マトロイドの双対は行列マトロイドです．
  • 平面グラフ $G$ の双対グラフがなすグラフマトロイドは， $G$ がなすグラフマトロイドの双対と同型です．
  • $G$ が平面グラフでないなら，一般には $G$ のなすグラフマトロイドの双対をとってもグラフマトロイドにはなりません．
  • strict gammoidは横断マトロイドの双対として表せます．*2

直和・合併

二つのマトロイド $(E_{1},\mathcal{F}_{1}), (E_{2},\mathcal{F}_{2})$ であって， $ E_{1} \cap E_{2} = \emptyset $ を満たすものが与えられた時， $$ \mathcal{F}_{1,2} = \{ F_{1}\cup F_{2} : F_{1} \in \mathcal{F}_{1}, F_{2} \in \mathcal{F}_{2} \} $$ と定めると，$(E_{1} \cup E_{2} , \mathcal{F}_{1,2})$ はマトロイドをなし，これをマトロイドの直和と呼びます．

また，二つのマトロイド $(E,\mathcal{F}_{1}), (E,\mathcal{F}_{2})$ に対して， $$ \mathcal{F}_{1,2} = \{ F_{1} \cup F_{2} : F_{1} \in \mathcal{F}_{1}, F_{2} \in \mathcal{F}_{2} \} $$ と定めると，$(E, \mathcal{F}_{1,2})$ はマトロイドをなし，これをマトロイドの合併と呼びます．

  • 分割マトロイドは，いくつかの一様マトロイドの直和として表せます．

独立集合の和集合をとったものはマトロイドになりますが，共通部分集合をとったものは一般にはマトロイドになりません(これをマトロイドの交叉と呼びます)．しかし，最大二部マッチングをはじめ多くの問題がマトロイドの交叉として定式化でき，また，2つのマトロイドの交叉に含まれる独立集合のうち最大重みのものを多項式時間で求めることができます．

マトロイドの最大独立集合を考えるように，与えられたマトロイドの合併に含まれる元数最大の集合を考えることがあります．これはマトロイドの交叉に帰着させることで，多項式時間で得ることができます．これを用いると，例えばグラフから辺素な全域木をいくつとれるかといった問題を扱うことができます．

マトロイド分割問題
$n$ 個のマトロイド $(E, \mathcal{F}_{1}), \ldots, (E,\mathcal{F}_{n})$ が与えられた時， $F_{i} \in \mathcal{F}_{i}$ を用いて $ X = F_{1} \cup \ldots \cup F_{n} $ と表せる $X \in E$ のうち元数最大のものを求める

二部グラフのマッチングによる構成

マトロイド $(E_{1}, \mathcal{F}_{1})$ ，有限集合 $E_{2}$ と，二部グラフ $G = (E_{1} \cup E_{2} , M)$ に対して， $\mathcal{F}_{2}$を次のように定めます． $$ \mathcal{F}_{2} = \{ F_{2} : F_{1} \in \mathcal{F}_{1} であって，F_{1} と F_{2} の間に完全マッチングが存在する \} $$ このとき，$(E_{2} , \mathcal{F}_{2})$ はマトロイドをなします．

  • 横断マトロイドは，$(E_{1}, \mathcal{F}_{1})$ が自由マトロイドのときに構成されるマトロイドです．

関数による構成

マトロイド $(E_{1}, \mathcal{F}_{1})$ と有限集合 $E_{2}$，関数 $f: E_{1} \to E_{2}$ に対して， $$\mathcal{F}_{2} = \{ f(F_{1}) : F_{1} \in \mathcal{F}_{1} \} $$ と定めると，$ (E_{2}, \mathcal{F}_{2}) $ はマトロイドをなします．

  • $e$ から $f(e)$ に辺を張った二部グラフを考えると，二部グラフのマッチングによる構成の特殊ケースであることがわかります．
  • どんな関数でもマトロイド性を保存するところが面白いです．

競プロでの出題例

マトロイドの最大重み独立集合問題または最小重み基問題に帰着されるものが多いです．貪欲で解けるタイプの問題は，正しい貪欲の方法を見つけたりその正当性を証明したりするのが難しいことも多いですが，マトロイド上の最適化問題として定式化できればそれ以降は機械的に解くことができて嬉しいです．

  • yukicoder No.2957

    略解 $X_{i} < Y_{i}$ であるような $i$ に対応するカードは，最初から $C_{i}$ 枚目までに使うとダメージが増えます．各カードと，それまでに使ったカードの枚数を頂点とする二部グラフを考え，各カード $i$ に対して，今まで使ったカードの枚数 ${0,1,\ldots, C_{i}-1}$ を対応させることで，横断マトロイドの最大重み問題に帰着できます．貪欲法を適用する際，カードは $Y_{i}-X_{i}$ の値が大きい順に見ていきます．対応する枚数の集合がどれも $\{0,1,\ldots, C_{i}-1 \}$ の形をしているので，独立性判定の際には，選んだ $i$ のうち $C_{i}$ が小さい方から順にカードを使うことで条件を満たすかを確かめるとよく，これはUnion-Findなどのデータ構造を用いることで高速に判定することができます．$X_{i} \geq Y_{i}$ の場合も同様で，$X_{i} < Y_{i}$ の場合と独立に考えることができます．

  • ABC236 F

    略解 $1$ 以上 $2^{N}-1$ 以下の任意の整数の辛さのカレーが作れることは，選んだ値を2進表記により長さ $N$ のベクトルに対応させたとき，そのうち$\mathbb{F}_{2}$ 上一次独立な $N$ 個のベクトルを選ぶことができることと同値です．そのような選び方は行列マトロイドの基に一対一対応しているので，行列マトロイドの最小重み基問題に帰着できます．独立性判定の際には，選んだベクトルがなす行列のランクを掃き出し法などを用いて計算して，列フルランクであるか確かめるとよいです．

  • ABC250 G

    略解 常に「買った株数」> 「売った株数」である必要があることから，買い方を括弧列に対応させられそうな感じがしてきます．株を買う日と何もしない日を区別するために，株を買う日・何もしない日・株を売る日のそれぞれに ( (, ( ), ) ) を割り当てると，実現可能な買い方の集合とカタランマトロイドの独立集合が1対1に対応することが分かります．よって，カタランマトロイドの最大重み独立集合問題に帰着できます．

  • 2019最強コン予選 E

    略解 各行と各列に対応する頂点を考え，各カードに対して，そのカードが存在する行と列に対応した頂点を繋ぐ辺を引いた二部グラフを考えると，選べるカードの集合は二部グラフ上で各連結成分が閉路を高々1個持つような辺の選び方の集合と1対1に対応することが分かります．よって，bicircular matroid の最大重み独立集合問題に帰着できます． ( *3に詳しいです)

  • ICPC2023Asia J

    略解 ラミナーマトロイドの最小重み基問題に帰着して解くことができます ( *4 に詳しいです)

参考文献

*1:https://www.ieice-hbkb.org/files/12/12gun_02hen_05.pdf

*2:https://www.sciencedirect.com/science/article/pii/0095895673900312

*3:https://maspypy.com/atcoder-jsc2019%E4%BA%88%E9%81%B8-e-card-collector-%EF%BC%88%E3%83%9E%E3%83%88%E3%83%AD%E3%82%A4%E3%83%89%EF%BC%89

*4:https://tokusakurai.hatenadiary.jp/entry/2024/01/14/012042#f-85b9f14a