Königsberg'in yedi köprüsü

Königsberg'in yedi köprüsü; graf teorisinin temelini oluşturan ve XVIII. yüzyılda Königsberg köprülerinden ilhamlanılarak ortaya atılan ünlü bir matematik problemidir.

Problemin kökeni

Königsberg kentinde Eski ve Yeni Pregel nehirleri birleşerek Pregel (Pregolya) nehrini oluşturmaktadır. Bu nehirler, şehri dört bölüme ayırmaktadır ve nehir üzerinde bu bölgeleri birleştiren yedi köprü bulunmaktadır. Merak edilen ise şudur: Bütün köprülerden bir ve yalnız bir defa geçmek koşulu ile bir yürüyüş yapılabilir mi?
Bu soru, 1736'da İsviçreli matematikçi Leonhard Euler tarafından cevaplandırılmıştır.

Problemin değişik biçimleri

Problemin, klasik ifadesinden faklı olarak her düğümün değişik renk veya isimlerle adlandırıldığı ve yeni köprülerin eklendiği çeşitleri de mevcuttur.

Prensler ve Piskopos

Şehrin kuzey yakasında (A) Mavi Prens'in şatosu, güney yakasında (B) Kırmızı Prens'in şatosu, doğuda (D) Piskopos'un kilisesi ve ortadaki adada (C) bir han bulunmaktadır.
Mavi Prens köprülerden istenen şekilde yürünemeyeceğini anlar ve gizlice sekizinci köprüyü yapmayı planlar. Köprüyü öyle bir yere yapmalıdır ki akşamüstü kendi şatosundan yürüyüşe başlamalı ve gezintisini handa tamamlayarak zaferini kutlamalıdır. Ancak Kırmızı Prens gezintiyi tamamlayamamalıdır. Mavi Prens sekizinci köprüyü nereye inşa etmelidir?
Mavi Prens'in sekizinci köprüyü inşa etmesi Kırmızı Prens'i çok kızdırır. Handa tamamlayabileceği bir yürüyüşü olanaklı ve Mavi Prens'in yürüyüşünü imkânsız hale getirecek dokuzuncu köprüyü inşa etmek ister. Kırmızı Prens dokuzuncu köprüyü nereye inşa etmelidir?
Piskopos ise bu köprü kurma yarışını endişeyle izlemektedir. Bu durum hem şehrin görüntüsünü bozmaktadır hem de han da sonlanan yürüyüşler sarhoşluğu artırmaktadır. Tüm gezintilerin başladığı yerde bitmesi için onuncu bir köprü yaptırmalıdır. Onuncu köprü nereye inşa edilmelidir?

Matematik tarihindeki önemi

Leonhard Euler’in bu araştırmaları matematikte tamamıyla yeni bir dal olan graf teorisinin ilk teoremi ve topolojinin keşfinin habercisi olmuştur. Çözümün ardından Euler, "Solutio problematis ad geometriam situs pertinentis" isimli makaleyi yayımlamıştır.

Çözümün kullanım alanları

Ayrıt rotalama problemleri, pek çok araştırmacının üzerinde çalıştığı bir rota en iyilemesi problemidir. Bu problemin, gerçek hayatta mektup dağıtımı, yol bakımı, kar temizleme, çöp toplama, devriye araçları ve yol tuzlama konularında pek çok uygulaması vardır. Gerek hükümetler gerekse de işletmeler her yıl bu işlemler için önemli harcamalar yapmaktadırlar. Fakat planlamanın etkin olarak yapılamaması durumunda önemli miktarlarda kaynak israfı söz konusudur.

Köprülerin günümüzdeki durumu

Probleme konu olan yedi köprünün ikisi II. Dünya Savaşı sırasındaki bombardımanlarla yok edildi. Daha sonra iki tanesi Ruslar tarafından yıkıldı ve yerine modern bir otoyol inşa edildi. Geriye kalan üç köprü ise hala ayakta durmakta. Bunlardan biri Almanlar tarafından 1935 yılında tekrar inşa edildi. Sadece geri kalan ikisi Euler zamanından bu yana ayakta kalmayı başardı. Sonuç olarak günümüz modern Königsberg'inde beş köprü bulunmakta.
Graf teorisine göre günümüzde ikinci dereceden üç düğüm ve üçüncü dereceden iki düğüm olacak şekilde konumlanmış olan Königsberg'in köprülerinde her köprüden bir ve yalnız bir kez geçmek koşulu ile bir yürüyüş yapmak mümkündür. Fakat bu yürüş bir adada başlayıp diğer bir adada biteceğinden dolayı bir Euler Turu oluşturmamaktadır.