この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

凸最適化・組合せ最適化の問題

難易度 2大学院の講義の演習問題レベル大学院数学凸最適化・組合せ最適化

有限集合 $E = {1, 2, 3, 4, 5, 6, 7, 8}$ の部分集合の族 $(A_{1}, A_{2}, A_{3}, A_{4}, A_{5})$ を次で定める。
$A_{1} = {1, 2}, A_{2} = {1, 2}, A_{3} = {1, 3, 4}, A_{4} = {3, 4, 5}, A_{5} = {5, 6, 7, 8} .$
部分集合 $I \subseteq E$ が独立であるとは、単射 $φ : I \to {1, 2, 3, 4, 5}$ で、すべての $i \in I$ に対して $i \in A_{φ (i)}$ を満たすものが存在することと定める（ $φ$ は空写像でもよく、 $\emptyset$ は独立とする）。このとき独立集合全体は $E$ 上のマトロイド $M$ （族 $(A_{1}, \dots, A_{5})$ の横断マトロイド）をなす。

各要素の重み $w : E \to R$ を
$w (1) = 6, w (2) = 5, w (3) = 8, w (4) = 7, w (5) = 10, w (6) = 9, w (7) = 4, w (8) = 3$
とし、 $B \subseteq E$ に対して $w (B) = \sum_{i \in B} w (i)$ とおく。 $M$ の基 $B$ に対する $w (B)$ の最大値を求めよ。

この問題で使うもの

貪欲法による最大重み基（説明と入口の問題）
マトロイドの独立集合・基・階数（説明と入口の問題）

この問題を解けるようになるまで（37 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

マトロイドの最大重み基は貪欲法（重みの大きい順に、独立性を保つ限り加える）で求まる。まず階数を調べよう。

ヒント 2

独立性の判定にはホールの定理を使う。特に $3, 4$ はどちらも $A_{3}, A_{4}$ にしか属さず、 $5$ は $A_{4}, A_{5}$ 、 $6$ は $A_{5}$ にしか属さないことに注目する。

ヒント 3

階数は $5$ 。重みの順に $5, 6, 3$ は独立に加えられるが、次の $4$ を加えると ${3, 4, 5, 6}$ がたった $3$ 個の集合 $A_{3}, A_{4}, A_{5}$ にしか含まれず従属になる。

答えと解説

答えを見る

38

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

階数. 独立集合は ${1, \dots, 5}$ への単射をもつので要素数は $5$ 以下である。一方 $φ (2) = 1, φ (1) = 2, φ (3) = 3, φ (5) = 4, φ (6) = 5$ により ${1, 2, 3, 5, 6}$ は独立なので、 $M$ の階数は $5$ であり、基はちょうど $5$ 個の要素からなる。

貪欲法. マトロイドでは、重みの大きい順に要素を見て、独立性を保つものだけを加える貪欲法で最大重み基が得られる（マトロイドの交換公理から従う基本定理）。各要素が属する集合は
$1 : A_{1}, A_{2}, A_{3}$ , $2 : A_{1}, A_{2}$ , $3 : A_{3}, A_{4}$ , $4 : A_{3}, A_{4}$ , $5 : A_{4}, A_{5}$ , $6, 7, 8 : A_{5}$ である。独立性の判定にはホールの定理（ $I$ が独立 $⟺$ 任意の $J \subseteq I$ について $J$ の要素を含む $A_{k}$ の個数が $∣ J ∣$ 以上）を使う。

重みの大きい順は $5 (10), 6 (9), 3 (8), 4 (7), 1 (6), 2 (5), 7 (4), 8 (3)$ 。
- $5$ を加える: ${5}$ は独立。
- $6$ を加える: $6 \to A_{5}, 5 \to A_{4}$ で独立。
- $3$ を加える: $6 \to A_{5}, 5 \to A_{4}, 3 \to A_{3}$ で独立。
- $4$ を加える: $J = {3, 4, 5, 6}$ の要素を含む集合は $A_{3}, A_{4}, A_{5}$ の $3$ 個しかなく $3 < 4$ 。ホールの条件に反するので従属。 $4$ は加えない。
- $1$ を加える: $1 \to A_{1}, 3 \to A_{3}, 5 \to A_{4}, 6 \to A_{5}$ で独立。
- $2$ を加える: $2 \to A_{1}, 1 \to A_{2}, 3 \to A_{3}, 5 \to A_{4}, 6 \to A_{5}$ で独立。ここで要素数が階数 $5$ に達したので、 $7, 8$ は加えられない。

よって最大重み基は $B = {1, 2, 3, 5, 6}$ であり、
$w (B) = 6 + 5 + 8 + 10 + 9 = 38.$
（参考: $4$ を含む基、例えば ${1, 2, 3, 4, 5}$ の重みは $36$ で、確かに小さい。）

答えは $38$ 。

別解

最大重み基は貪欲法で求められる。重みの大きい順に 5(10), 6(9), 3(8), 4(7), 1(6), 2(5), 7(4), 8(3) を、独立性を保てるときだけ加える。

5 を加える：5→ $A_{4}$ で独立。
6 を加える：6→ $A_{5}$ 、5→ $A_{4}$ で独立。
3 を加える：3→ $A_{3}$ で独立。 ${3, 5, 6}$ は独立。
4 を加える： ${3, 4, 5, 6}$ の要素を含む集合は $A_{3}, A_{4}, A_{5}$ の 3 個しかなく、Hall の条件が破れる。よって加えない。
1 を加える：1→ $A_{1}$ 、3→ $A_{3}$ 、5→ $A_{4}$ 、6→ $A_{5}$ で独立。
2 を加える：2→ $A_{2}$ を加えて、 ${1, 2, 3, 5, 6}$ は独立。

独立集合 ${1, 2, 3, 5, 6}$ は大きさ 5 で、集合の個数が 5 なので階数の上限に達している。したがって基である。

重みは $6 + 5 + 8 + 10 + 9 = 38$ 。

検算：階数は 5 で、 ${1, 2, 3, 4, 5}$ も独立である。 $4$ を含む基の重みを調べる。 ${3, 4, 5, 6}$ は独立でないので、3,4,5,6 のうち 4 個を同時には取れない。基は ${1, 2}$ と ${3, 4, 5, 6, 7, 8}$ から 3 個ちょうどを取る形になる。ここで 1,2 は $A_{1}, A_{2}$ を占め、残る $A_{3}, A_{4}, A_{5}$ に 3 個を割り当てる。3 個の選び方で最大のものは ${3, 5, 6}$ で重み 27。 ${3, 5, 6}$ が独立であることは上で確認済み。1,2 の重み 11 を加えて 38。

凸最適化・組合せ最適化の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題