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

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

[Thm] 平面上に()個の点が与えられたとき、最短距離は個より多くは起こりえない。 (証明) 最短距離をとおく。 点の個数のグラフGを次のように定める。 「Gの頂点集合をとする。また2点,間の距離がのときに限りそれら2点を結ぶ。この操作により得られた線分の…

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

凸包の定義 点集合Pの凸包とは、Pの点を全て含む極小の凸集合のことである。 (イメージ的にはPの各点を板に打ち付けた釘とみなした時、全ての釘を含むように外側から輪ゴムを掛けてできる凸多角形がPの凸包である。) 定理: 平面上にn個の点(n≧3)が与えられた…