二部グラフとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 二部グラフの意味・解説 

2部グラフ

(二部グラフ から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/05/24 19:12 UTC 版)

2部グラフの例
完全2部グラフ K3, 3

数学、特にグラフ理論における2部グラフ(にぶグラフ、: bipartite graph)とは、頂点集合を2つに分割して各部分の頂点は互いに隣接しないようにできるグラフのことである。一般に互いに隣接しない頂点からなる集合を独立集合といい、頂点集合を n 個の独立集合に分割可能なグラフのことを n 部グラフ (n-partite graph) という。

頂点集合を独立集合 V1, V2 に分割したとき、V1V2 の任意の頂点が隣接するグラフを完全2部グラフという。頂点集合が m 頂点とn 頂点に分割される完全2部グラフを Km,n と書く。

辺を共有する頂点を異なる色で塗ることを(頂点)彩色という。よって、n 部グラフは n 彩色可能なグラフに他ならない。同様に、頂点を共有する辺を異なる色で塗ることを辺彩色という。

2部グラフの辺集合はどの2辺も互いに隣接していないときマッチングと呼ばれる。辺の数が最大のマッチングを最大マッチングと呼ぶ。また、すべての頂点がマッチングに含まれる辺の端点であるとき完全マッチングと呼ぶ。

性質

  • 2部グラフの最大マッチングは多項式時間で求められる。最大フロー問題を参照。
  • は2部グラフである。
  • 閉路グラフは頂点が偶数個のときに限り2部グラフである。
  • Königの定理:2部グラフにおいて、最大マッチングの辺数は最小点被覆の点数と等しい。

関連項目

外部リンク




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「二部グラフ」の関連用語

二部グラフのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



二部グラフのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの2部グラフ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS