しましょう $G$2部グラフになります。証明してください $\alpha(G) = |V(G)|/2$ Gが完全に一致する場合に限ります。

Question

しましょう $G$2部グラフになります。証明してください$\alpha(G) = |V(G)|/2$ 場合に限り $G$ 完全に一致しています。

$\alpha(G)$ の独立数です $G$、すなわち、の最大独立集合のサイズ$G$。

この証明を開始する方法がわかりません。の写真を見ると、これが真実であることがわかります。https://i.stack.imgur.com/lV4b9.png、しかし私は証明を定式化することはできません。誰かが私が完全な正式な証明を書くのを手伝ってくれるなら、私は非常に感謝するでしょう。

Answer 1

私はすでに基本的にコメントで解決策を示しているので、証明を完了するために追加の手順を実行します。完全な解決策を確認する前に、合理的な試みを試みてください。

しましょう $G$ 順序の2部グラフである $n$。まず、注意してください$G$ 完全に一致しています $\iff \alpha'(G) = \frac{n}{2}$ （これは、完全一致との定義から明らかです。 $\alpha'(G)$）。König-Egeváryの定理はそれを与えます$\alpha'(G) = \beta(G)$ （以来 $G$ Gallaiの結果はそれを与えますが $\alpha(G) + \beta(G)= n$（どちらも証明するのは特に難しいことではありませんが、ここでは証明しません）。上記を組み合わせると、次のようになります。$$\alpha(G) = n - \beta(G) = n - \alpha'(G),$$ それゆえ $$\alpha(G) = \frac{n}{2} \iff \alpha'(G) = \frac{n}{2},$$ 示されるように。

Answer 2

$(\Longleftarrow)$：しましょう $G$2部グラフであるため、König1931、Egerváry1931により、最大マッチングのサイズが得られます。$\alpha'(G)$ 最小頂点被覆のサイズに等しい $\beta(G)$、 あれは $$\alpha'(G)=\beta(G)$$さて、ガライ1958年までに、$$\alpha(G)+\beta(G)=|V(G)|$$したがって、 $$2\alpha(G)=|V(G)|\iff \alpha(G)=\frac{1}{2}|V(G)|$$

ここから他の意味に進むことができますか？