Euler ve Königsberg'in yedi köprüsü: Graf kuramının başlangıcı

Bir kalemi kâğıttan kaldırmadan ve hiçbir çizginin üzerinden iki kez geçmeden bir şekli çizmeye çalıştınız mı? Bazı şekillerde bu kolayca olur, bazılarında ne kadar denerseniz deneyin olmaz. Neden? Deneme yanılmayla bu soruya cevap bulmak zordur; ama 18. yüzyılda bir şehrin köprüleri üzerine düşünen Leonhard Euler, cevabı bir sayma kuralına indirgedi.

Königsberg şehrinde bir nehir, bir ada ve yedi köprü vardı. Soru şuydu: Her köprüden tam bir kez geçen bir yürüyüş yapılabilir mi? Euler, böyle bir yürüyüşün imkânsız olduğunu gösterdi ve bunu yaparken mesafeleri, açıları ya da haritanın tam biçimini hiç kullanmadı. Önemli olan yalnızca hangi kara parçasının hangisine kaç köprüyle bağlandığıydı. Bu yazıda Euler’in akıl yürütmesini adım adım kuracak ve bugünkü graf kuramıyla bağlantısını göreceğiz.

Bir şehir, bir nehir, yedi köprü

Königsberg o dönemde Doğu Prusya’nın bir şehriydi; bugün Rusya’daki Kaliningrad’dır. Şehrin içinden geçen Pregel Nehri, Kneiphof adlı bir adanın çevresinde iki kola ayrılıyordu. Böylece şehir dört kara parçasına bölünmüştü: nehrin kuzey kıyısı, güney kıyısı, ada ve adanın doğusunda iki kol arasında kalan kara parçası. Bu dört parça yedi köprüyle birbirine bağlıydı.

Euler’in çizimindeki gibi kara parçalarına A, B, C, D adlarını verelim. A ada olsun. Köprülerin dağılımı şöyledir:

Kara parçası	Bağlı köprü sayısı
A (ada)	5
B	3
C	3
D	3

Bu sayıları toplarsak 5 + 3 + 3 + 3 = 14 elde ederiz. Köprü sayısı 7 iken toplamın 14 çıkması tesadüf değildir: Her köprü iki kara parçasını birbirine bağlar, bu yüzden iki kez sayılır. Euler makalesinde bu gözlemi de açıkça yazar.

Euler ve “konum geometrisi”

Leonhard Euler 1707’de İsviçre’de doğdu, 1783’te St. Petersburg’da öldü. Hayatının büyük bölümünü St. Petersburg ve Berlin akademilerinde geçirdi. Königsberg problemini ele alan makalesi Solutio problematis ad geometriam situs pertinentis (Konum geometrisiyle ilgili bir problemin çözümü) başlığını taşır. Euler Archive kayıtlarına göre makale 1735’te yazıldı ve St. Petersburg akademisinin dergisinin 1736 tarihli sekizinci cildinde, 1741’de basıldı.

Euler makalesine, geometrinin uzunluk ve açı gibi büyüklüklerle uğraşan bilinen kısmının yanında, Leibniz’in sözünü ettiği bir “konum geometrisi”nin de bulunduğunu hatırlatarak başlar. Bu tür bir geometri ölçüm yapmaz; yalnızca şeylerin birbirine göre konumuyla ilgilenir. Königsberg köprüleri, Euler’e göre tam da böyle bir problemdir.

Yürüyüşü harflerle yazmak

Euler’in ilk fikri, bir yürüyüşü harflerden oluşan bir dizi olarak yazmaktır. Örneğin A’dan B’ye bir köprüyle geçip oradan D’ye gidersek, bu yürüyüşü ABD diye yazarız.

Bu yazımda her köprü geçişi diziye bir harf ekler. Başlangıç noktası da bir harf olduğu için:

• 1 köprü geçen yürüyüş 2 harfle yazılır.
• 2 köprü geçen yürüyüş 3 harfle yazılır.
• 7 köprünün her birinden bir kez geçen yürüyüş 8 harfle yazılmalıdır.

Şimdi soruyu değiştirelim: Bu 8 harflik dizide her harf kaç kez görünmek zorundadır?

Tek sayıda köprüsü olan bölge

Önce basit bir durum düşünelim. Bir bölgeye yalnızca 1 köprü bağlı olsun. Bu köprüden geçen bir yürüyüşte o bölgenin harfi 1 kez görünür: Ya o bölgeden çıkarken ya da o bölgeye girerken.

Bölgeye 3 köprü bağlıysa, bu üç köprüden geçen bir yürüyüşte bölgenin harfi 2 kez görünür. Nedeni şudur: Her giriş ya da çıkışta harf yazılır; ama bir girişi hemen bir çıkış izlediğinde harf yalnızca bir kez yazılır. Genel olarak Euler şu kuralı gösterir:

Bir bölgeye tek sayıda, k tane köprü bağlıysa, bütün köprüleri bir kez geçen yürüyüşte o bölgenin harfi (k + 1) ÷ 2 kez görünür.

Königsberg’e uygulayalım:

Bölge	Köprü sayısı	Harfin görünme sayısı
A	5	(5 + 1) ÷ 2 = 3
B	3	(3 + 1) ÷ 2 = 2
C	3	(3 + 1) ÷ 2 = 2
D	3	(3 + 1) ÷ 2 = 2
Toplam		9

Her köprüden bir kez geçen bir yürüyüşün diziye tam 8 harf yazması gerekirken, bölgelerin köprü sayıları en az 9 harf gerektiriyor. Bu bir çelişkidir. Demek ki Königsberg’de her köprüden tam bir kez geçen bir yürüyüş yoktur.

Dikkat edin: Bu ispat bütün olası yolları tek tek denemeden, yalnızca sayarak yapıldı. Deneme yanılmayla yüzlerce rotayı kontrol etmek yerine, imkânsızlığın nedenini gösteren kısa bir akıl yürütme.

Genel kural

Euler bu yöntemi herhangi bir nehir, ada ve köprü düzenine genelledi. Makalesinin sonunda vardığı sonuç, bugünkü dille şöyle özetlenebilir:

• Tek sayıda köprüsü olan bölge sayısı ikiden fazlaysa, her köprüden bir kez geçen yürüyüş mümkün değildir.
• Tek sayıda köprüsü olan tam iki bölge varsa, yürüyüş bu iki bölgeden birinde başlamalı (ve diğerinde bitmelidir).
• Tek sayıda köprüsü olan hiç bölge yoksa, yürüyüş istenen herhangi bir bölgeden başlayabilir.

Königsberg’de dört bölgenin dördünün de köprü sayısı tektir; bu yüzden cevap olumsuzdur.

Tek sayıda köprüsü olan bölge sayısının neden hiçbir zaman tek olamayacağını da gördük: Bütün köprü sayılarının toplamı, köprü sayısının iki katıdır, yani çifttir. Çift bir toplamda tek sayıların adedi çift olmak zorundadır.

Kendiniz deneyin: Königsberg’e hayalî bir sekizinci köprü eklendiğini ve bu köprünün B ile C’yi bağladığını düşünelim. B ve C’nin köprü sayıları 4 olur, yani çifttir. A’nın 5, D’nin 3 köprüsü kalır. Tek sayıda köprüsü olan tam iki bölge vardır: A ve D. Euler’in kuralına göre bu durumda her köprüden bir kez geçen bir yürüyüş mümkündür; ama yürüyüş A’da başlayıp D’de ya da D’de başlayıp A’da bitmelidir. Harf sayımıyla da kontrol edebiliriz: 8 köprü için 9 harf gerekir; A 3 kez, D 2 kez, B ve C ise ikişer kez görünür. 3 + 2 + 2 + 2 = 9, yani artık bir çelişki yoktur.

Köprülerden graflara

Bugün bu problemi anlatırken genellikle her kara parçasını bir nokta, her köprüyü iki noktayı birleştiren bir çizgi olarak çizeriz. Böyle bir çizime graf, noktalara köşe, çizgilere kenar, bir köşeye bağlı kenar sayısına da o köşenin derecesi denir. Euler’in makalesindeki şekiller ise nehir ve köprü planlarıdır; bugünkü nokta-çizgi çizimi, onun fikrini anlatmak için sonradan yaygınlaşan bir gösterimdir.

Graf diliyle Euler’in sonuçları şöyle okunur:

• Bütün köşe derecelerinin toplamı, kenar sayısının iki katıdır.
• Her kenardan bir kez geçen bir yol için tek dereceli köşe sayısı 0 ya da 2 olmalıdır.

Kalemi kaldırmadan çizim bulmacaları da aynı kurala uyar. Çocukların sıkça çizdiği “zarflı ev” şeklinde, yani bir karenin iki köşegeni ve üstüne bir çatı üçgeni eklenmiş şekilde, alt iki köşenin derecesi 3, diğer köşelerin derecesi çifttir. Tek dereceli tam iki köşe olduğu için şekil kalem kaldırmadan çizilebilir; ama alt köşelerden birinden başlamak gerekir.

Bugün nerede karşımıza çıkar?

• Rota planlama: Çöp toplama, kar temizleme ya da posta dağıtımı gibi, her sokaktan en az bir kez geçmesi gereken araçların rotaları, bu problemin uzantılarıyla planlanır.
• Ağlar: Yol, elektrik, bilgisayar ve sosyal ağlar graflarla modellenir.
• Sayma ve ispat: “Aynı şeyi iki farklı yoldan say” fikri ve tek-çift akıl yürütmesi, kombinatorik ve sayılar konusundaki birçok sorunun anahtarıdır.
• Topoloji: Mesafeleri önemsemeyip yalnızca bağlantılara bakmak, topolojinin temel düşüncelerinden biridir.

Somut bir durumdan soyut bir modele geçme yaklaşımımızı nasıl öğretiyoruz sayfasında anlatıyoruz. Sayarak imkânsızlık göstermenin başka bir güçlü örneği için Cantor ve sonsuzlukların büyüklüğü yazımıza bakabilirsiniz.

Kapanış

Euler’in çözümü, bir problemi gereksiz ayrıntılardan arındırmanın ne kadar güçlü olabileceğini gösterir. Köprülerin uzunluğu, nehrin genişliği ya da sokakların biçimi önemli değildi; önemli olan yalnızca bağlantılar ve onların tek ya da çift olmasıydı. Bir şehir bulmacası, bugün ağları anlamak için kullandığımız graf kuramının ilk adımlarından biri oldu.