グラフ理論の問題

手順 1：2 部グラフであることの確認

どの辺も文字の頂点 $\{a,b,c,d,e\}$ と数字の頂点 $\{1,2,3,4,5\}$ を結んでいる。したがって $G$ は $L=\{a,b,c,d,e\}$, $R=\{1,2,3,4,5\}$ を 2 つの部集合とする 2 部グラフである。よってケーニヒの定理 $\nu (G)=\tau (G)$ が使える。

手順 2：増加道を使って最大マッチングを作る

まず辺を順に選んで、マッチング $M_0=\{\{a,1\},\{d,2\},\{e,4\}\}$（大きさ $3$）を作る。

$M_0$ に含まれない辺と含まれる辺を交互にたどり、両端がどちらもマッチングで覆われていない頂点になる道（増加道）を探す。$b$ から出発すると
$$b-1=a-2=d-3$$
という道が見つかる（$-$ は $M_0$ に含まれない辺、$=$ は $M_0$ に含まれる辺）。$b$ と $3$ はどちらも $M_0$ で覆われていないので、これは増加道である。この道の上で、辺がマッチングに入っているかどうかを入れ替えると
$$M=\{\{b,1\},\{a,2\},\{d,3\},\{e,4\}\}$$
となり、大きさ $4$ のマッチングが得られる。よって $\nu (G)\ge 4$ である。

手順 3：これ以上大きくできないことの確認

$a,b,c$ が隣接する頂点は、どれも $1,2$ のどちらかだけである。マッチングの辺は端点を共有しないので、$a,b,c$ のうちマッチングで覆える頂点は高々 $2$ 個である。したがって、マッチングで覆える $L$ の頂点は高々 $5-1=4$ 個であり、$\nu (G)\le 4$ となる。

以上より $\nu (G)=4$ である。

（確認：$\{1,2,d,e\}$ は頂点被覆になっている。$a,b,c$ を端点とする辺はすべて $1$ か $2$ を含み、$d,e$ を端点とする辺は $d$ か $e$ を含むからである。）

手順 4：ケーニヒの定理で $\tau (G)$、さらに $\alpha (G)$ を求める

ケーニヒの定理より $\tau (G)=\nu (G)=4$ である。$\alpha (G)+\tau (G)=|V|$ と $|V|=10$ から
$$\alpha (G)=10-4=6$$
となる。

実際、最小頂点被覆 $\{1,2,d,e\}$ の補集合 $\{a,b,c,3,4,5\}$ をとると、この $6$ 頂点のどの 2 つの間にも辺がないので、これは大きさ $6$ の独立集合である。

答え：$\alpha (G)=6$

$G$ は二部グラフ（部分 $\{a,b,c,d,e\}$ と $\{1,2,3,4,5\}$）で、孤立点はない。ケーニッヒの定理より、最大マッチングの大きさ $\nu$ について $\alpha (G)=|V|-\nu (G)=10-\nu (G)$ である。

最大マッチング：$\{b,1\},\{a,2\},\{d,3\},\{e,4\}$ は互いに頂点を共有しない 4 本の辺なので、$\nu \ge 4$。
一方、$a,b,c$ の隣接頂点はすべて $\{1,2\}$ に含まれる。したがって $a,b,c$ のうち同時にマッチングに入れるのは高々 2 個である。$d,e$ を合わせても、マッチングの大きさは高々 $2+2=4$。よって $\nu =4$。

ゆえに $\alpha (G)=10-4=6$。

検算：$\{a,b,c,3,4,5\}$ は独立集合である。$a,b,c$ は同じ側の頂点なので互いに隣接せず、$3,4,5$ も同様である。また $a,b,c$ の隣接頂点は $1,2$ だけなので、$a,b,c$ と $3,4,5$ の間に辺はない。大きさは 6 で、上の計算と一致する。