非常に重要な頂点を持つ二部グラフの頂点カバーを見つける

Question

私は二部グラフの最小頂点カバーを見つけることができます。最初に最大マッチングを見つけ、Konig's Theoremを使って同じ順序の頂点カバーにします。

しかし、得られた結果は、多くの有効な頂点カバーである可能性のあるものの1つに過ぎません。次のグラフでは、{A、B}、{C、D}、および{B、C}はすべて有効なカバーです。 Konig法を適用すると、カバー{A、B}が得られます。

(A)=====(C) 
    /
    /
/
(B)=====(D) 

特定の重要な頂点、たとえば頂点Dを含む最小の頂点カバーの存在を確認するにはどうすればよいですか？

私の最初の推測は、になります。グラフをクリックし、別の最小頂点カバーを見つけます。上記の場合、これは{C、D}をもたらす。どちらの解も重要な頂点を含んでいない場合、それは最小限のカバーの一部ではありません。しかし、私はこれを本当に自分自身に証明するのに十分深くは考えていません。

Answer 1

私は「非常に重要頂点」を削除し、によってカバーされるすべてのエッジ

（頂点カバーは$ C $とする）は、以下の方法

1. が最小頂点被覆の大きさを探すことをお勧め+のV |プロセス
2. リピート（頂点は$ V $こと）と「C $場合$

の新しい頂点カバーは$ Cも聞かせて同じ| = | C | $次に、最小頂点カバーを報告します。elseレポートには、特定の頂点に最小頂点カバーが存在しません。

私は同じ回答を持っていると思いますが、証拠は同じ行にもあります。

新しい頂点カバーは、$ C $が最小頂点カバーの1つであるという条件に違反するため、小さくすることはできません。

$ C '$はグラフの残りの部分をカバーする最小カバーです。

頂点$ V $を含む少なくとも1つの最小頂点カバーがある場合、そのセット内の残りの頂点は、$ V $に隣接する頂点以外のすべての頂点をカバーしますが、$ | C '| $は$ | C | -1 $より大きくないので、これを行うにはVIPエッジを含む最小の頂点カバーが存在しないことを意味する。

Answer 2

ハンガリーアルゴリズムを使用して初期マッチングを計算し、その頂点で終了するすべてのエッジの重みを小さくします。