二部グラフ G = (V, U, E) があるとしましょう
v1 は u1、u2、および u3 に接続されています
v2 は u2 と u3 に接続されています
v3 は u3 に接続されています。
グラフを見ると、頂点カバーの最小値が {v1, v2, u3} と {v1, u2, u3} であることがわかりますが、2 部マッチング/頂点カバー アルゴリズムを使用してこれを見つける方法がわかりません。 . ここ とここ
手動でアルゴリズムを実行すると、出力は V のすべての単純な最小頂点カバーだけになります。何か間違ったことをしていますか?
編集：
グラフの最大一致は、エッジ (v1、u1)、(v2、u2)、および (v3、u3) です。最大の一致が与えられた場合、次のステップは、不飽和頂点 (一致したエッジの終点の 1 つではない頂点) から開始することです。
しかし、この場合はすべての頂点が飽和しているため、どうすればよいかわかりません。
ケーニッヒの定理には 2 つの方向性があります。弱い線形計画法の双対性に対応する簡単な方向は、頂点カバーが少なくともマッチングと同じ大きさであるということです。これは、すべての頂点カバーで、一致する各エッジに少なくとも 1 つの端点が存在するためです。
強力な LP 双対性に対応するケーニッヒの定理の厳密な方向性は、一致する各エッジの多くても (つまり、正確に) 1 つの端点が存在する頂点カバーが存在するということです。ウィキペディアの現在の証明の要点は、頂点カバーを貪欲に構築するためにマッチングを使用することであり、このアルゴリズムが行き詰まった場合、主張されている最大マッチングには拡張パス (矛盾) があることを示しています。すべてのエッジは一致する頂点に付随するため、一致しない頂点はカバーから除外できます。次に、それらの隣人を含める必要があります。隣人の隣人を除外することができます。
このプロセスでは、各頂点のステータスを判断できない場合があることに気付きました。この場合、ウィキペディアの編集者は、「そのような頂点がないが、以前に定義されたセット Sk に含まれていない頂点が残っている場合、これらのいずれかを任意に選択し、S2j+1 をその単一の頂点で構成する」と書いています。このステップを正当化する 1 つの方法は次のとおりです。u を選択した頂点、v を u のメイトとすると、v のメイトは u ではなく、新しく作成された頂点 u' であるかのように見せかけています。次に、u は一致しないため、u を除外してアルゴリズムを再シードし、新しく作成されたエッジ u' -- v を後で v を含めるときにカバーします。