マトロイドの独立集合・基・階数

線形マトロイド・グラフ的マトロイド・一様マトロイドについて、部分集合が独立かを判定し、階数関数 $r (X)$ と基を求められる（グラフ的マトロイドの階数は $∣ V ∣ - (連結成分の数)$ ）

前提

行列の階数と解の存在（大学数学線形代数）
最小全域木（クラスカル法・プリム法）（大学数学グラフ理論）

この技能までの道筋（35 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
乗法公式による展開（中学数学数と式）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
行列の階数と解の存在（大学数学線形代数）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
グラフの次数と握手補題（大学数学グラフ理論）
最小全域木（クラスカル法・プリム法）（大学数学グラフ理論）

説明

マトロイドは「独立」という性質を抽象化した構造で、ベクトルの一次独立とグラフの「閉路を含まない辺集合」を同じ言葉で扱えるようにします。この技能を身につけると、線形マトロイド・グラフ的マトロイド・一様マトロイドについて、与えられた部分集合が独立かどうかを判定し、部分集合 $X$ の階数 $r (X)$ と基を具体的に求められるようになります。貪欲法がなぜ最適解を与えるかを理解するときや、組合せ最適化の問題を整理するときの基本的な道具になります。

なぜそうしてよいのか

有限集合 $E$ と、 $E$ の部分集合の族 $I$ の組 $M = (E, I)$ が次の 3 条件を満たすとき、 $M$ をマトロイドといい、 $I$ の元を独立集合、独立でない部分集合を従属集合といいます。(I1) $\emptyset \in I$ 。(I2) $A \in I$ かつ $B \subseteq A$ なら $B \in I$ 。(I3)（交換公理） $A, B \in I$ かつ $∣ A ∣ < ∣ B ∣$ なら、ある $e \in B ∖ A$ があって $A \cup {e} \in I$ 。極大な独立集合を基といい、 $X \subseteq E$ に含まれる独立集合の最大の大きさを $X$ の階数 $r (X)$ といいます。(I3) から、 $X$ に含まれる極大な独立集合はどれも同じ大きさをもちます（大きさが違えば小さい方に大きい方から (I3) で元を足せて、極大性に反するため）。したがって、 $X$ の中で「独立を保つ限り元を 1 つずつ足していく」だけで、どの順に足しても大きさ $r (X)$ の極大独立集合に到達します。特に基はすべて同じ大きさ $r (E)$ です。

代表的な例を見ます。線形マトロイド：行列 $A_{0}$ の列（の番号）の集合を $E$ とし、列ベクトルが一次独立な列の集合を独立とします。(I1)(I2) は明らかです。(I3) は次のように確かめられます。独立な $A, B$ （ $∣ A ∣ < ∣ B ∣$ ）について、すべての $e \in B ∖ A$ で $A \cup {e}$ が従属だったとします。 $A$ は一次独立なので、これは $e$ のベクトルが $A$ のベクトルの一次結合で書けることを意味します。 $B \cap A$ の元も当然 $A$ の一次結合なので、 $B$ のベクトルはすべて $A$ のベクトルの一次結合で書け、 $B$ のベクトルを並べた行列の階数は $∣ A ∣$ 以下になります。これは $B$ が一次独立で階数 $∣ B ∣ > ∣ A ∣$ であることに矛盾します。このとき $r (X)$ は $X$ の列だけを並べた行列の階数です。一様マトロイド $U_{k, n}$ （ $0 \leq k \leq n$ とする）： $∣ E ∣ = n$ で、大きさ $k$ 以下の部分集合をすべて独立とします。したがって $r (X) = min (∣ X ∣, k)$ で、基は大きさ $k$ の部分集合全体です（ $k > n$ を許すと基は $E$ 自身だけになり、大きさ $k$ の部分集合は存在しないので、 $k \leq n$ と約束しておきます）。

グラフ的マトロイド：グラフ $G = (V, E)$ の辺集合 $E$ について、閉路を含まない辺集合（森）を独立とします（自己ループは長さ 1 の閉路とみなすので、それ自身で従属です）。辺集合 $X$ について、全頂点 $V$ と辺 $X$ からなるグラフ $(V, X)$ の連結成分を $C_{1}, \dots, C_{c}$ （孤立点も 1 つの成分と数える）とし、 $C_{i}$ の頂点数を $n_{i}$ とします。 $X$ に含まれる極大な森 $F$ は、各成分 $C_{i}$ の中で全域木になっています。実際、 $F$ がある成分 $C_{i}$ を全域していなければ（ $F$ の $C_{i}$ の部分が 2 つ以上の木に分かれていれば）、 $C_{i}$ は $X$ の辺で連結なので、その別々の木を結ぶ $X$ の辺があり、それを $F$ に足しても閉路ができず、 $F$ の極大性に反します。木の辺数は頂点数より 1 少ないので、 $F$ の辺数は $\sum_{i} (n_{i} - 1) = ∣ V ∣ - c$ です。よって $r (X) = ∣ V ∣ - c (V, X)$ となり、連結グラフでは基がちょうど全域木、 $r (E) = ∣ V ∣ - 1$ です。

手順

