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

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

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

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

2部グラフの最大マッチングは多項式時間で求められる。最大フロー問題を参照。

木は2部グラフである。

閉路グラフは頂点が偶数個のときに限り2部グラフである。

Konigの定理：2部グラフにおいて、最大マッチングの辺数は最小点被覆の点数と等しい。

関連項目

ホールの定理

DM分解

外部リンク

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

表

話

編

歴
グラフ理論
要素・定義・表現

頂点

辺（英語版）

グラフ

無向

有向

ラベル付き（英語版）

重み付き（英語版）


ハイパーグラフ

接続行列

隣接行列

隣接リスト

指標

位数（英語版）

サイズ（英語版）

次数

次数行列

距離（英語版）

半径

直径


内周

(頂点)彩色数

辺彩色数（英語版）

点連結度

辺連結度

交叉数（英語版）

部分構造

ループ（英語版）

多重辺（英語版）

部分グラフ（英語版）

誘導部分グラフ


道

閉道


連結成分（英語版）

強連結成分（英語版）


橋（英語版）

カット

クリーク

独立集合

支配集合（英語版）

マッチング

オイラー路

シュタイナー木

全域木

ハミルトン路


全体構造

連結グラフ

正則グラフ

立方体グラフ

ケージ

強正則グラフ


木

平面グラフ

2部グラフ

有向非巡回グラフ

弦グラフ

ムーアグラフ

パーフェクトグラフ

対称グラフ

半対称グラフ


頂点推移グラフ

辺推移グラフ

距離推移グラフ

補グラフ

双対グラフ

グラフ同型

固有名を持つグラフ