一筆書き
奇数頂点
描いた辺
一筆書きの通り数

    • 奇数頂点が0個:どの頂点から出発してもそこへ戻る閉路
    • 奇数頂点が2個:一方から他方へ向かう路
    • 4個以上:一筆書きは不可能

    方法

    オイラー路とオイラー閉路について詳しく

    オイラー路ファインダー

    ニコラウスの家を、鉛筆を離さず、同じ線を二度なぞらずに描けるでしょうか。描けます。ただし下側の二つの角のどちらかから始めたときだけで、それぞれ44通りの描き方があります。理由は頂点の次数、つまりそこに集まる線の本数です。鉛筆は頂点を通り抜けるたびに、その頂点の線を二本使います。レオンハルト・オイラーは1736年、ケーニヒスベルクの七つの橋でこの規則を見つけました。自分で図形をなぞり、どこでなぜ行き詰まるかを確かめ、ヒントをもらい、あるいはアルゴリズムが描く様子をご覧ください。 図形を選んでなぞります。まず頂点をタップして始め、次に辺または次の頂点を順にタップするか、頂点から頂点へドラッグします。各辺は一度しか使えません。戻るは一手戻し、ヒントは次に安全な辺を示し、解くはフルーリーのアルゴリズムまたはヒエルホルツァーのアルゴリズムを一手ずつ再生します。奇数頂点は塗りつぶされ、各頂点のバッジはその次数です。描くモードでは、空いた場所をタップすると頂点が増え、二つの頂点をタップすると結ばれ、もう一度タップすると二本目の辺が加わります。頂点はドラッグで動かせます。消すは頂点と辺を取り除きます。奇数頂点が三つ以上あるときは、追加を押すと一筆書きできるようにする辺が入ります。

    使い方

    1. ケーニヒスベルクの七つの橋、ニコラウスの家、星などの図形を選ぶか、描くモードで自分の図形を描きます。二つの頂点の間に何本でも辺を引けます。
    2. 頂点をタップして始め、次に辺または頂点を順にタップするか、頂点から頂点へドラッグします。行き詰まったら、状態の行が理由を伝えます。戻るは一手戻し、ヒントは安全な辺を示します。
    3. 図形の下の次数の規則を読み、描けない図形には提案された辺を追加し、あるいは解くを押して、フルーリーまたはヒエルホルツァーのアルゴリズムが一手ずつ描く様子をご覧ください。

    なぜ奇数頂点が決め手になるのか

    頂点を通り抜ける筆は、一本の線から入って別の線から出ていきます。つまりその頂点の線を二本ずつ使います。線が相手なしで残れるのは、筆の始まりと終わりだけです。ですから線の本数が奇数の頂点は、始点か終点でなければなりません。奇数頂点がなければ筆は始めた場所で終わります。これがオイラー閉路です。二つあれば一方から他方へ進みます。これがオイラー路です。四つ以上あると一筆には端が多すぎ、奇数頂点が k 個なら k/2 筆必要です。ケーニヒスベルクには四つの陸地があり、橋の数は五、三、三、三。四つとも奇数なので、どの散歩でも各橋を一度ずつ渡ることはできませんでした。そのうち二つの間に橋を一つ新しく架ければ、散歩は可能になっていました。

    フルーリーとヒエルホルツァーのアルゴリズム

    図形が描けると知ることと、実際に描くことは別です。不用意な一筆は、まだ必要な線から自分を切り離してしまいます。1883年のフルーリーのアルゴリズムは一つの規則でこれを避けます。橋、つまり取り除くと残りの線が二つに分かれてしまう線は、ほかに線がない場合を除いて決して渡らない、という規則です。1873年に公表された論文によるヒエルホルツァーのアルゴリズムはもっと速く、まずどこへでも行き止まりになるまで進み(これは出発点でしか起きません)、次に周回上のまだ空いた線を持つ頂点から、もう一つ閉じた輪をたどって周回に組み込みます。時間は辺の本数に比例し、計算機はこの方法でオイラー路を見つけます。

    よくある質問

    オイラー路とオイラー閉路の違いは何ですか。

    どちらもグラフの各辺をちょうど一度ずつ使います。オイラー閉路は始めた場所で終わり、オイラー路は別の場所で終わります。連結なグラフは、すべての頂点の次数が偶数のとき閉路を持ち、次数が奇数の頂点がちょうど二つのとき路を持ちます。そのとき路は一方から他方へ進みます。

    ケーニヒスベルクの七つの橋を一度ずつ渡れないのはなぜですか。

    各陸地を頂点に、各橋を辺にして描きます。クナイプホーフ島には橋が五つ、ほかの三つの陸地には三つずつあったので、四つの頂点はすべて奇数です。散歩は奇数頂点でしか始まりも終わりもできず、四つでは多すぎます。そのうち二つの間に橋を一つ足せば奇数頂点は二つになり、散歩は可能になります。

    ニコラウスの家は何通りの描き方がありますか。

    下側の二つの角それぞれから44通り、合わせて88通りです。順序や向きが違えば別の描き方として数えています。ほかのどの頂点からも描けません。線の本数が奇数なのはこの二つの角だけだからです。このアプリは小さな図形の通り数をこのように数えます。

    グラフの橋とは何ですか。

    取り除くと連結なグラフが二つに分かれてしまう辺のことです。フルーリーのアルゴリズムは、ほかに選択肢があるかぎり、残りの辺にとっての橋を決して渡りません。渡れば図形の一部が取り残されるからです。このアプリでは、橋を早く渡ったせいで行き詰まった筆に、それが何手目だったかを伝えます。

    二つの頂点の間に複数の辺があってもよいですか。

    よいです。平行な辺を持つグラフは多重グラフと呼ばれ、ケーニヒスベルクにはそれが必要です。クナイプホーフと各岸を二つの橋が結んでいました。描くモードで二つの頂点をもう一度タップすると、その間に辺をもう一本、最大四本まで足せます。次数の規則は同じように働き、どの辺も数えます。

    試してみますか?

    ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

    エディターへ