Königsberg'in Yedi Köprüsü

Bazen bir problemi çözmek, bir problemi çözmekten daha fazlasıdır. Königsberg Köprüleri Problemi buna güzel bir örnektir. Königsberg günümüzde Rusya Federasyonu'nda Kaliningrad adıyla yer alan, tarihte ise Alman Doğu Prusya eyaletinin başkenti olan bir şehirdir. Bu şehirde Eski ve Yeni Pregel nehirleri birleşerek Pregolya nehrini oluşturmaktadır. Bu nehirler şehri dört bölgeye ayırmaktadır ve nehir üzerine inşa edilen yedi köprü ile bu bölgeler birbirine bağlanmıştır.

Königsberg'in Yedi Köprüsü Problemi şudur: Şehrin herhangi bir noktasından başlayıp, her köprüden yalnızca bir defa geçmek şartıyla bir şehir turu yapılabilir mi?

 Günümüzde bu yedi köprüden ikisi ayakta kalmayı başarmıştır, diğer beşi yıkılarak yerlerine üç köprü yapılmıştır. 

 Çözüme geçmeden önce, Matematikte çok farklı kapılar açan bu problemi çözmeyi denemenizi tavsiye ediyoruz.

Königsberg'in Yedi Köprüsü

Anlaşılması basit olan bu probleme çözüm bulunamamış, neden bulunamadığı ise 1736 yılında ünlü matematikçi Leonhard Euler'in çözümüyle açıklığa kavuşmuştur.

Euler'in Çözümü

Euler çözümünde kara parçalarını harflerle, köprüleri ise sayılarla işaretlemiştir. Çözümü kolaylaştırmak ve şekli daha sade hale getirmek amacıyla kara parçalarının noktalarla, köprülerin ise çizgilerle temsil edildiğ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. Bu grafta A, B ve D düğümlerinin derecesi 3, C düğümünün derecesi ise 5'tir. 

Königsberg'in Yedi Köprüsü

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.

Çözümün temelinde yatan düşünce şudur: Bir düğüm, başlangıç ya da bitiş düğümü değilse o düğüme gelen kişinin turu tamamlayabilmek için oradan ayrılması gerekecektir. Dolayısıyla bu tip düğümler çift dereceleri olmalıdır. Oysa tek dereceli bir düğüme, örneğin D düğümüne ikinci kez gelen bir kişi çıkış yolu bulamayacaktır. Dolayısıyla bu düğüm ya gezintinin bitiş düğümü olmalıdır ya da başlangıç düğümü olarak seçilmelidir ki ikinci gelişte çıkış yolu bulunabilsin. Buna göre tek dereceli düğüm sayısı ikiden fazlaysa gezinti tamamlanamayacaktır.

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.

Bir Problemden Fazlası

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.

Yararlanılan Kaynak: https://tr.wikipedia.org/wiki/Königsberg'in_yedi_köprüsü