グラフと一筆書き(その 3) - Red cat の数学よもやま話

オイラー・グラフと半オイラー・グラフ

さて、グラフ G は連結であるとします(連結の定義は既に述べました)。
このとき、G の全ての辺を含むような閉じた小道があれば、G をオイラー・グラフ(Eulerian graph)と言います。また、そのような小道をオイラー小道(Eulerian trail)と言います。
また、オイラー・グラフでないグラフ G で、やはり全ての辺を含む小道があるグラフを半オイラー・グラフ(semi-Eulerian graph)と言います。
小道の定義から、オイラー小道は G の全ての辺をちょうど一個ずつだけ含んでいます。半オイラー・グラフの場合も同様です。
すなわち、オイラー・グラフと半オイラー・グラフはまさしく「一筆書きが可能」なグラフ、ということになります。
では、どんなグラフがオイラー・グラフ、あるいは半オイラー・グラフになるのか ? その種明かしはもう少し後にして、一つ定義をしておきます。

「通過する」とは ?

グラフ G の頂点 $v\in V$ に対して
$\varphi(e_0)=[v_0,v],\varphi(e_1)=[v_1,v]$
を満たす辺 $e_0,e_1\in E(e_0\neq e_1)$ があるとき、 $v_0\to v\to v_1$ なる小道ができます。ある歩道がこのような小道を含むとき、歩道は v を通過する、と定義しておきます。