グラフ理論

オイラーの多面体定理：

任意の（穴のない）多面体において，頂点の数を $V$, 辺の数を $E$, 面の数を $F$ とおくと，$V-E+F=2$ が成立する。

一筆書きの条件：

連結なグラフにおいて，

オイラーグラフ⇔全ての頂点の次数が偶数

準オイラーグラフ⇔次数が奇数であるものがちょうど2つ

Hall（ホール）の結婚定理：頂点集合が $U,\:V$ と分割された二部グラフ $G$ に対して，以下は同値。

条件1：$U$ の頂点を全てカバーするマッチングが存在する

条件2（Hallの条件）：任意の $U$ の部分集合 $A$ に対して，$|A|\leq |\Gamma(A)|$

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

完全グラフ $K_5$ および完全二部グラフ $K_{3,3}$ は平面的グラフでない（平面に交差なしで書けない）。

Gale-Shapleyアルゴリズムを用いて安定マッチングを求めることができる。

グラフが与えられたときに要素数最大のマッチングを求める問題を最大マッチング問題と言う。

四色定理

任意の地図は四色で塗り分けることができる。

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

深さ優先探索とは「とにかく行けるとこまで行ってそれ以上進めなくなったら一歩戻ってそこから探索する」という探索方法。

幅優先探索とは「出発点に近い点から順に探索する」という探索方法。

深さ優先探索を2回すれば強連結成分分解できる。