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

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