頂点集合を とする完全グラフ の辺集合を とし、 を 上のグラフ的マトロイド（独立集合は森をなす辺集合）、 をその双対マトロイドとする。各辺 に重み を
で与え、辺集合 の重みを と定める。 の基の重みの最大値を求めよ。
双対マトロイドと切り詰め
双対マトロイドの階数 を使い、 の最大重み基が の最小重み基の補集合であることから重みの最大値を求められる。切り詰め の最大重み基も求められる
前提
- 貪欲法による最大重み基 （大学院数学 凸最適化・組合せ最適化）
この技能までの道筋（37 技能）
読み込み中…
右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
一覧で見る（前提が先）
- 三角形の角の大きさ （算数 平面図形）
- 対頂角と平行線の同位角・錯角 （中学数学 平面図形）
- 三角形の外角と角の組み合わせ （中学数学 平面図形）
- 小数の四則計算 （算数 計算と数のきまり）
- 分数のたし算・ひき算 （算数 計算と数のきまり）
- 分数のかけ算・わり算 （算数 計算と数のきまり）
- 小数と分数のまじった計算 （算数 計算と数のきまり）
- 逆算（□ を求める） （算数 計算と数のきまり）
- 正負の数の加法・減法 （中学数学 数と式）
- 四則の混じった計算の順序 （算数 計算と数のきまり）
- 正負の数の乗除・累乗と四則混合 （中学数学 数と式）
- 分配法則を使った計算のくふう （算数 計算と数のきまり）
- 文字式の計算（同類項・分配法則） （中学数学 数と式）
- 1 次方程式の解き方 （中学数学 方程式）
- 二等辺三角形の角 （中学数学 平面図形）
- 平行四辺形と特別な四角形の性質 （中学数学 平面図形）
- 三角形・四角形の面積 （算数 平面図形）
- 約数の見つけ方 （算数 整数の性質）
- 素因数分解と約数の個数 （算数 整数の性質）
- 平方根の意味と根号の簡単化 （中学数学 数と式）
- 三平方の定理 （中学数学 相似と三平方の定理）
- 乗法公式による展開 （中学数学 数と式）
- 折り返した図形の角と長さ （中学数学 平面図形）
- 三平方の定理と平面図形 （中学数学 相似と三平方の定理）
- ベクトルの演算と成分 （数学C ベクトル）
- 行列の和・積と 2 次の逆行列 （大学数学 線形代数）
- 掃き出し法と連立 1 次方程式 （大学数学 線形代数）
- 行列の階数と解の存在 （大学数学 線形代数）
- 樹形図で数え上げる （算数 場合の数）
- 積の法則と和の法則 （算数 場合の数）
- 和の法則・積の法則と樹形図 （数学A 場合の数と確率）
- 順列・円順列・重複順列 （数学A 場合の数と確率）
- 組合せ （数学A 場合の数と確率）
- グラフの次数と握手補題 （大学数学 グラフ理論）
- 最小全域木（クラスカル法・プリム法） （大学数学 グラフ理論）
- マトロイドの独立集合・基・階数 （大学院数学 凸最適化・組合せ最適化）
- 貪欲法による最大重み基 （大学院数学 凸最適化・組合せ最適化）
説明
有限集合 上のマトロイド （独立集合族 、階数関数 ）から、「 の基の補集合」を基とする双対マトロイド と、「大きさ 以下の独立集合」だけを残した切り詰め という 2 つの新しいマトロイドが作れます。この技能では、双対の階数 を計算し、 の最大重み基を「 の最小重み基の補集合」として求めます。また切り詰めの最大重み基を、貪欲法を途中で止めることで求めます。グラフで言えば、全域木の補集合（閉路をすべて壊すために取り除く辺の集合）の最大重みや、ちょうど 本の辺からなる森（ の基）の最大重みを求める場面で使います。
なぜそうしてよいのか
の基全体を とし、 とします。 の独立集合は のどれかに含まれる集合、つまり「補集合 が の基を含む（ となる）集合 」です。階数を求めると、 です。ここで基 は と最大で 個しか共有できず（ は の独立部分集合だから）、しかも の極大独立部分集合を基に拡張すればちょうど 個共有できるので、 です。これで が得られます。特に で、 の基の大きさは です（ がマトロイドの公理を満たすことも知られています）。
重み について、 の基 の重みは です。 は一定なので、これを最大にすることは を最小にすることと同じです。したがって「 の最大重み基 の最小重み基の補集合」で、最大値は になります。 の最小重み基は、重みの小さい順に独立性を保つ要素を加える貪欲法（重みを にした最大重み基の貪欲法と同じ）で求められます。
切り詰め （）の独立集合は で、基は大きさちょうど の独立集合です。貪欲法を に適用すると、大きさが に達するまでは に適用したときと同じ要素を選び、 個選んだ時点でそれ以上何も加えられなくなります。よって の最大重み基は「 の貪欲法で最初に選ばれる 個」です。途中で独立性を破る要素は飛ばすので、単に重みの大きい 個をとるのとは一般に異なります。
手順
問題が双対 についてか、切り詰め についてかを確認し、 の階数 を求める（ の基の大きさは 、 の基の大きさは ）。
双対の階数が必要なら に代入する。
の最大重み基を求めるときは、重みの小さい順に独立性を保つ要素を加える貪欲法で の最小重み基 を求める。
の最大重み基は 、その重みは として計算する。
の最大重み基を求めるときは、重みの大きい順の貪欲法を で行い（独立性を壊す要素は飛ばす）、 個選んだところで止める。
例題
完全グラフ の頂点を とし、辺の重みを , , , , , とする。 のグラフ的マトロイド （辺集合 上で、閉路を含まない辺集合を独立集合とする）の双対マトロイド について、基の重みの最大値を求めよ。
例題の解答
【手順 1】 は連結で頂点が 4 個なので （全域木の辺数）。 の基の大きさは 。
【手順 2】この問題では特定の集合の双対階数は必要ないので、手順 2 は使わない。
【手順 3】 の最小重み基（最小全域木）を、重みの小さい順の貪欲法で求める。（1）を採用、（2）を採用、（3）は -- の閉路を作るので不採用、（4）を採用。これで 3 本そろい、、。
【手順 4】 なので、 の最大重み基は で、その重みは （実際 ）。
（手順 5 は切り詰めのときの手順なので、この問題では使わない。）
答え:
よくある誤り
の最大重み基の補集合を の最大重み基としてしまう誤り。それは の最小重み基になる。例題では最大全域木 （重み ）の補集合 の重み が の最小値。正しくは最小重み基の補集合をとり、最大値は 。
双対の階数を としてしまう誤り。正しくは補集合の階数を使って 。例題で なら は全域木なので （ ではない）。
切り詰めの最大重み基を、独立性を無視して重みの大きい 個としてしまう誤り。たとえば頂点 、辺 （6）、（5）、（4）、（2）、（1）のグラフ（）で とすると、重みの大きい 3 本 の合計 を答えてしまうが、これは閉路で独立でない。正しくは貪欲法で , を採用、 は閉路を作るので飛ばし、 を採用して 、最大値は 。
の基の大きさを としてしまう誤り。正しくは で、例題では （偶然一致するが、たとえば では で と異なる）。
この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。
入口の問題
この技能を使う問題
とし、各 に のベクトル を次のように対応させる。
を 上の線形マトロイド（ が独立であるとは、 が 上一次独立であること）とし、 をその双対マトロイド（基は の基の補集合）とする。各要素の重みを
と定め、部分集合 の重みを とする。 の基 にわたる の最大値を求めよ。頂点集合を とする単純グラフ を考える。 の辺集合 は、 の異なる 頂点を結ぶ 本の辺すべてと、 本の辺 からなる（）。辺 を と書く。各辺の重み は次のとおりである。
閉路を含まない辺集合を森とよぶ（空集合も森とする）。 の部分集合 が独立であることを「森 を用いて と書けること」と定めると、これは 上のマトロイド （ のグラフ的マトロイド とそれ自身との合併 ）を定める。 の階数 と、 の基 の重み の最大値を、この順に組で求めよ。頂点集合を とする完全グラフ の辺集合を とし、 を 上のグラフ的マトロイド（独立集合は森をなす辺集合）、 をその双対マトロイドとする。さらに の階数 への切り詰め を
で定める（ はマトロイドである）。辺 （）に重み を与える。 の基 のうち、重みの和 が最大となるものについて、その最大値を求めよ。
を 2 元体とし、（15 個のベクトルからなる集合）とする。 上のマトロイド を、部分集合 が 上 1 次独立であるとき、かつそのときに限り独立集合であるものとして定める（ の階数は ）。 を の双対マトロイド、すなわち の基の補集合 全体を基の族とするマトロイドとする。
ベクトル の成分のうち であるものの個数を と書き、重み を
で定める。 の基 の重みを とするとき、 が最大となる の基 の個数を求めよ。