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

有限集合 $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$ が独立であるとは、単射 $\phi :I\to \{1,2,3,4,5\}$ で、すべての $i\in I$ に対して $i\in A_{\phi (i)}$ を満たすものが存在することと定める（$\phi$ は空写像でもよく、$\varnothing$ は独立とする）。このとき独立集合全体は $E$ 上のマトロイド $M$（族 $(A_1,\dots ,A_5)$ の横断マトロイド）をなす。

各要素の重み $w:E\to \mathbb{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)$ の最大値を求めよ。

$E=\{1,2,3,4,5,6\}$ とし、$E$ 上の一様マトロイド $U_{3,6}$ を考える。すなわち、$E$ の部分集合 $I$ が独立であるとは $|I|\le 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}$ の基の重みの最大値を求めよ。

頂点集合を $\{1,2,3,4\}$ とする完全グラフ $K_4$ の辺集合を $E$ とし、$M$ を $E$ 上のグラフ的マトロイド（独立集合は森をなす辺集合）、$M^{\ast }$ をその双対マトロイドとする。各辺 $e\in E$ に重み $w(e)$ を
$$w(\{1,2\})=1,w(\{1,3\})=4,w(\{1,4\})=3,w(\{2,3\})=2,w(\{2,4\})=6,w(\{3,4\})=5$$
で与え、辺集合 $B$ の重みを $w(B)={\sum }_{e\in B}w(e)$ と定める。$M^{\ast }$ の基の重みの最大値を求めよ。

頂点集合を $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)$ を求めよ。

${\mathbb{F}}_2=\{0,1\}$ を 2 元体とし、$E={\mathbb{F}}_2^4\setminus \{0\}$（15 個のベクトルからなる集合）とする。$E$ 上のマトロイド $M$ を、部分集合 $I\subseteq E$ が ${\mathbb{F}}_2$ 上 1 次独立であるとき、かつそのときに限り独立集合であるものとして定める（$M$ の階数は $4$）。$M^{\ast }$ を $M$ の双対マトロイド、すなわち $M$ の基の補集合 $E\setminus B$ 全体を基の族とするマトロイドとする。

ベクトル $v\in E$ の成分のうち $1$ であるものの個数を $\mathrm{hw}(v)$ と書き、重み $w:E\to \mathbb{Z}$ を
$$w(v)=\{\begin{array}{ll}1& (\mathrm{hw}(v)=2,4)\\ 2& (\mathrm{hw}(v)=1)\\ 3& (\mathrm{hw}(v)=3)\end{array}$$
で定める。$M^{\ast }$ の基 $B^{\ast }$ の重みを $w(B^{\ast })={\sum }_{v\in B^{\ast }}w(v)$ とするとき、$w(B^{\ast })$ が最大となる $M^{\ast }$ の基 $B^{\ast }$ の個数を求めよ。