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

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

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? Evet, siz de uğraşabilirsiniz. Kolay görünüyor değil mi? Şimdi yapılabilir mi yapılamaz mı göreceğiz.

Königsberg, Eskiden Rusya’ya bağlı olmasına rağmen şimdi Almanya sınırları içerisinde bulunan bir kenttir. Fakat Königsberg bir ırmak üzerinde iki adadan oluşuyordu. Bu adalar ise birbirine yollar ile bağlıydı. Adalardan biri ırmağın iki kıyısına ikişer köprü; diğeri de birer köprü ile bağlanmıştır. Ayrıca iki adasında bir köprü vardır. Kentteki insanlar pazar günleri her köprüden yalnızca bir kez geçerek tüm köprülerden geçmeye çalışıyorlardı. Bu gelenekselleşmiş olay Leonhard Euler’ın kulağına gider. Kimse tek seferde geçemediği için insanların kafasında hep bir merak konusu olmuştu.

EULER’İN ÇÖZÜMÜ    

Euler, çözümünde kara parçalarını harflerle, köprüleri ise sayılarla ifade etmiş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 andandı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.

Konigsberg-graf.jpg

 

    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.