Sözlük

Soldaki anahtar kelimelerden birini seçin…

Grafikler ve AğlarKönigsberg Köprüleri

Okuma zamanı: ~20 min

Grafikler ve ağlar hakkında düşünen ilk matematikçilerden biri Leonhard Euler idi . Euler, Baltık Denizi yakınlarındaki Königsberg kasabasıyla ilgili eski bir sorundan etkilendi.

Pregel nehri, Königsberg'i yedi köprü ile birbirine bağlanan dört ayrı parçaya ayırır. Tüm köprüleri tam olarak bir kez geçerek - birden fazla değil, şehirde dolaşmak mümkün mü? (Her yerde başlayabilir ve bitirebilirsiniz, aynı yerde olması gerekmez.)

Şu haritalarda çizim yaparak geçerli bir rota bulmaya çalışın:

Map 1

Map 2

Map 3

Map 4

Königsberg örneğinde, geçerli bir rota bulmak imkansız gibi görünüyor, ancak diğer bazı şehirler çalışıyor. Euler, grafik teorisini kullanarak pek çok olasılığı denemek zorunda kalmadan herhangi bir şehre uygulanabilecek basit bir kural bulmayı başardı.

İlk olarak, şehir haritalarını kenarları ve köşeleri olan grafiklere dönüştürmemiz gerekiyor. Her ada veya bölge temsil edilir ve iki bölgeyi birbirine bağlayan her köprü karşılık gelen bir ile temsil edilir .

Şimdi “her köprüyü tam olarak bir kez geçerken bir şehri gezmek” sorunu, “her kenarı tam olarak bir kez izleyerek bir sürekli vuruşla bir grafik çizmek” sorunu haline geldi.

Kağıt üzerinde birkaç farklı grafik oluşturun ve hangilerinin tek bir sürekli konturla çizilebileceğini bulmaya çalışın.

Tıpkı daha önceki şehir haritalarında olduğu gibi, bazı grafiklerin mümkün olduğunu, bazılarının ise mümkün olmadığını görüyoruz. Nedenini anlamamıza yardımcı olmak için, her köşeyi derecesi ile etiketleyelim. Ardından köşeleri farklı şekillerde renklendirebilir ve bir desen ortaya çıkarmaya çalışabiliriz:

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

Mümkün olan ve mümkün olmayan grafikler için bu sayıların karşılaştırılması, yoksa bir grafiğin çizilebileceği anlaşılmaktadır. . Grafikte yalnızca tek bir tepe noktasına bakarsak bu durum açıklanabilir:

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.

Königsberg haritasına geri dönerseniz, tek sayıda köprüye sahip ikiden fazla ada olduğunu göreceksiniz. Bu nedenle, her köprüyü tam olarak bir kez geçen bir rota gerçekten imkansızdır - ve Leonard Euler keşfetti.

Euler'nin keşfi gerçek hayatta özellikle yararlı görünmeyebilir, ancak grafikler iki konum arasında yön bulma gibi diğer birçok coğrafi sorunun temelini oluşturur. Daha sonra bu uygulamalardan daha fazlasını keşfedeceğiz.