言語を変えてください

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

マシゴンにサインインする

または

新しいアカウント     パスワードを再設定する     

Untitled Course
前書き
ケーニヒスベルクの橋
握手とデート
平面グラフ
マップのカラーリング
巡回セールスマン問題
問題のスケジュール
日常生活のグラフ

シェア

進行状況をリセット

これにより、このコースのすべてのチャプターの進行状況とチャットデータが削除され、元に戻すことはできません。

用語集

左側のキーワードの1つを選択…

Untitled Courseケーニヒスベルクの橋

読書の時間: ~15 min

グラフとネットワークについて考える最初の数学者の一人は、 レオンハルトオイラーでした。オイラーは、バルト海の近くのケーニヒスベルクの町に関する古い問題に興味をそそられました。

プレゲル川は、ケーニヒスベルクを4つの部分に分け、7つの橋でつながっています。すべての橋を渡る街を正確に1度だけ歩くことはできますか。 （どこでも開始および終了できますが、必ずしも同じ場所である必要はありません。）

これらの地図を描いて、有効なルートを見つけてください。

Map 1

Map 2

Map 3

Map 4

ケーニヒスベルクの場合、有効なルートを見つけるのは不可能のようですが、他のいくつかの都市は機能しています。オイラーは、グラフ理論を使用して、多くの可能性を試さなくても、どの都市にも適用できる簡単なルールを見つけることができました。

まず、都市マップをエッジと頂点を持つグラフに変換する必要があります。すべての島または土地の領域は表されと2つのリージョンを接続するすべてのブリッジは、対応する表され 。

現在、「すべての橋を1度だけ通過しながら都市をツアーする」という問題は、「すべてのエッジを1回だけトレースしながら1つの連続したストロークでグラフを描く」という問題になっています。

紙の上で、いくつかの異なるグラフを考え出してから、単一の連続したストロークで描画できるグラフを考えてみてください。

以前の都市マップと同じように、一部のグラフは可能であるが、それ以外は不可能であることがわかります。理由を理解するために、すべての頂点にその次数をラベル付けしましょう。次に、さまざまな方法で頂点に色を付け、パターンを明らかにすることができます。

Value
Size
Prime Numbers
Even and Odd

These graphs are possible:

2 4 3 3 4 4 2 2 4 4 2 2 2 4 4 2 2 2 4 4 2 4 4 8 2 2 4 4 4 4 2

These graphs are not possible:

2 3 2 3 4 3 2 3 2 2 2 2 2 3 5 3 3 5 3 3 6 3 3 3 3 3

可能なグラフと不可能なグラフのこれらの数を比較すると、 場合にグラフを描画できるようです。 。この状態は、グラフ内の単一の頂点だけを見ると説明できます。

Here you can see a single, magnified vertex in a graph.
If we draw the graph, we will eventually have an edge leading towards this vertex, and then another one leading away. This makes two edges meeting at the vertex.
Maybe the vertex is a crossing rather than a corner. In that case there will be another edge leading towards the vertex, and another edge leading away. Now we have four edges.
And in some graphs, there may even be a third pair of edges leading towards and away from the vertex. Now there are six edges.
Notice that, either way, there always is an even number of edges meeting at the vertex.
The only two exceptions are the vertices where the path starts, and where it ends – these two may have an odd number of edges. If the start and end point are the same, all vertices in the graph are even.

スクロールしてケーニヒスベルクの地図に戻ると、橋の数が奇数である島が3つ以上あることがわかります。したがって、すべての橋を1度だけ通過するルートは確かに不可能です。これが、レナードオイラーが発見したものです。

オイラー氏の発見は、実際にはそれほど有用ではないように見えるかもしれませんが、グラフは、2つの場所間の方向を見つけるなど、他の多くの地理的問題の基礎となっています。これらのアプリケーションについては、後で詳しく説明します。

Archie