📂グラフ理論

フルーリーのアルゴリズムの証明

定義 ¹

$G$をオイラーグラフとしよう。すると次の方法でオイラートレイルを作ることができる。

任意の頂点$u$から始め、次の二つのルールに従ってトレイルを作る:

• (i): 既に通ったエッジは消す。エッジが消えることによって孤立頂点になる場合、その頂点も消す。
• (ii): 各ステップで橋は他に選択肢がない場合にのみ渡る。

---

• エッジ$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$でなければならない。

■