2部グラフとは

auです。

アルゴリズムで2部グラフについて学んだので、軽くまとめたいと思います。

2部グラフとは

2部グラフとは、AとBの点集合があり、辺は同じ点集合には存在していないようなグラフを指します。以下の図だと分かりにくいですが、AからBへの有向グラフとなっているため、BからAへはフローは流れません。

こんな感じ

完全有効2部グラフとなると、AのノードがBのノードへの辺が全て存在するグラフを指します。