Sözlük

Soldaki anahtar kelimelerden birini seçin…

Çizgeler ve AğlarKönigsberg Köprüleri

Okuma zamanı: ~20 min

Çizgeler ve ağlar hakkında ilk defa düşünen matematikçilerden birisi Leonhard Eulerdi. Euler Baltık denizinin yakınlarındaki Königsberg kasabasıyla ilgili eski bir problem üzerinde düşünüyordu.

Pregel nehri Königsberg’i dört parçaya ayırır, ve bu parçaları bağlayan yedi köprü vardır. Her köprüden tam olarak bir kez geçerek şehri dolaşmak mümkün mü? (Yola istediğiniz yerden başlayıp istediğiniz yerde bitirebilirsiniz, aynı yerden başlayıp bitirmeniz şart değil.)

Bu haritalar üzerinde çizerek böyle bir yol bulmaya çalışabilirsiniz:

Harita 1

Harita 2

Harita 3

Harita 4

Köningsberg için böyle bir yol bulmak imkansız gibi görünüyor, ancak başka şehirler için mümkün olabilir. Euler çizgeler kuramını kullanarak herhangi bir şehir için çalışan basit bir kural bulmayı başardı, böylece bir sürü deneme yapmaya gerek kalmıyordu.

Öncelikle şehir haritalarını noktaları ve çizgileri olan çizgelere çevirmemiz gerek. Bu çizgede her ada ya da kara parçası bir ile ve her köprü bir ile gösterilecek.

Şimdi “bütün köprülerden sadece bir kez geçerek şehri dolaşma” sorusu “bir çizgeyi aynı çizginin üzerinden iki kez geçmeden tek hamlede çizebilir miyiz” sorusuna dönüştü.

Kağıt üzerinde bir kaç farklı çizge çizip hangilerinin sürekli bir hamle ile çizilebileceğini görmeye çalışın.

Aynı şehir haritalarında olduğu gibi, kimi çizgelerde bu mümkünken kimi çizgelerde değil. Bunun nedenini anlamak için her noktayı derecesi ile numaralayalım:

Değere göre
Büyüklüğe göre
Asallık ve bileşikliğe göre
Tek ve çiftliğe göre

Bu çizgeler için mümkün:

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

Bu çizgeler için mümkün değil:

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

Bu çizgelere ve noktalardaki sayılara baktığımız zaman sanki bir çizgenin tek seferde çizilebilir gibi görünüyor. Bu koşul çizgedeki sadece tek bir noktaya bakarak açıklanabilir:

Burada çizgenin tek bir noktasını büyütülmüş olarak görebilirsiniz.

Eğer çizgeyi çizersek sonuçta bu noktaya doğru gelen ve bu noktadan çıkan birer çizgi olmalı. Böylece bu noktada buluşan iki çizgimiz olacak.

Belki bu nokta bir köşe değildir de bir geçişi gösteriyordur. Bu durumda bu noktaya doğru gelen başka bir çizgi daha olacaktır, ve bu noktadan ayrılan bir çizgi. Şimdi dört çizgimiz oldu.

Ve kimi çizgelerde üçüncü bir çizgi çifti daha olabilir. Şimdi altı çizgi var.

Her durumda bir noktada hep çift sayıda çizgi olduğuna dikkat edin.

Buna tek istisna yolun başladığı ve bittiği noktalar olacak – bunların tek sayıda çizgisi olabilir. Eğer başlangıç ve bitiş noktaları aynıysa bütün noktaların çift derecesi olur.

Eğer yeniden Königsberg haritasına dönüp bakarsanız tek sayıda köprü bağlantısı olan ada sayısının ikiden fazla olduğunu görürsünüz. Bu yüzden bütün köprülerden tek bir sefer geçen bir yol olması imkansız, ve Euler de bunu keşfetmişti.

Euler’in keşfi gerçek hayatta işlevsiz gibi görünebilir, ancak çizgeler iki konum arasında yol bulma gibi bir sürü coğrafi problemin temelinde yatar. Bu uygulamalar hakkında daha fazlasını ileride göreceğiz.

Archie