どのマトロイドかを確認し、独立の意味を決める：線形なら「列ベクトルが一次独立」、グラフ的なら「閉路を含まない（森）」、一様 $U_{k, n}$ （ $k \leq n$ ）なら「大きさが $k$ 以下」。
独立判定をする：線形なら $X$ の列を並べた行列の階数が $∣ X ∣$ に等しいか調べる。グラフ的なら $X$ の辺に閉路があるか調べる（ $∣ X ∣ = ∣ V ∣ - c (V, X)$ が成り立てば独立）。一様なら $∣ X ∣ \leq k$ か調べる。
階数 $r (X)$ を求める：線形なら $r (X) = rank (A_{X})$ （ $A_{X}$ は $X$ の列だけの行列）。グラフ的なら頂点集合を $V$ 全体のまま辺を $X$ だけにしたグラフの連結成分の数 $c$ を数えて $r (X) = ∣ V ∣ - c$ 。一様なら $r (X) = min (∣ X ∣, k)$ 。
基（または $X$ の中の極大独立集合）を求めるときは、 $X$ の元を順に見て、今までに選んだものと合わせても独立なら選び、従属になるなら捨てる。最後に選んだ個数が $r (X)$ に一致することを確かめる。

例題

頂点集合 $V = {1, 2, 3, 4, 5}$ をもつグラフ $G$ の辺を $e_{1} = {1, 2}$ , $e_{2} = {2, 3}$ , $e_{3} = {1, 3}$ , $e_{4} = {3, 4}$ , $e_{5} = {4, 5}$ とする。 $G$ のグラフ的マトロイド（閉路を含まない辺集合を独立とする）において、 $X = {e_{1}, e_{2}, e_{3}, e_{5}}$ の階数 $r (X)$ を求めよ。

例題の解答

手順 1：グラフ的マトロイドなので、独立とは「閉路を含まない」ことである。

手順 2： $X$ は $e_{1}, e_{2}, e_{3}$ が三角形 $1 - 2 - 3 - 1$ をなすので閉路を含み、独立ではない。よって $r (X) < ∣ X ∣ = 4$ である。

手順 3：頂点は $V$ の 5 個すべてを残し、辺を $X$ だけにしたグラフ $(V, X)$ の連結成分を数える。 $e_{1}, e_{2}, e_{3}$ により ${1, 2, 3}$ が 1 つの成分、 $e_{5}$ により ${4, 5}$ が 1 つの成分になる（辺 $e_{4}$ は $X$ に入っていないので、この 2 つはつながらない）。連結成分の数は $c = 2$ で、 $r (X) = ∣ V ∣ - c = 5 - 2 = 3$ 。

手順 4（確認）： $e_{1}, e_{2}, e_{3}, e_{5}$ の順に見ると、 $e_{1}$ を選び、 $e_{2}$ を選び、 $e_{3}$ は $e_{1}, e_{2}$ と閉路を作るので捨て、 $e_{5}$ を選ぶ。 ${e_{1}, e_{2}, e_{5}}$ は閉路を含まない 3 本の辺で、 $X$ の中の極大な独立集合になっており、大きさ 3 が $r (X)$ と一致する。

したがって $r (X) = 3$ 。

答え: $3$

よくある誤り

階数を $r (X) = ∣ X ∣$ としてしまう誤り。正しくは $X$ が従属なら $r (X) < ∣ X ∣$ で、上の例では $∣ X ∣ = 4$ だが三角形 $e_{1}, e_{2}, e_{3}$ のうち 1 本が余分なので $r (X) = 3$ 。
グラフ的マトロイドで、 $X$ の辺が触れている頂点だけで連結成分を数え、それを全頂点数 $∣ V ∣$ から引いてしまう誤り。例えば $V = {1, 2, 3, 4}$ , $X = {{1, 2}}$ で成分を ${1, 2}$ の 1 個と数えると $4 - 1 = 3$ になってしまう。正しくは孤立点 $3, 4$ も成分に数えて $c = 3$ 、 $r (X) = 4 - 3 = 1$ （触れている頂点だけを使うなら $2 - 1 = 1$ のように頂点数もそろえる）。
一様マトロイド $U_{k, n}$ で、どんな $X$ に対しても $r (X) = k$ としてしまう誤り。正しくは $r (X) = min (∣ X ∣, k)$ で、例えば $U_{3, 5}$ で $∣ X ∣ = 2$ なら $r (X) = 2$ 。
線形マトロイドで、どの 2 本の列も平行でないことから列の集合全体が独立だと判断してしまう誤り。例えば $(10), (01), (11)$ はどの 2 本も一次独立だが、3 本を並べた行列の階数は 2 なので 3 本は従属で、 $r = 2$ 。正しくは独立判定を必ず $X$ 全体の列を並べた行列の階数で行う。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
頂点集合を $V = {1, 2, 3, 4, 5, 6}$ とし、辺集合 $E = {e_{1}, e_{2}, e_{3}, e_{4}, e_{5}, e_{6}}$ を
$e_{1} = {1, 2}, e_{2} = {2, 3}, e_{3} = {1, 3}, e_{4} = {4, 5}, e_{5} = {5, 6}, e_{6} = {3, 4}$
とするグラフ $G = (V, E)$ を考える。 $M (G)$ を $E$ 上のグラフ的マトロイド（辺の部分集合が独立であるとは、それが閉路を含まないこととする）とし、 $r$ をその階数関数とする。 $X = {e_{1}, e_{2}, e_{3}, e_{4}, e_{5}}$ に対して $r (X)$ を求めよ。

この技能を使う問題

この技能の次に学べること

貪欲法による最大重み基（大学院数学凸最適化・組合せ最適化）