[Def]近傍 グラフの任意の点集合に対して、のどれかの点に隣接する点の全体をにおけるの近傍と呼び、やと書く。 を2部分割を持つ2部グラフとするとき、の点がすべて飽和されるようなのマッチングを見つけることは応用上重要である。 [Thm]Hallの定理 を2部分…

単純無向グラフを考える。 [Def](マッチング) のどの2辺も互いに隣接しないとき、をのマッチングという。 マッチングに属する辺の両端点はでマッチングされているという。 点がマッチングに属する辺の端点のとき、はを飽和しているといい、を飽和点という。 …

[Def]平面グラフ グラフが平面グラフであるとは、辺が交わることなく平面(または2次元球面)上に描くことができるグラフのことである。 ■オイラーの公式■ Gが連結平面グラフで、個の頂点、個の辺、個の面を持てば、次の関係式が成り立つ。 [離散幾何でしばし…