無向グラフを2色のみで色付けできるかどうかを調べる

Question

無向グラフを2色のみで色付けできるかどうかについてのヒントはありますか？ これをJavaでどのように実装できますか？

Answer 1

breadth-first searchをグラフ上に表示します。すべての偶数の深さでノードを1色、たとえば赤色に、奇数深度にノードの色を青色にします。ツリー以外のエッジ（2つのノード間のエッジ）を使用するたびに、色が異なることを確認します。グラフに複数のコンポーネントが接続されている場合は、各コンポーネントの検索を繰り返すだけです。

Answer 2

グラフが2部構成であるかどうかを判断するのと同じです。これを行うには、奇数長のサイクルがグラフに存在するかどうかをチェックする必要があります。そのために、グラフの幅優先探索を行います。 BFS内のどのレベルでも、同じレベルのノード間にエッジがある場合、グラフは二部構成ではなく、つまり、2つの色のみを使用して色付けすることはできません。 （隣接ノードが異なる色でなければならないという制約があると仮定して）