グラフに最小エッジを追加して奇数グラフにする方法

Question

無向グラフが与えられ、最初に奇数サイクルになるようにエッジの数を最小限にする必要があります。これらのエッジは

Answer 1

1. すなわち、ブラックを使用して任意の点から出発して、白色用いて隣接する非塗装ノードをペイントと同様に、これらの白いノード上で動作され、黒と白の使用グラフを着色します。

2. エッジが同じ色のノードを持つかどうかを確認します。はいの場合は、すでに奇数サイクルが存在します。

3. それ以外の場合は、同じ色の2つのノードを接続すると奇数サイクルになります。つまり、ちょうど余分なエッジが1つ必要で、C（number_of_black_nodes、2）+ C（number_of_white_nodes、2）の方法があります。