0

私は単純なグラフでそれを読みました |最小限の頂点カバー| <= 2*|最大一致|。

ここにグラフショーを考えてみましょう:-

グラフ

ここで、最小の頂点カバーは {B,C,D,E} で、サイズは 4 で、最大一致のサイズはちょうど 1 です。したがって、4>2*1 であり、プロパティは満足していないようです。

誰かがこれで私を助けることができますか?

4

0 に答える 0