分野: グラフ理論


組み合わせの良問です。JJMO(日本ジュニア数学オリンピック)の組み合わせの問題はJMOの対策にもなります。

証明だけでなく,考え方や重要なテクニックも紹介します。


Hall(ホール)の結婚定理:頂点集合が $U,\:V$ と分割された二部グラフ $G$ に対して,以下は同値。
条件1:$U$ の頂点を全てカバーするマッチングが存在する
条件2(Hallの条件):任意の $U$ の部分集合 $A$ に対して,$|A|\leq |\Gamma(A)|$

ただし,$\Gamma(A)$ は $A$ と辺でつながっている頂点の集合。


点(母点)がいくつか与えられたとき,どの点に一番近いかによって平面を分割したものをボロノイ図(Voronoi diagram)と言う。

三つ目の性質&その証明が美しいのでおすすめです。


この記事ではグラフ探索の二つの考え方「深さ優先探索」「幅優先探索」について解説します。非常に基本的なグラフアルゴリズムです。