2部グラフ
2007年7月12日 (木) 23:52時点における122.17.2.240 (トーク)による版 (新しいページ: '【にぶぐらふ (bipartite graph)】 グラフ$G$の点集合$V$のある2分割$\{U,W\}$が存在して, 各枝が$U$の点と$W$の点を結ぶとき, このグラフ$G$...')
【にぶぐらふ (bipartite graph)】
グラフ$G$の点集合$V$のある2分割$\{U,W\}$が存在して, 各枝が$U$の点と$W$の点を結ぶとき, このグラフ$G$を2部グラフという. $U$と$W$の点の数がそれぞれ$m$と$n$であって, $U$の各点と$W$の各点を結ぶ枝が丁度1本存在するとき, この2部グラフを完全2部グラフといい, ${\rm K}_{m,n}$のように表す.