2部グラフ

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

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

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

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

性質

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

外部リンク

『二部グラフの最大マッチングと増加道』 - 高校数学の美しい物語

表話編歴グラフ理論
要素・定義・表現	頂点辺（英語版）グラフ無向有向ラベル付き（英語版）重み付き（英語版）ハイパーグラフ接続行列隣接行列隣接リスト
指標	位数（英語版）サイズ（英語版）次数次数行列距離（英語版）半径直径内周 (頂点)彩色数辺彩色数（英語版）点連結度辺連結度交叉数（英語版）
部分構造	ループ（英語版）多重辺（英語版）部分グラフ（英語版）誘導部分グラフ道閉道連結成分（英語版）強連結成分（英語版）橋（英語版）カットクリーク独立集合支配集合（英語版）マッチングオイラー路シュタイナー木全域木ハミルトン路
全体構造	連結グラフ正則グラフ立方体グラフケージ強正則グラフ木平面グラフ 2部グラフ有向非巡回グラフ弦グラフムーアグラフパーフェクトグラフ対称グラフ半対称グラフ頂点推移グラフ辺推移グラフ距離推移グラフ補グラフ双対グラフグラフ同型
固有名を持つグラフ	パスグラフ（英語版） $P n$ 閉路グラフ $C n$ 完全グラフ $K n$ 完全2部グラフ $K m, n$ スター $S n = K 1, n$ 車輪グラフ $W n$ 空グラフピーターセングラフヒーウッドグラフマギーグラフホフマンシングルトングラフフォークマングラフ
トピック・定理	一筆書きオイラーの多面体定理クラトフスキの定理四色定理五色定理ケイリーの公式プリューファー列最短経路問題巡回セールスマン問題中国人郵便配達問題ダイクストラ法ベルマン-フォード法ワーシャル-フロイド法ハミルトン閉路問題最大クリーク問題頂点被覆問題最小頂点被覆問題最大独立集合問題最大流最小カット定理支配集合問題次数直径問題安定結婚問題
カテゴリ / コモンズ

性質

関連項目

外部リンク