貪欲法による最大重み基

重みの大きい順に独立性を保つ要素を加える貪欲法で、マトロイドの最大重み基の重みを求められる。同じ重みの要素の選び方を調べて、最大重み基の個数を数えられる

前提

マトロイドの独立集合・基・階数（大学院数学凸最適化・組合せ最適化）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

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

説明

有限集合 $E$ 上のマトロイドの各要素に実数の重み $w (e)$ が与えられたとき、基 $B$ の重み $w (B) = \sum_{e \in B} w (e)$ を最大にする基（最大重み基）を、重みの大きい順に「独立性を保てるなら加える」という単純な手順（貪欲法）で求められます。グラフ的マトロイドでは最大重み全域木（クラスカル法の逆順版）、線形マトロイドでは重み付きのベクトルから基を選ぶ問題になります。さらに、同じ重みの要素ごとにグループに分けて選び方を調べることで、最大重み基がいくつあるかも数えられます。

なぜそうしてよいのか

マトロイドの独立集合族 $I$ は、(i) 独立集合の部分集合は独立、(ii) $I, J \in I$ , $∣ I ∣ < ∣ J ∣$ ならある $x \in J ∖ I$ で $I \cup {x} \in I$ （増加公理）、を満たし、その帰結として、どの部分集合 $X$ についても $X$ に含まれる極大な独立集合（ $X$ の基）はすべて同じ大きさ $r (X)$ をもちます。以下、現れる重みの値を $w_{1} > w_{2} > \dots > w_{k}$ とし、重みが $w_{j}$ の要素のグループを $G_{j}$ 、重みが $w_{j}$ 以上の要素全体を $E_{j} = G_{1} \cup \dots \cup G_{j}$ とします（ $E_{0} = \emptyset$ , $E_{k} = E$ ）。

しきい値で切って考える。 任意の基 $A$ （ $∣ A ∣ = r (E)$ ）について、重みを段差に分けて足し直すと $w (A) = j = 1 \sum k - 1 (w_{j} - w_{j + 1}) ∣ A \cap E_{j} ∣ + w_{k} ∣ A ∣$ となります（重み $w_{i}$ の要素は、 $j \geq i$ の項で $w_{j} - w_{j + 1}$ ずつ、最後に $w_{k}$ を数えられ、合計 $w_{i}$ になります）。 $A \cap E_{j}$ は $E_{j}$ に含まれる独立集合なので $∣ A \cap E_{j} ∣ \leq r (E_{j})$ で、係数 $w_{j} - w_{j + 1}$ は正です。 $∣ A ∣ = r (E)$ はどの基でも同じなので（ $w_{k}$ が負でもかまいません）、 $w (A) \leq j = 1 \sum k - 1 (w_{j} - w_{j + 1}) r (E_{j}) + w_{k} r (E)$ が成り立ち、等号はすべての $j$ で $∣ A \cap E_{j} ∣ = r (E_{j})$ 、つまり $A \cap E_{j}$ が $E_{j}$ の基であるときに限ります。貪欲法で得た $B$ はこの条件を満たします。実際、 $E_{j}$ の要素をすべて調べ終えた時点で、捨てられた $e \in E_{j}$ は、そのときの選択集合（ $B \cap E_{j}$ の部分集合）に加えると従属だったので、(i) より $(B \cap E_{j}) \cup {e}$ も従属です。よって $B \cap E_{j}$ は $E_{j}$ の中で極大な独立集合、すなわち $E_{j}$ の基です。したがって $B$ は上の上界を達成し、最大重み基です。

個数の数え方。 上の議論から、最大重み基とは「すべての $j$ で $A \cap E_{j}$ が $E_{j}$ の基」となる基のことです。そこで $A$ をグループ $G_{1}, G_{2}, \dots$ の順に決めていくと、 $G_{j}$ から選ぶ個数は $c_{j} = r (E_{j}) - r (E_{j - 1})$ でどの最大重み基でも同じです。すでに決めた $B_{j - 1} = A \cap E_{j - 1}$ （ $E_{j - 1}$ の基）に対し、 $S \subseteq G_{j}$ , $∣ S ∣ = c_{j}$ で $B_{j - 1} \cup S$ が独立になるものを選びます。ここで $E_{j - 1}$ の要素はどれも $B_{j - 1}$ に加えても階数を増やさない（グラフ的マトロイドなら $B_{j - 1}$ と $E_{j - 1}$ は同じ連結成分をもつ、線形マトロイドなら同じ部分空間を張る）ので、 $B_{j - 1} \cup S$ が独立かどうかは「 $r (E_{j - 1} \cup S) = r (E_{j - 1}) + ∣ S ∣$ か」だけで決まり、 $B_{j - 1}$ の選び方によりません。よって各段の選び方の数 $N_{j}$ は以前の選び方と無関係に決まり、最大重み基の個数は積 $N_{1} N_{2} \dots N_{k}$ になります。

手順

要素を重みの値ごとにグループ $G_{1}, G_{2}, \dots, G_{k}$ （重み $w_{1} > w_{2} > \dots > w_{k}$ ）に分け、重みの大きい順に並べる。同じ重みの要素どうしは任意の順でよい
選んだ集合を $B = \emptyset$ から始め、並べた順に要素 $e$ を調べて、 $B \cup {e}$ が独立なら $e$ を $B$ に加え、従属なら捨てる（グラフ的マトロイドなら「閉路ができないか」、線形マトロイドなら「1 次独立か」で判定）
$∣ B ∣ = r (E)$ になったら止める（重みが負の要素も、基の大きさに足りなければ加える）。このとき $B$ は最大重み基で、最大重みは $w (B) = \sum_{e \in B} w (e)$
個数を数えるときは、各グループについて $E_{j} = G_{1} \cup \dots \cup G_{j}$ の階数を求め、 $G_{j}$ から選ぶ個数 $c_{j} = r (E_{j}) - r (E_{j - 1})$ を出す（ $r (E_{0}) = 0$ ）
各 $j$ で、 $S \subseteq G_{j}$ , $∣ S ∣ = c_{j}$ のうち $r (E_{j - 1} \cup S) = r (E_{j - 1}) + c_{j}$ となるもの（＝前の段で選んだ基に加えても独立なもの）の数 $N_{j}$ を数える。グラフ的マトロイドなら、 $E_{j - 1}$ の各連結成分を 1 点につぶしたグラフで $S$ が閉路を作らない選び方を数えればよい
最大重み基の個数は $N_{1} N_{2} \dots N_{k}$ （ $c_{j} = 0$ の段は $N_{j} = 1$ ）

例題

頂点 $1, 2, 3, 4$ をもつ完全グラフ $K_{4}$ のグラフ的マトロイドを考える。各辺の重みを $w (12) = 5, w (13) = w (23) = w (14) = w (24) = 3, w (34) = 1$ とする（ $ij$ は頂点 $i, j$ を結ぶ辺）。このマトロイドの基（全域木）の重みの最大値と、最大重み基の個数を、この順に求めよ。

例題の解答

頂点 4 個で連結なので階数は $r (E) = 4 - 1 = 3$ で、基は辺 3 本の全域木です。

手順 1: グループは $G_{1} = {12}$ （重み 5）, $G_{2} = {13, 23, 14, 24}$ （重み 3）, $G_{3} = {34}$ （重み 1）。並べる順は $12, 13, 23, 14, 24, 34$ とします。

手順 2: 順に調べます。
- $12$ : 閉路はできないので加える。 $B = {12}$
- $13$ : 閉路はできないので加える。 $B = {12, 13}$
- $23$ : $1 - 2 - 3 - 1$ の閉路ができる（従属）ので捨てる
- $14$ : 頂点 4 はまだどの辺ともつながっていないので加える。 $B = {12, 13, 14}$

手順 3: $∣ B ∣ = 3$ で止めます。最大重みは $5 + 3 + 3 = 11$ 。

