【グラフ理論】 オイラーグラフについて

オイラーグラフ」という考え方は,「中国人郵便配達問題」を考える際に重要になってくる.
中国人郵便配達問題とは, 正の重み付き無向グラフについて, 重みの和が最小となる閉路(閉じた道)を求める問題である.

まずはオイラーグラフについて考える.
オイラーグラフの定義は, "オイラー回路を持つグラフ"である.
では, オイラー回路とは, "すべての辺を含む回路" である.
また, オイラー小道とは, "すべての辺を含む閉じていない(始点 \neq終点)の小道"である.

定理2.1
Gを連結で位数が2以上のグラフとする.
Gがオイラーグラフである  \Leftrightarrow Gの全ての点の次数が偶数

証明:
「Gがオイラーグラフ→Gの全ての点の次数が偶数」の証明
Gはオイラーグラフであるので定義より, Gはオイラー回路を持つ. すなわち全ての辺を含む回路を持つ.
各点は, 出る辺と入る辺(日本語おかしい)の2本ずつカウントされるので, 次数は偶数.

「Gがオイラーグラフ←Gの全ての点の次数が偶数」の証明
Gは連結で位数が2以上であるので定理1.9より, Gには閉路Cが存在する.
(i)閉路Cが, Gの全ての辺を含んでいるとき. E(C) = E(G)
これはGにおけるオイラー回路である.
(ii) 閉路Cが, Gの全ての辺を含んでいないとき, すなわちE(C)  \in E(G)
GからCを除いたHを考える. このCの各点の次数は偶数なので, Hの各点も偶数になる.
これを再帰的に, 言えれば良い. (省略)
f:id:umashika5555:20180903212959p:plain

これを言い換えると
系2.2
Gを連結, 位数2以上のグラフ
Gがオイラーグラフ \LeftrightarrowE(G)が互いに素な閉路に分割できる


系2.3
Gを連結, 位数2以上のグラフ
Gがオイラー小道をもつ \LeftrightarrowGの奇点の個数が2

説明:
奇点となるのは始点と終点の2点.
始点は偶数個+出, 終点は偶数個+入の奇数個となる.

証明:
「Gがオイラー小道をもつ→Gの奇点の個数が2」の証明
オイラー小道Pの始点と終点以外は入と出で辺を2本カウントするので偶点.
始点は偶数+出, 終点は偶数+入のみ
「Gがオイラー小道をもつ←Gの奇点の個数が2」の証明
始点uと終点vを結ぶ辺eをGに加えてグラフG+eを考える.
G+eは全ての点が偶点 \LeftrightarrowグラフG+eはオイラーグラフ \Leftrightarrowオイラー回路Wが存在する
uを始点としてeをまずたどりオイラー閉路Wを作る.
f:id:umashika5555:20180903231554p:plain
赤はオイラー回路
これを W: u, v, w_1, w_2, ..., w_k, u と表せる.
ここで v, w_1, w_2, ..., w_k, uはGのオイラー小道である.


参考: