この用語はまだ監査を通っていません（未確認）。
二部グラフ
にぶぐらふ ／ 2部グラフ 1対1で対応bipartite graph
名詞 ・書き言葉・答案
定義
頂点全体を 2 つの組に分けて、どの辺も異なる組の頂点どうしを結ぶようにできるグラフのこと。
A graph whose vertices can be split into two sets so that every edge joins a vertex in one set to a vertex in the other.
例文
話し言葉 A bipartite graph is one you can color with just two colors, so no edge ever joins two vertices of the same color. 二部グラフは 2 色だけで塗り分けられるグラフで、同じ色の頂点どうしを結ぶ辺が 1 本もない。
書き言葉・答案 Show that a bipartite graph cannot contain a cycle of odd length. 二部グラフは長さが奇数の閉路を含まないことを示せ。
言い間違えやすいところ
- 「頂点を 2 色で塗り分けられる」「長さが奇数の閉路をもたない」は、どちらも二部グラフであることと同値。
- 一方の組の m 個の頂点と他方の組の n 個の頂点がすべて辺で結ばれたものを complete bipartite graph（完全二部グラフ）といい、Kₘ,ₙ と書く。
- 用例コーパスでは話し言葉は少なく（MIT OCW）、書き言葉はすべて MIT の講義ノート。Levin の本では 37 件（2.7 Matching in Bipartite Graphs 15 ほか）。