手順 4: $E_{1} = {12}$ の階数は 1 なので $c_{1} = 1$ 。 $E_{2} = {12, 13, 23, 14, 24}$ は 4 頂点をすべてつなぐので階数 3、 $c_{2} = 3 - 1 = 2$ 。 $E_{3} = E$ の階数も 3 なので $c_{3} = 0$ 。

手順 5: $N_{1} = 1$ （ $12$ を選ぶしかない）。 $N_{2}$ は、 $E_{1}$ の連結成分 ${1, 2}$ を 1 点 $P$ につぶしたグラフで考えます。 $13, 23$ はどちらも $P$ – $3$ の辺、 $14, 24$ はどちらも $P$ – $4$ の辺になるので、閉路を作らずに 2 本選ぶには $P$ – $3$ から 1 本、 $P$ – $4$ から 1 本選ぶ必要があり、 $N_{2} = 2 \times 2 = 4$ （ ${13, 23}$ や ${14, 24}$ は $12$ と閉路を作るので不可）。 $c_{3} = 0$ より $N_{3} = 1$ 。

手順 6: 個数は $1 \times 4 \times 1 = 4$ 。実際、最大重み基は ${12, 13, 14}, {12, 13, 24}, {12, 23, 14}, {12, 23, 24}$ の 4 個です。

したがって、最大値は $11$ 、個数は $4$ 。

答え: $(11, 4)$

よくある誤り

独立性を確かめずに、重みの大きい方から $r$ 個をそのまま選んでしまう誤り。例えば $K_{4}$ で $w (12) = 5, w (13) = w (23) = 4, w (14) = 3, w (24) = 2, w (34) = 1$ のとき、上位 3 本 $12, 13, 23$ は閉路をなして基でないので $5 + 4 + 4 = 13$ は答えにならない。正しくは各段階で $B \cup {e}$ が独立かを判定し、独立のときだけ加える（答えは $5 + 4 + 3 = 12$ ）
重みが負の要素を捨てて、要素の少ない集合で止めてしまう誤り。「最大重み基」は大きさ $r (E)$ の基の中で最大を求めるので、例えば階数 2 で重み $3$ の要素を選んだあと独立に加えられる要素が重み $- 1$ のものしかないなら、答えは $3 + (- 1) = 2$ であって $3$ ではない（ $3$ は最大重みの独立集合の値）
同じ重みのグループから選ぶ個数だけを見て、独立性を確かめずに $(c _{j} ∣ G _{j} ∣)$ を掛けてしまう誤り。例題では重み 3 のグループから 2 本選ぶので $(2 4) = 6$ とすると個数を $6$ と答えてしまうが、 ${13, 23}$ と ${14, 24}$ は $12$ と閉路を作る。正しくは前の段の連結成分をつぶしたグラフで閉路を作らない選び方だけを数えて $N_{2} = 4$ 、個数は $4$
いったん捨てた要素を後で拾い直そうとする、または採用した要素を後で入れ替えようとする誤り。ある時点で $B \cup {e}$ が従属なら、 $B$ を大きくした後も $B \cup {e}$ は従属のまま（従属集合を含む集合は従属）なので、各要素は 1 回調べれば十分である。例えば例題で捨てた $23$ を最後に $13$ と入れ替えても重みは $11$ のままで、改善にはならない

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

入口の問題

難易度 1（大学院の講義の例題レベル）
$E = {1, 2, 3, 4, 5, 6}$ とし、 $E$ 上の一様マトロイド $U_{3, 6}$ を考える。すなわち、 $E$ の部分集合 $I$ が独立であるとは $∣ I ∣ \leq 3$ であることとする。各要素 $i \in E$ に重み $w (i)$ を
$w (1) = 4, w (2) = 7, w (3) = 2, w (4) = 7, w (5) = 5, w (6) = 3$
で与え、基 $B$ の重みを $w (B) = \sum_{i \in B} w (i)$ と定める。 $U_{3, 6}$ の基の重みの最大値を求めよ。

この技能を使う問題

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

双対マトロイドと切り詰め（大学院数学凸最適化・組合せ最適化）