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

$M^{\ast }$ の独立集合の特徴づけ. 双対マトロイドの定義から、$I\subseteq E$ が $M^{\ast }$ で独立 $⟺$ $E\setminus I$ が $M(K_5)$ の基（全域木）を含む $⟺$ $K_5$ から $I$ の辺を除いたグラフが連結、である。$r(M^{\ast })=|E|-r(M(K_5))=10-4=6$ なので、切り詰め $T$ の階数は $5$ であり、$T$ の基は「除いても $K_5$ が連結のままである 5 本の辺の集合」である。

除いて非連結になるのは、$I$ がある辺カットを含むときである。$K_5$ の頂点を $S$ と $V\setminus S$ に分ける辺カットの大きさは $|S|(5-|S|)$ なので、$|S|=1$ のとき $4$、$|S|=2$ のとき $6$ である。したがって $|I|\le 5$ の $I$ について
$$I\text{ が }{M}^{\ast }\text{ で従属}⟺I\text{ がある頂点 }v\text{ に接続する 4 本の辺（星）をすべて含む}$$
となる（大きさ $6$ のカットは $5$ 本以下の集合には含まれない）。特に $|I|\le 3$ ならつねに独立である。

貪欲法. マトロイドの最大重み基は、重みの大きい順に、独立性を保つ限り要素を加える貪欲法で得られる。重みを大きい順に並べると
$$w(45)=48,w(35)=40,w(25)=36,w(15)=34,w(34)=24,w(24)=20,w(14)=18,w(23)=12,w(13)=10,w(12)=6.$$

• $45,35,25$: $3$ 本以下なので採用。
• $15$: 加えると $\{15,25,35,45\}$ は頂点 $5$ の星そのものなので従属。不採用。
• $34$: $\{45,35,25,34\}$ は星を含まない（頂点 $5$ の星には $15$ が足りず、他の頂点の星には含まれる辺が $2$ 本以下）。採用。
• $24$: $\{45,35,25,34,24\}$ を調べる。頂点 $5$ の星は $15$ を欠き、頂点 $4$ の星は $14$ を欠き、頂点 $2,3$ の星に含まれる辺はそれぞれ $3$ 本以下、頂点 $1$ の星の辺は含まない。よって独立で、採用。これで $5$ 本となり基が得られた。

（確認として、この 5 本を除いた残り $\{12,13,14,15,23\}$ は頂点 $1$ から全頂点に辺が出ているので連結である。）

したがって最大値は
$$48+40+36+24+20=168.$$

$K_5$ は頂点 5、辺 10 本、$M(K_5)$ の階数は 4。双対 $M^{\ast }$ の階数は $10-4=6$ で、$M^{\ast }$ の独立集合は「補集合が全域連結部分グラフ（全域木を含む）となる辺集合」である。$T$ は $M^{\ast }$ の階数 5 への切り詰めなので、$T$ の基 $B$ は $|B|=5$ かつ $E\setminus B$ が $K_5$ の全域木を含む 5 辺の集合である。つまり $C=E\setminus B$ は 5 辺からなる連結な全域部分グラフ（全域木 + 辺 1 本）。

全辺の重みの和: 各頂点は 4 辺に含まれるので ${\sum }_{e}w(e)=4(2+4+8+16+32)=248$。よって $w(B)=248-w(C)$ であり、$w(C)$ を最小化すればよい。

$w(C)={\sum }_v{\mathrm{deg}}_C(v)2^v$。各頂点の次数は 1 以上、次数和は 10。次数 1 を基準に余分な次数 5 を配分し、$w(C)=62+{\sum }_v{e}_v{2}^v$（$e_v={\mathrm{deg}}_C(v)-1$, $\sum e_v=5$）。
- $e_1\le 3$。$e_1=3$ のとき残り 2 を配分: $e_2=2$（次数列 $(4,3,1,1,1)$）は、頂点 2 の隣接頂点のうち 1 以外が次数 1 の頂点になれず実現不可能。$e_2=1,e_3=1$（次数列 $(4,2,2,1,1)$）は実現可能で $w=62+6+4+8=80$。
- $e_1\le 2$ の場合、$e_2=3$（次数列 $(3,4,1,1,1)$）は同様に実現不可能。実現可能な他の次数列、たとえば $(3,3,2,1,1)$ は 82、$(4,2,1,2,1)$ は 88 などでいずれも 80 より大きい。

$w(C)=80$ は $C=\{12,13,23,14,15\}$（三角形 123 に 4, 5 を頂点 1 から付けたもの）で達成される: $6+10+12+18+34=80$。これは連結で全域的。

以上より $B=E\setminus C=\{24,25,34,35,45\}$ で $w(B)=(4+16)+(4+32)+(8+16)+(8+32)+(16+32)=20+36+24+40+48=168$。検算: $248-80=168$。

最大値は $168$。