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.
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.
Aşağıdaki şekilde kara parçaları harflerle, köprüler ise sayılarla işaretlenmiştir. Önce çözümü biraz daha kolaylaştırmak ve şekli gereksiz bileşenlerden arındırmak amacıyla kara parçalarının noktalar, köprülerin ise bu noktaları birleştiren çizgiler olarak gösterildiği ikinci bir şekil yani graf (çizge) çizilir. Graflar graf elemanı, noktalar düğüm, düğüme bağlı olan elemanların sayısı ise düğüm derecesi olarak adladırılmak üzere soru, grafın herhangi bir düğümünden başlayarak yedi elemanının her birini bir ve yalnız bir kere kullanarak dolaşma problemine dönüşmüş olur.
1736'da Euler'in incelemeleri böyle bir gezintinin mümkün olmadığını kanıtlamış ve bu tür dolaşmayı mümkün kılacak grafların şu özelliklere sahip olmaları gerektiğini göstermiştir: Birleşik bir grafın bütün elemanlarını bir ve yalnız bir defa kullanarak dolaşmak için o grafın tek dereceli düğümlerinin sayısı eğer varsa iki olmalıdır. Tek dereceli düğümler dolaşmanın başlangıç ve bitiş düğümleridir. Grafta böyle düğümler yoksa dolaşmaya herhangi bir düğümden başlanabilir.
Yürüyüşün sonunda başlangıç noktasına dönülebilmesi içinse bütün düğümler çift dereceli olmalıdır. Böylece, başlangıç ve bitiş düğümü aynı olan ve her bir elemanı sedece ve en az bir kez içeren turlara "Euler turu" ve Euler turu içeren graflara da "Euler grafları" denmiştir.
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.İngilizce wikipedia
Prensler ve Piskopos
Öncelikle şekil düğümleri renkli (han → turuncu, kilise → beyaz) olan bir grafa indirgenir.
Piskopos'un isteğinde ise farklı bir durum söz konusudur. Yeni grafta başlangıç ve bitiş noktası aynı olmalıdır. Buna göre graftaki bütün düğümler çift dereceli yapılmalıdır. Dolayısıyla onuncu köprü kırmızı şato ile han arasına inşa edilmelidir.
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.
Köprülerin günümüzdeki durumu
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.
↑ What Ever Happened to those bridges?
Tokad, Y. (1996). Devre Analizi Dersleri, Çağlayan Kitabevi, İstanbul