4.7. オイラー歩道とオイラー回路
無向多重グラフのオイラー歩道とオイラー回路は第 3.4 節で学んだ。多重有向グラフでも同様の概念を定義しよう:
\(D\) を多重有向グラフとする。
-
\(D\) のオイラー歩道 (Eulerian walk) とは、\(D\) の全ての弧をちょうど一度ずつ含む歩道を意味する。
-
\(D\) のオイラー回路 (Eulerian circuit) とは、オイラー歩道である回路 (つまり閉歩道) を意味する。
Euler–Hierholzer の定理 (定理 3.4.4) は多重グラフがオイラー歩道およびオイラー回路を持つための必要十分条件を示す。多重有向グラフでも同様の結果が知られている:
\(D\) を弱連結な多重有向グラフとする。このとき:
-
多重有向グラフ \(D\) がオイラー回路を持つのは、\(D\) の任意の頂点 \(v\) が \(\deg^{+}v=\deg^{-}v\) を満たすとき、かつそのときに限る。
-
多重有向グラフ \(D\) がオイラー歩道を持つのは、特定の二つを除く全ての \(D\) の頂点 \(v\) で \(\deg^{+}v=\deg^{-}v\) が成り立ち、除かれた二つの頂点 \(v\) で \(\left\vert \deg^{+}v-\deg^{-}v\right\vert \leq1\) が成り立つとき、かつそのときに限る。
定理 4.7.2 を証明せよ。
ちなみに、「任意の頂点 \(v\) で \(\deg ^{+}v=\deg^{-}v\) が成り立つ」には名前が付いている:
\(D\) を多重有向グラフとする。\(D\) の任意の頂点 \(v\) が \(\deg^{+}v=\deg^{-}v\) を満たすとき、\(D\) は平衡 (balanced) と言う。
つまり平衡であることは弱連結な多重有向グラフにオイラー回路が存在するための必要十分条件である。
次の命題は容易に分かる:
\(G\) を多重グラフとする。\(G^{\operatorname*{bidir}}\) は平衡である。
\(G^{\operatorname*{bidir}}\) の定義より、\(G^{\operatorname*{bidir}}\) の各頂点 \(v\) が \(\deg^{+}v=\deg v\) および \(\deg^{-}v=\deg v\) を満たす。ここで \(\deg v\) は \(G\) の頂点としての \(v\) の次数を表す。よって \(G^{\operatorname*{bidir}}\) の任意の頂点 \(v\) は \(\deg^{+}v=\deg v=\deg ^{-}v\) を満たす。言い換えれば \(G^{\operatorname*{bidir}}\) は平衡である。□
この命題と定理 4.7.2 (a) を組み合わせると、無向 (！) 多重グラフに関する興味深い事実が得られる:
\(G\) を連結な多重グラフとするとき、多重有向グラフ \(G^{\operatorname*{bidir}}\) はオイラー回路を持つ。言い換えれば、\(G\) の各辺をちょうど二度 (各方向に一度) ずつ含む \(G\) の回路が常に存在する。
命題 4.7.4 より多重有向グラフ \(G^{\operatorname*{bidir}}\) は平衡だと分かり、\(G\) の連結性から \(G^{\operatorname*{bidir}}\) は弱連結だと分かる。よって定理 4.7.2 (a) より \(D=G^{\operatorname*{bidir}}\) はオイラー回路を持つ。このオイラー回路を \(G\) の回路として解釈したものが定理の条件を満たす。□