フルーリーのアルゴリズムの証明
定義 1
$G$をオイラーグラフとしよう。すると次の方法でオイラートレイルを作ることができる。
任意の頂点$u$から始め、次の二つのルールに従ってトレイルを作る:
- エッジ$b \in G$が消えてグラフが分断される場合、$b$を橋と呼ぶ。
説明
オイラーグラフのオイラートレイルは定義によりその存在が保証されているが、オイラートレイルが具体的にどういうものかまでは分からない。フルーリのアルゴリズムは与えられたオイラーグラフからオイラートレイルを作り出す。
証明
オイラーグラフの同値条件:$G$を連結グラフとする。
$G$がオイラーグラフで、$G$の全ての頂点の次数が偶数であることは同値である。
トレイルが$u$から出て頂点$v$に入ると、そのエッジを消す。もし$v = u$ならば、$v \ne u$になるまでループする。$v \ne u$の場合、消されたサブグラフ$H$はまだ連結グラフであり、$u$と$v$の二つの頂点のみが奇数の次数を持つ。したがって、このような削除をもう一度行った時、$H$がまだ連結グラフであることを示さなければならない。ある頂点$w$に対して$H - vw$が連結グラフでないと仮定するならば、それは$u$を含まずに$w$を含む何らかのコンポーネント$K$が存在するということである。$K$の頂点$w$は次数が奇数であるため、$K$は奇数の次数を持つもう一つの頂点を持たなければならない。しかし、これは矛盾であるため、$H - vw$は連結グラフであることが保証される。つまり、このような削除を繰り返しても連結グラフのままであり、ルール(ii)によると、どのステップでも橋は最後にしか消せないため、トレイルの終点は$u$でなければならない。
■
Wilson. (1970). Introduction to Graph Theory: p33. ↩︎