graph-algorithm - 二部グラフの検出

Question

私は二部グラフを検出するアルゴリズムを作成していますが、私のアルゴリズムはそう言っていますが、二部グラフとしてカウントされるかどうかわからないグラフを考えました。

グラフは次のようになります

(A)--(B)

(C)

したがって、これには 3 つのノードがありますが、 と の間にのみエッジが 1 つAありBます。これは実際に二部構成ですか？

Answer 1

はい、サンプル グラフは本当に 2 部構成です。

たとえば、導入文で述べているウィキペディアの記事を参照してください...

グラフ理論の数学的分野では、2 部グラフ (バイグラフ) は、頂点が 2 つの互いに素なセット U と V に分割できるグラフであり、すべてのエッジが U の頂点を V の頂点に接続します。つまり、U と V はそれぞれ独立したセットです。同様に、二部グラフは奇数長のサイクルを含まないグラフです。

このグラフを分割するには 2 つの方法 ("{A,C}, {B}" または "{B,C}, {A}") があり、2 部グラフに必要な条件を満たします。

二部グラフが連結グラフである必要はありません。