グラフ理論の問題

最大マッチング $\nu (G)$ を求める。
頂点 $7$ と $11$ はどの頂点とも辺で結ばれていない（$V$ の中に $7,11$ の約数や $2$ 倍以上の倍数がない）。したがって、マッチングに使える頂点は残りの $9$ 個 $\{2,3,4,5,6,8,9,10,12\}$ だけである。マッチングの各辺は相異なる 2 頂点を使うので、$\nu (G)\le \lfloor 9/2\rfloor =4$ となる。
一方、$\{4,8\},\{3,9\},\{5,10\},\{6,12\}$ はどの 2 本も端点を共有しないので、辺数 $4$ のマッチングである。よって $\nu (G)=4$。

最大独立集合 $\alpha (G)$ を求める。
$\{7,8,9,10,11,12\}$ を考える。$7$ 以上 $12$ 以下の相異なる 2 数では、小さいほうの $2$ 倍は $14$ 以上で $12$ を超えるから、一方が他方を割り切ることはない。よってこの集合は独立集合であり、$\alpha (G)\ge 6$ である。
逆に、$V$ を次の $6$ 個の部分に分ける。
$$\{2,4,8\},\{3,6,12\},\{5,10\},\{9\},\{7\},\{11\}$$
$\{2,4,8\}$ と $\{3,6,12\}$ はそれぞれ三角形（3 頂点のどの 2 つも辺で結ばれている）であり、$\{5,10\}$ は辺である。独立集合はこれらの各部分から高々 $1$ 個の頂点しか含めないので、$\alpha (G)\le 6$ である。よって $\alpha (G)=6$。

最小頂点被覆 $\tau (G)$ を求める。
頂点の部分集合 $S$ が独立集合であることと、その補集合 $V\setminus S$ が頂点被覆であることは同値である（辺の両端がともに $S$ に入らないことと、どの辺も少なくとも一方の端点が $V\setminus S$ に入ることは同じ）。したがって
$$\tau (G)=|V|-\alpha (G)=11-6=5$$
である。実際、$\{2,3,4,5,6\}$ はすべての辺の少なくとも一方の端点を含む頂点被覆である。

なお、$G$ は三角形を含むので二部グラフではなく、ケーニッヒの定理（$\nu =\tau$）は成り立たない。実際 $\nu (G)=4<5=\tau (G)$ である。

以上より、$(\nu (G),\alpha (G),\tau (G))=(4,6,5)$。

非孤立頂点は $2,3,4,5,6,8,9,10,12$ の 9 個で、$7,11$ は孤立頂点である。

最大マッチング $\nu (G)$: 非孤立頂点が 9 個なので $\nu \le 4$。マッチング $\{5,10\},\{3,9\},\{2,8\},\{4,12\}$ が 4 辺で取れるので、$\nu =4$。

最小頂点被覆 $\tau (G)$: 互いに頂点を共有しない部分グラフとして、三角形 $\{2,4,8\}$（辺 $2$-$4$, $4$-$8$, $2$-$8$）、三角形 $\{3,6,12\}$（辺 $3$-$6$, $6$-$12$, $3$-$12$）、辺 $\{5,10\}$ を取る。三角形の被覆には 2 頂点ずつ、辺の被覆には 1 頂点が必要なので、$\tau \ge 2+2+1=5$。
一方、$\{2,3,4,5,12\}$ が被覆になる。
- 2 を端点とする辺は 2 で覆われる。
- 3 を端点とする辺は 3 で覆われる。
- $4$-$8$ は 4 で、$4$-$12$ は 4 と 12 で、$6$-$12$ は 12 で覆われる。
- $5$-$10$ は 5 で覆われる。

よって $\tau =5$。

最大独立集合 $\alpha (G)$: 独立集合の補集合は頂点被覆なので、$\alpha =|V|-\tau =11-5=6$。
検算として、$\{6,7,8,9,10,11\}$ は互いに辺で結ばれていない（$6$ と $8,9,10$、$8$ と $10$ など、どれも割り切らない）。大きさ 6 の独立集合が実際に存在する。

答え: $(4,6,5)$