【にぶぐらふ (bipartite graph)】
グラフ G {\displaystyle G\,} の点集合 V {\displaystyle V\,} のある2分割 { U , W } {\displaystyle \{U,W\}\,} が存在して, 各枝が U {\displaystyle U\,} の点と W {\displaystyle W\,} の点を結ぶとき, このグラフ G {\displaystyle G\,} を2部グラフという. U {\displaystyle U\,} と W {\displaystyle W\,} の点の数がそれぞれ m {\displaystyle m\,} と n {\displaystyle n\,} であって, U {\displaystyle U\,} の各点と W {\displaystyle W\,} の各点を結ぶ枝が丁度1本存在するとき, この2部グラフを完全2部グラフといい, K m , n {\displaystyle {\rm {K}}_{m,n}\,} のように表す.
の点集合
のある2分割
が存在して, 各枝が
の点と
の点を結ぶとき, このグラフを2部グラフという. との点の数がそれぞれ
と
であって, の各点との各点を結ぶ枝が丁度1本存在するとき, この2部グラフを完全2部グラフといい, 
のように表す.