2部グラフ

2部グラフとは

数学、特にグラフ理論において、2部グラフ（bipartite graph）とは、グラフの頂点集合を二つのグループ（独立集合）に分割し、それぞれのグループ内の頂点同士が隣接しないようにできるグラフのことを指します。

独立集合とn部グラフ

一般に、互いに隣接しない頂点の集合を独立集合と呼びます。グラフの頂点集合を n 個の独立集合に分割できるグラフを n部グラフ (n-partite graph) といいます。2部グラフは、n = 2 の場合の特殊なケースです。

完全2部グラフ

頂点集合が二つの独立集合 V1 と V2 に分割されたとき、V1 の任意の頂点と V2 の任意の頂点が隣接するグラフを 完全2部グラフ といいます。V1 が m 個の頂点を持ち、V2 が n 個の頂点を持つ完全2部グラフは、K_m,n と表記されます。

2部グラフと彩色

グラフの彩色とは、辺を共有する頂点（または、頂点を共有する辺）に異なる色を塗る操作を指します。

頂点彩色: 隣り合う頂点に異なる色を塗ること。n 部グラフは n 彩色可能なグラフです。
辺彩色: 隣り合う辺に異なる色を塗ること。

2部グラフのマッチング

2部グラフの辺集合において、どの二つの辺も互いに頂点を共有しないとき、その辺集合をマッチングと呼びます。マッチングの中でも特に、辺の数が最大のマッチングを 最大マッチング といいます。さらに、グラフ内のすべての頂点がマッチングに含まれる辺の端点になっているとき、そのマッチングを 完全マッチング といいます。

マッチングの重要性

マッチングは、様々な組み合わせ最適化問題を解決する上で重要な概念です。特に2部グラフのマッチング問題は、効率的なアルゴリズムが存在するため、多くの実用的な問題に応用されています。

2部グラフの性質

最大マッチング: 2部グラフの最大マッチングは、多項式時間で効率的に求めることができます。この計算には、最大フロー問題のアルゴリズムが利用されます。
木: すべての木構造は2部グラフです。これは、木の頂点を2つのグループに分け、隣り合う頂点が異なるグループに属するようにできるためです。
閉路グラフ: 閉路グラフは、頂点の数が偶数である場合に限り2部グラフとなります。頂点数が奇数の閉路グラフでは、2つの独立集合に分割することができません。
ケーニグの定理: 2部グラフにおいて、最大マッチングの辺の数（最大マッチングのサイズ）は、最小点被覆（すべての辺をカバーする最小の頂点集合）の点数と等しいという定理です。

関連事項

ホールの定理: 2部グラフにおいて、完全マッチングが存在するための条件を記述した定理です。
DM分解: 2部グラフの構造解析に使われる分解手法です。

参考文献

* 二部グラフの最大マッチングと増加道


2部グラフは、その単純な構造にもかかわらず、数学やコンピュータサイエンスの様々な分野で重要な役割を果たしています。

もう一度検索