問題文 → ■
自分の提出 → ■ （コンテスト外）
公式解説pdf → ■
公式解説pdf 、特に「マトロイドを知っていれば一発」という部分について、マトロイドの基礎を学んだり、他の方の本問題を扱ったブログ等を見ても、なかなかスマートな理解に辿り着けず（「○○を勉強すれば分かる」「○○に証明が載っている」すらなかなか手に入らなかった）。同様の方が居るかもしれませんし、私なりに理解を整理して記述してみます。
解法の概要
主題ではないので、深堀りはしません。
- マス目 $(x,y)$ を、頂点「$x$行」と頂点「$y$列」を結ぶ辺と見立てた2部グラフの問題に書き換える。各頂点から1つずつまで辺を選び、辺の価値の和を最大化する問題に帰着。
- 取れる辺集合の満たすべき条件を考える。連結成分ごとに、（辺の個数）$\leqq$（頂点の個数）が成り立つことが必要十分条件であると分かる。
- グラフ $G = (V,E)$ （$V$ は頂点集合、$E$ は辺集合）に対して、$E$ の部分集合族 $F = \{X\subset E\mid \text{$X$ は (2) を満たす}\}$ を考える。この $F$ はマトロイドであり、したがって今回の最大化問題に貪欲戦略が適用できる。
・ 1. の2部グラフ → これは定跡の1つなので、経験があれば考察 0 でできる範囲かと思います。
・ 2. の辺集合の条件 → 必要性は簡単に出てくる。この必要性を満たすグラフは簡単な構造しかなくて、十分性の考察も難しくない。
3. の部分は 解説PDF ではかなりあっさりと流されているところです。
しかし個人的に、マトロイドの定義や具体例を調べたり（Wikipedia、「Introduction to Algorithms」、競プロブログいくつか）、その上で証明を考えようとしてもなかなかスムーズに行かなかったところです（特に、マトロイド理論のおかげで思考が節約できているようになかなか感じられなかった）。
→ 「貪欲戦略が適用できる」は流石に基礎的な一般論。マトロイドについて調べるとほぼ必ず証明もあります。
→ 「この $F$ はマトロイドであり」がなかなかすっきりと分からず。特に、マトロイド理論のおかげで問題全体の思考を省略できていると感じるようにはなかなかなりませんでした。
→ マトロイドであることを示すときの思考パターンが少し整理できました、同じところで苦戦する方も居ると思うので記事にしておきます。
→ 最終的には、この $M$ 自体も Bicircular matroid、Pseudoforest matroid などと名前がついているマトロイドであることを見つけました。深くマトロイドを勉強していれば、このような例も知っていて、「マトロイドを（この具体例も含めて）知っていれば一発」という気持ちで書かれた解説だったのかなと。
マトロイドの定義・貪欲法との関係
定義
とりあえずWikipediaを大体写経します。有限集合 $E$ と、 $E$ の部分集合族 $F\subset 2^E$ が
・$\emptyset \in F$.
・$X\subset Y\in F \implies X\in F$.
・$X,Y\in F, |X|>|Y| \implies \exists x\in X\setminus Y, Y\cup\{x\} \in F$.
を満たすとき、$(E,F)$ をマトロイドという．
貪欲法
マトロイドにおけるコスト最大化問題は、クラスカル法の要領で解ける。より形式的には
・コスト関数 $c\colon E\longrightarrow \mathbb{R}_{+}$ が与えられていて、$X\in F$ に対してコストの和 $c(X) = \sum_{x\in X} c(x)$ を最大化したいとする。
・$X = \emptyset$ から始める。
・$c(e)$ の大きな $e\in E$ から順に見ていって、「$X\cup\{e\} \in F$ ならば $X$ を $X\cup\{e\}$ に書き換える」ことを繰り返す。
・全ての $e\in E$ に対してこの操作を行った結果として得られる、$X$ が最大化問題に対する解となる。
証明も難しくはないです。証明を追いながらクラスカル法の証明と見比ると、マトロイドが「クラスカル法の証明に必要な要素を抜き出して抽象化した」ようなものだという気持ちに私はなりました。
マトロイドであることの証明
この記事の主題です。上述のマトロイドの定義や性質を学んでも、結局マトロイドであるかどうかの判定や証明ができなければ、具体的な問題への適用は困難です。特に、交換性
・$X,Y\in F, |X|>|Y| \implies \exists x\in X\setminus Y, Y\cup\{x\} \in F$
の証明を毎回1から生み出すという思考法だと、結局苦労が絶えないように思います。
いくつかのマトロイドの交換性の証明を確認しながら、共通の戦略を確認していきます。
ベクトルマトロイド (vector matroid)
グラフよりベクトル空間の方が難しく見える人は、読み飛ばして次の例へ行くと良いかもしれません。
ベクトル空間 $V$ の有限部分集合 $E$ を固定して、$F$ を $E$ の線形独立な部分集合全体とします。マトロイドになること、特に交換性を証明します。
- $E$ の部分集合 $X$ に対し、$X$ が生成する $V$ の部分空間を $\mathrm{span}(X)$ と書き、$r(X) = \mathrm{dim} (\mathrm{span}(X))$ とする。$X\in F\iff |X| = r(X)$ が成り立つ。
- $X,Y\in F, |X|>|Y|$ を仮定する。このとき $r(X) > r(Y)$ である。
- $X\setminus Y = \{x_1,x_2,\ldots,x_n\}$ として、これらの元を $Y$ に1元ずつ追加していくことを考える。つまり、$Y_k = Y\cup\{x_1,\ldots,x_k\}$ とおいて、列 \[Y = Y_0\subset Y_1\subset Y_2\subset \cdots \subset Y_n = X\cup Y\] を考える（注：これらは $F$ に属する保証はない）。$r(Y) < r(X) \leq r(X\cup Y)$ であるから、$r$ が初めて増える瞬間が存在する：ある $k$ に対して $r(Y) = r(Y_{k-1}) < r(Y_{k})$。
- このとき $x_k\notin \mathrm{span}(Y_{k-1}) = \mathrm{span}(Y)$ なので、$Y\cup\{x_k\}\in F$。これで交換性が示された。
閉路マトロイド (cycle matroid)
グラフ $G = (V,E)$ を固定して、$F$ 閉路を含まない辺集合全体とします。マトロイドになること、特に交換性を証明します。
- $E$ の部分集合 $X$ に対し、部分グラフ $(V,X)$ の連結成分の個数を $r(X)$ と書く。
- $X\in F$ のとき、各連結成分は木である。したがって連結成分ごとに、$\text{頂点の個数} = \text{辺の個数} + 1$ が成り立つので、全体として $r(X) = |V| – |X|$ が成り立つ。
- $X,Y\in F, |X|>|Y|$ を仮定する。$|V| = r(X) + |X| = r(Y) + |Y|$ より $r(X) < r(Y)$ である。
- $X\setminus Y = \{x_1,x_2,\ldots,x_n\}$ として、これらの元を $Y$ に1元ずつ追加していくことを考える。つまり、$Y_k = Y\cup\{x_1,\ldots,x_k\}$ とおいて、列 \[Y = Y_0\subset Y_1\subset Y_2\subset \cdots \subset Y_n = X\cup Y\] を考える。$r(Y) > r(X)\geq r(X\cup Y)$ であるから、$r$ が初めて減る瞬間が存在する：ある $k$ に対して$r(Y) = r(Y_{k-1}) > r(Y_{k})$。
- 辺 $x_k$ は、部分グラフ $(V,Y_{k-1})$ における相異なる2連結成分を結ぶ。$Y$ と $Y_{k-1}$ は頂点の連結成分分解には変化がしていない。よって $x_k$ は部分グラフ $(V,Y)$ においても相異なる2連結成分を結ぶので、$Y\cup\{x_k\}\in F$。これで交換性が示された。
今回の問題のマトロイド (Bicircular matroid, Pseudoforest matroid)
グラフ理論の用語をいくつか用います：
・木 (tree)：略。なお、頂点が1つで辺が1つもないグラフも木です。
・擬似木 (pseudo-tree) ：辺の個数と頂点の個数が等しい連結グラフ。競プロ方言で「なもりグラフ」とも呼ぶようです。でも森グラフじゃないです。
・森 (forest)：連結成分ごとに木。
・擬似森 (pseudo-forest)：連結成分ごとに木または擬似木。
グラフ $G = (V,E)$ を固定して、$F = \{X\subset E\mid (V,X) は擬似森\}$ がマトロイドになること、特に交換性を証明します。
- $E$ の部分集合 $X$ に対し、部分グラフ $(V,X)$ における木成分の個数を $r(X)$ と書く。
- $X\in F$ のとき、連結成分ごとに （頂点の個数） $-$ （辺の個数） $\in \{0,1\}$ が成り立つ。この値が $1$ になることと成分が木であることは同値である。よって全体として $r(X) = |V| – |X|$ が成り立つ。
- $X,Y\in F, |X|>|Y|$ を仮定する。$|V| = r(X) + |X| = r(Y) + |Y|$ より $r(X) < r(Y)$ である。
- $X\setminus Y = \{x_1,x_2,\ldots,x_n\}$ として、これらの元を $Y$ に1元ずつ追加していくことを考える。つまり、$Y_k = Y\cup\{x_1,\ldots,x_k\}$ とおいて、列 \[Y = Y_0\subset Y_1\subset Y_2\subset \cdots \subset Y_n = X\cup Y\] を考える。$r(Y) > r(X)\geq r(X\cup Y)$ であるから、$r$ が初めて減る瞬間が存在する：ある $k$ に対して$r(X) = r(Y_{k-1}) > r(Y_{k})$。
- 辺 $x_k$ は、部分グラフ $(V,Y_{k-1})$ において、「同じ木成分の2点」または「異なる木成分の2点」を結ぶ。$Y$ と $Y_{k-1}$ では木成分は変化していない。よって、 $x_k$ は部分グラフ $(V,Y)$ においても「同じ木成分の2点」または「異なる木成分の2点」を結ぶので、$Y\cup\{x_k\}\in F$。これで交換性が示された。
ランク関数による特徴づけ
3つのマトロイドについて、交換性の証明を与えました。証明自体もそっくりです。それぞれ
・生成するベクトル空間の次元
・連結成分の個数
・木成分の個数
に注目すると、ほとんど同様な証明が書けました。また、マトロイドはいずれも「この量が増える方向のみに元を追加することを許容する」ような部分集合です。
このように、マトロイドであることの証明の1つの方針として、「よい量を見つけて観察する」（1点ずつ追加していって～）というパターンがありそうに思います。いきなり「交換性を証明するぞ！」と思うのではなく、マトロイドを表すような「よい量」を見つけようと思うことで、かなり証明までの道筋が見通し良くなったように私には感じられました。
ここでいう「よい量」はマトロイド理論におけるランク関数と言われていおり、マトロイドをランク関数により特徴付けることができます。つまり、「よい量を見つけて観察することによりマトロイド性を証明する」という方針は、理論上は任意のマトロイドに適用できることが分かります。
ランク関数の定義
$E$ を有限集合とする。$r\colon 2^E\longrightarrow \mathbb{Z}_{+}$は、任意の$X,Y\subset E$に対して
- $r(X)\leq |X|$.
- $X\subset Y\implies r(X)\leq r(Y)$.
- $X\subset Y\implies r(X\cup\{x\}) – r(X) \geq r(Y\cup\{x\}) – r(Y)$.
を満たすとき、ランク関数であるといいます。最後の条件は 劣モジュラと呼ばれ、他にも分かりやすい同値な言い換えもあります（ここでは上で行った証明と直接結びつく条件を採用しました）。
なお、上記のマトロイド性の証明に現れた $r$ は、全てランク関数またはその亜種（符号を変えて定数ずらした）です。たとえば閉路マトロイドでは、「連結成分の個数」ではなく、「$|V| – $連結成分の個数」を $r$ と置き直すと、ランク関数となります。
マトロイドとランク関数
次の対応により、有限集合 $E$ 上のマトロイドとランク関数は1対1に対応します。
- $F\subset 2^E$ がマトロイドであるとする。このとき、$r(X) = \max\{|Y|\mid Y\subset X, Y\in F\}$ はランク関数を定める。
- $r\colon 2^E\longrightarrow \mathbb{R}$ がランク関数であるとする。このとき、$F = \{X\in 2^E\mid r(X) = |X|\}$ はマトロイドを定める。
後半のランク関数からマトロイドへの対応は、上記で3度繰り返した証明パターンを真似すれば証明できます。今回の記事では「マトロイド性の証明の手段」を興味の中心としたので、逆の対応は省略します（難しくはないです）。
また、得られたマトロイドの特徴づけ 2種（の主要部）
・交換性を満たす：$\forall X,Y\in F, |X|>|Y|, \exists e\in X\setminus Y,\ldots$
・ランク関数が存在する：$\exists r\colon 2^E\longrightarrow \mathbb{Z}_{+}, \forall X,Y\in E,\ldots$
を見比べると、「$\forall, \exists$」の順序が入れ替わっているところも面白いところだと思います。一般に、$\forall$ の命題よりも $\exists$ の命題の方が、成り立つならば簡潔に証明しやすいことが多いです。1つの実例に焦点を当てて議論すればよいので。この意味でも、マトロイドであることの証明の手段を、交換性の成立からランク関数の存在へと移行することは自然なように感じます。
一方で、ある $F\subset 2^E$ が「マトロイドではない」ことを証明する手段が必要な場合には、ランク関数による特徴づけはむしろ扱いづらくて、「交換性の反例の存在」を示そうとする方が簡潔におさまるのではないかとも想像します。1つの実例に焦点を当てて議論すればよいので。
