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

記号. $K=\{12,13,14,15,23,24,25,34,35,45\}$（頂点 $\{1,\dots ,5\}$ 上の $K_5$ の辺, $10$ 本）、$H=K\cup \{16,26,36\}$（頂点 $\{1,\dots ,6\}$ の間の辺, $13$ 本）とおく。

基本事実. $k$ 個の頂点の上の森は高々 $k-1$ 本の辺しかもたない。したがって独立集合 $I=F_1\cup F_2$ と頂点集合 $S$ について、両端が $S$ に入る $I$ の辺は高々 $2(|S|-1)$ 本である。

階数の上界. 独立集合 $I$ に対し、$|I\cap H|\le 2(6-1)=10$、$|I\setminus H|\le |E\setminus H|=1$（$E\setminus H=\{67\}$）であるから、
$$|I|\le 10+1=11.$$
同様に $|I\cap K|\le 2(5-1)=8$ も成り立つ。

階数 $11$ の独立集合の構成. 次の $11$ 本の辺からなる集合
$$B=\{12,13,14,15,23,24,25,34,36,26,67\}$$
を考え、これを次の $2$ つに分ける。
- $F_1=\{12,23,34,15,36,67\}$：$7$ 頂点を結ぶ $6$ 本の辺で連結（$4\text{-}3\text{-}2\text{-}1\text{-}5$, $3\text{-}6\text{-}7$）なので全域木であり、閉路をもたない。
- $F_2=\{13,14,24,25,26\}$：$3\text{-}1\text{-}4\text{-}2\text{-}5$ と $2\text{-}6$ からなる、頂点 $\{1,\dots ,6\}$ 上の木であり、閉路をもたない。

よって $B$ は独立であり、上界と合わせて $r_M(E)=11$ である。

最大重み基. 基 $B^{\prime }$ は $11$ 本の辺をもつので、その補集合 $R=E\setminus B^{\prime }$ は $3$ 本である。
- $|B^{\prime }\cap H|\le 10$ かつ $|H|=13$ より $|R\cap H|\ge 3$ である。よって $R\subseteq H$ であり、特に $67\notin R$ となる。
- $|B^{\prime }\cap K|\le 8$ かつ $|K|=10$ より $|R\cap K|\ge 2$ である。

$K$ の辺の重みのうち小さい $2$ つは $w(45)=3$, $w(35)=4$ である。$R$ の残り $1$ 本の重みは、$E$ の中で最小の重み $1$ 以上である。ゆえに
$$w(R)\ge 3+4+1=8$$
となる。等号は $R=\{45,35,16\}$ のときに成り立ち、このとき $E\setminus R$ はちょうど上で構成した $B$ である。したがって $B$ は基になっている。

全辺の重みの和は $1+2+\cdots +14=105$ であるから、
$$\underset{B^{\prime }}{\max }w(B^{\prime })=105-8=97.$$

（参考：貪欲法で確かめる。合併 $M(G)\vee M(G)$ はマトロイドなので、重みの大きい順に独立性を保つ辺を加える貪欲法で最大重み基が得られる。$36,34,25,24,23,15,14,13,12,67$ を順に採用する。次の $35$ は $K$ 内の辺が $9>8$ 本になるので棄却し、$45$ も同じ理由で棄却する。$26$ は採用する。最後の $16$ は $H$ 内の辺が $11>10$ 本になるので棄却する。こうして上の $B$ が得られる。）

答え：$(11,97)$

$M=M(G)\vee M(G)$ の独立集合は、2 つの森の和集合で表せる辺集合である。

階数。 辺 $67$ は橋（頂点 7 は次数 1）なので、森に必ず入れられる。残りのグラフ $H$（頂点 1〜6、辺 13 本）は 6 頂点なので、森 1 つにつき辺は高々 5 本である。したがって $H$ からは高々 10 本しか取れず、$r_M(E)\le 10+1=11$ となる。

10 本取れることは具体例で示す。$H$ の辺 $26,36$ を 1 本ずつ葉として使い、$K_5$ 部分から辺集合 $\{15,14,34,23\}$（道 5-1-4-3-2）と $\{12,13,24,25\}$（木）を取る。これらは $K_5$ の互いに素な全域木 2 本である。これに $26$ と $36$ を 1 本ずつ加えると、$H$ の互いに素な全域木 2 本になる。さらに $67$ を片方の森に加えれば 11 本の独立集合が得られる。よって $r_M(E)=11$ である。

最大重みの基。 基は大きさ 11 で、必ず $67$（重み 5）を含む。$H$ の全辺の重みの和は $105-5=100$ である。したがって、$H$ から 3 本の辺を除いて、残り 10 本が互いに素な全域木 2 本になるようにし、除く辺の重みの和を最小にすればよい。

頂点 6 の次数は $H$ で 3（辺 $16,26,36$）である。全域木 2 本のそれぞれが頂点 6 に接する辺を使うので、残す辺のうち頂点 6 に接するものは 2 本以上必要である。つまり $16,26,36$ のうち除けるのは高々 1 本である。

重みの小さい辺は $16(1),26(2),45(3),35(4),12(6),\dots$ である。除く 3 本の重みの和は、$16,45,35$ を除く場合の $1+3+4=8$ が最小である。$\{1,2,3\}$ は頂点 6 の次数が 1 になるので不可。重みの和が 8 未満の組で、$16$ と $26$ の両方を含まないものは他にない。

$16,45,35$ を除いたものが実際に可能なことは、上の分解で確認済みである。したがって最大重みは $105-8=97$ である。

答えは $(11,97)$。