オイラー路とオイラー閉路の解説
鉛筆を離さず、同じ線を二度なぞらずに一筆で描ける図形もあれば、どれだけ試しても描けない図形もあります。試す必要はありません。各角に集まる線を数えてください。線の本数が奇数の角が二つ以下なら、その図形は描けます。そして筆はその角で始まり、その角で終わらなければなりません。レオンハルト・オイラーは1736年にこの規則を見つけ、それによってグラフ理論を打ち立てました。
ケーニヒスベルクの七つの橋
プロイセンの都市ケーニヒスベルク、今日のカリーニングラードは、プレーゲル川の両岸と川の中の二つの島、クナイプホーフとロムゼにまたがっていました。七つの橋が四つの部分を結んでいました。クナイプホーフから各岸へ二つずつ、二つの島の間に一つ、ロムゼから各岸へ一つずつです。市民たちは、各橋をちょうど一度ずつ渡る散歩ができるだろうかと考えました。オイラーは1735年にサンクトペテルブルクの科学アカデミーへ提出し1741年に印刷された論文で答えました。できない、と。決定的な一歩は、町の部分とその間の橋以外をすべて捨て去ることでした。これはまさにグラフのすることです。陸地ごとに頂点を一つ、橋ごとに辺を一本、同じ場所どうしを二つの橋が結ぶところは辺を二本にします。
次数の規則
頂点の次数とは、そこに集まる辺の本数です。頂点を通り抜ける筆は一本の辺から入り、別の辺から出ていくので、その頂点の辺を対にして使います。相手のない辺を残せるのは、筆の最初の頂点と最後の頂点だけです。ですから次数が奇数の頂点は、筆の始まりか終わりでなければなりません。クナイプホーフには橋が五つ、ほかの三つの部分には三つずつ。奇数頂点が四つあり、二つ多すぎました。一般に、連結なグラフは、すべての次数が偶数ならオイラー閉路、つまり始めた場所で終わる筆を持ち、次数が奇数の頂点がちょうど二つなら、一方から他方へのオイラー路を持ちます。奇数頂点の個数が1になることも、ほかの奇数になることもありません。どの辺も次数の総和に2を加えるので、総和は偶数だからです。これにもオイラーは気づいており、今日では握手補題と呼ばれます。
なぜこの規則で十分なのか
オイラーは奇数頂点が三つ以上の図形は描けないことを示し、ほかの連結な図形はすべて描けると、証明なしに述べました。証明したのはドイツの数学者カール・ヒエルホルツァーで、1871年に若くして亡くなり、論文は1873年に世に出ました。奇数頂点があればそこから、なければどこからでも始め、使っていない辺をたどれるだけたどります。ほかの頂点はすべて次数が偶数なので、行き止まりになるのは終点の頂点だけです。辺が残っていれば、図形は連結ですから、そのいくつかはここまでの道筋に触れています。そうした頂点から再び行き止まりまで進むと、今度はその頂点に戻って止まるので、そこで輪を道筋に組み込みます。辺がなくなるまで繰り返します。この証明はそのまま最も速いアルゴリズムでもあります。各辺を見る回数は決まっているからです。
フルーリーのアルゴリズム:橋を焼かないこと
描ける図形でも、一筆は失敗しえます。一本の辺で結ばれた二つの三角形を考え、最初の三角形の角から始めてみてください。最初の三角形を描き終える前に二つ目へ渡ってしまうと、もう戻れません。その結ぶ辺が橋です。取り除けば図形は二つに分かれます。1883年のフルーリーのアルゴリズムは一つの規則を与えます。各頂点では、残りの辺にとって橋ではない辺を選ぶ。ほかに辺がない場合は別、というものです。これに従えば必ず描き終えられます。橋かどうかの判定には時間がかかるので、フルーリーのアルゴリズムはヒエルホルツァーのものより遅いのですが、鉛筆を持って自分でたどれるのはこちらで、アプリのヒントもこれを使っています。
図形を直す
奇数頂点が k 個の図形には k/2 筆必要です。一筆で描くには、奇数頂点を二つずつ結ぶ辺を足します。新しい辺は一本ごとに二つの奇数頂点を偶数にします。k/2 − 1 本足すと奇数頂点が二つ残って路になり、k/2 本足すと一つも残らず閉路になります。ケーニヒスベルクでも、四つの部分のどれか二つの間に橋をもう一つ架けていれば散歩は可能になり、二つ架けていれば一周もできました。歴史も似たことをしました。二つの橋が第二次世界大戦で失われ、二つは近代的な道路に置き換えられ、今日昔の場所に架かる五つの橋は、一方の島からもう一方の島へ、一度ずつ渡れます。
通り数を数える
ニコラウスの家は、対角線を両方引いた正方形に屋根を載せた形で、このパズルのドイツの子ども向けの姿です。「Das ist das Haus vom Ni-ko-laus」は八音節で、線一本に一音節ずつ当たります。下側の二つの角だけが奇数頂点で、それぞれからちょうど44通り、合わせて88通りの描き方があります。有向グラフなら、オイラー閉路の個数にはド・ブラン、ファン・アールデンネ=エーレンフェスト、スミス、タットの名を冠したBEST定理という公式があります。ふつうのグラフにはそうした公式が知られておらず、数えること自体が一般には難しいと考えられているので、このアプリは小さな図形についてすべての描き方を試し、図形を二つに分けてしまう手は飛ばして数えます。
オイラー路の使われ方
除雪車も清掃車も郵便配達員も、各通りを一度ずつ通って戻りたいものです。どの交差点でも通りの数が偶数なら、オイラー閉路で済みます。そうでなければ二度通る通りが出てきて、費用が最も小さい組み合わせを選ぶのが中国人郵便配達員問題です。1962年に管梅谷が提起しました。ペンプロッターやレーザーカッターも、ペンを上げずにできるだけ多くの線を引くことで時間を節約します。ゲノム解読では、各断片を辺とするド・ブラン・グラフの中にオイラー路を探すことで、何百万もの短いDNA断片をつなぎ合わせます。そして同じ規則は、パズル本のどの線画なら試す価値があるかも教えてくれます。
試してみる
オイラー路ファインダーを開けば、1736年と現在のケーニヒスベルクから、星、入れ子の正方形、立方体まで、十二の図形を自分でなぞれます。平行な辺を使って自分の図形を描くこともできます。奇数頂点は塗りつぶされ、各頂点は自分の次数を示し、図形の下の次数の規則が何が可能か、どの辺を足せば図形が直るかを伝えます。行き詰まったときは、始めた頂点が違ったのか、橋を早く渡ってしまったのか、そしてそれが何手目だったかをアプリが教えます。ヒントは安全な辺を示し、解くはフルーリーのアルゴリズムで橋の判定を見せながら、またはヒエルホルツァーのアルゴリズムで小周回の組み込みを見せながら、図形を描きます。
よくある質問
オイラー路とハミルトン路は同じものですか。
違います。オイラー路は各辺を一度ずつ使い、同じ頂点を何度通ってもかまいません。ハミルトン路は各頂点を一度ずつ通り、すべての辺を使う必要はありません。グラフにオイラー路があるかどうかは奇数頂点を数えればすぐ分かりますが、ハミルトン路には速い判定法が知られておらず、一本見つけることは計算機科学の古典的な難問の一つです。
二つの頂点が複数の辺で結ばれていても、次数の規則は成り立ちますか。
成り立ちます。どの辺も両端の次数に数えられ、同じ二つの頂点を別の辺が結んでいるかどうかは関係ありません。ケーニヒスベルクはまさにそうした多重グラフで、クナイプホーフと各岸は二つの橋で結ばれています。頂点から自分自身へ戻る辺、すなわちループは次数に2を加えるので、偶奇を変えることはありません。
一方通行の道路の場合はどうなりますか。
有向グラフでは各辺に向きがあり、規則は各頂点に入る辺と出る辺を比べます。どの頂点でも入る辺と出る辺が同数で、辺がひとつながりならオイラー閉路があります。ある頂点で出る辺が一本多く、別の頂点で入る辺が一本多く、ほかはすべて釣り合っていればオイラー路があり、その路は前者から後者へ進みます。
奇数頂点がちょうど一つの図形はありえますか。
ありえません。すべての頂点の次数を足すと辺の本数の二倍になります。どの辺にも端が二つあるからです。この和は偶数なので、その中の奇数の次数の個数も偶数でなければなりません。0、2、4 と続き、1 や 3 になることはありません。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
オイラー路ファインダーを開く