エッジを削除してグラフを二分グラフにする（エッジ/ 2以上ではない） - アルゴリズム？

Question

だから、我々はグラフが与えられていると言うことができます（2つ以上のグラフ（元のグラフのエッジ）/ 2以上）を削除することが許可されます。

E={ (4, 1),(1 ,2), (2 ,3),(7, 2),(1 ,5),(8 ,4), (5 ,8),(8, 9)} 

と頂点の集合：1は、この問題を解決する必要がありますどのように

V= { 1,2,3,4,5,6,7,8} 

を

は、我々が与えられているとしましょうか？これを行うアルゴリズムはありますか？どんな種類の説明もありがたいです。

Answer 1

任意のノードをセットAの最初のメンバーとして選択します。ノードがリンクされている場合は、セットBの最初のメンバーとして1を選択します。そうでない場合は、他のノードをセットBの最初のメンバーとして選択します。

ここでは、ノードAとノードBの2つのセットがあります。どちらのセットにもないノードを繰り返し選択します。そのノードをAとBのノードにリンクする辺の数を数えます。それをセットAにリンクする辺がある場合は、それをセットBのノードにリンクする辺を消去し、集合Bに入れます。セットAのノードを削除し、セットAに入れます。そのノードにリンクされているエッジの半分以下を消去することに注意してください。