この記事は 英語版の対応するページを翻訳することにより充実させることができます。(2024年5月)翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
- 英語版記事を日本語へ機械翻訳したバージョン(Google翻訳)。
- 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。
- 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。
- 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。
- 翻訳後、
{{翻訳告知|en|Bipartite graph|…}} をノートに追加することもできます。
- Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。
|
数学、特にグラフ理論における2部グラフ(にぶグラフ、英: bipartite graph)とは、頂点集合を2つに分割して各部分の頂点は互いに隣接しないようにできるグラフのことである。一般に互いに隣接しない頂点からなる集合を独立集合といい、頂点集合を n 個の独立集合に分割可能なグラフのことを n 部グラフ (n-partite graph) という。
2部グラフの例
完全2部グラフ K3, 3
頂点集合を独立集合 V1, V2 に分割したとき、V1 と V2 の任意の頂点が隣接するグラフを完全2部グラフという。頂点集合が m 頂点とn 頂点に分割される完全2部グラフを Km,n と書く。
辺を共有する頂点を異なる色で塗ることを(頂点)彩色という。よって、n 部グラフは n 彩色可能なグラフに他ならない。同様に、頂点を共有する辺を異なる色で塗ることを辺彩色という。
2部グラフの辺集合はどの2辺も互いに隣接していないときマッチングと呼ばれる。辺の数が最大のマッチングを最大マッチングと呼ぶ。また、すべての頂点がマッチングに含まれる辺の端点であるとき完全マッチングと呼ぶ。
- 2部グラフの最大マッチングは多項式時間で求められる。最大フロー問題を参照。
- 木は2部グラフである。
- 閉路グラフは頂点が偶数個のときに限り2部グラフである。
- Königの定理:2部グラフにおいて、最大マッチングの辺数は最小点被覆の点数と等しい。
関連項目
編集
外部リンク
編集