グラフ理論における二分化を理解する

グラフ理論では、グラフの二分割とは、すべてのエッジが異なる部分セットの頂点を接続するように、頂点セットを 2 つの素なセット (部分セットと呼ばれる) に分割することです。言い換えれば、同じ部分集合内の頂点間にエッジはありません。たとえば、4 つの頂点 {a,b,c,d} を持つグラフを考え、頂点集合を 2 つの部分 ({a,b} と {a,b}) に分割します。 {CD}。すべてのエッジが異なる部分の頂点を接続しているため、グラフは二部構成になっています。二部構成を使用すると、グラフの走査、最短経路の検索、グラフのマッチングなどのグラフの問題のアルゴリズムの複雑さを軽減できます。