私はアルゴリズムを見つけたようですが、それを理解するのに苦労しています.アルゴリズムの一般的な概要を知っている人がいるかどうか疑問に思っていました.
2ページで見つけたアルゴリズムへのリンクは次のとおりです
質問する
14333 次
2 に答える
11
アルゴリズムは次のように単純です。
- 一致しない頂点を見つけ、最小頂点カバーに含まれていないものとしてマークします。
- この頂点のすべての一致した隣接を、最小頂点カバーに含まれているものとしてマークします。
- 前のステップの頂点のすべての合致を一致しない頂点として扱い、ステップ 1 を繰り返します。
- 再帰が終了した場合は、手順 1 から繰り返します (グラフの複数の連結要素の場合)。
- 一致しない頂点がない場合は、残りのすべてのペアを取り、好きなようにマークします (ペアの 1 つの頂点が最小頂点カバーに含まれている必要があり、他の 1 つは含まれていない必要があることに注意してください)。
于 2015-11-01T21:56:51.350 に答える
-4
まず、2 部グラフ、頂点の 2 つのセット、およびエッジを理解する必要があります。
次に、すべてのエッジをカバーするために、2 つのセットからいくつかの頂点を選択する必要があります。1 つの頂点が選択されている限り、それにリンクするすべてのエッジがカバーされます。ここでのタスクは、頂点の最小数を選択して、すべてのエッジをカバーすることです。
原則は、必要な最小数が最大一致ペアの数に等しいことを意味します。
于 2012-09-16T19:01:40.000 に答える