Ön Bilgi: Königsberg Köprü Problemi
Problemin Tanımı
Königsberg (günümüzdeki Kaliningrad), Pregel Nehri'nin etrafına kurulmuş eski bir Prusya şehridir. Nehir, şehrin ortasında Kniephof adında bir ada oluşturur ve şehri dört ana kara parçasına ayırır. 18. yüzyılda bu kara parçalarını birbirine bağlayan yedi köprü bulunmaktaydı.
O dönemde şehir sakinleri arasında popüler olan bir soru ortaya çıktı:
"Bir kişi yürüyüşüne herhangi bir noktadan başlayıp, yedi köprünün her birinden yalnızca bir kere geçerek başladığı noktaya dönebilir mi veya tüm köprüleri geçebilir mi?"
Euler'in Çözümü ve Graf(Çizge) Teorisi
Bu problem, ünlü matematikçi Leonhard Euler tarafından 1736'da çözülmüştür ve bu çalışma graf teorisinin başlangıcı olarak kabul edilir. Euler, problemi soyutlayarak kara parçalarını düğüm (köşe) ve köprüleri de bu düğümleri birleştiren kenar olarak modellemiştir.
Euler, bir grafın tüm kenarlarından tam olarak bir kez geçilip geçilemeyeceğini belirlemek için düğümlerin derecelerini (bir düğüme bağlı kenar sayısını) incelemiştir:
- Euler Devresi (Başlangıç noktasına dönülen yol): Bir graf üzerinde her kenardan tam olarak bir kez geçerek başlanan düğüme geri dönülebilmesi için, grafın tüm düğümlerinin derecesinin çift olması gerekir.
- Euler Yolu (Başlangıç ve bitiş farklı olabilir): Bir graf üzerinde her kenardan tam olarak bir kez geçilebilmesi için (başlangıç ve bitiş düğümleri farklı olabilir), grafın tam olarak iki düğümünün derecesinin tek olması gerekir. Diğer tüm düğümlerin derecesi çift olmalıdır. Tek dereceli düğümler yolun başlangıç ve bitiş noktaları olur.
- Eğer grafın ikiden fazla tek dereceli düğümü varsa, ne Euler Yolu ne de Euler Devresi çizilebilir.
Königsberg Probleminin Çözümü
Yukarıdaki graf gösteriminde Königsberg köprü probleminin düğüm dereceleri şöyledir:
- Sağ Kıyı (A): 3 (Tek)
- Üst Kıyı (B): 3 (Tek)
- Alt Kıyı (C): 3 (Tek)
- Orta Ada (D): 5 (Tek)
Görüldüğü gibi, grafın dört tane tek dereceli düğümü vardır. Euler'in teoremine göre, ikiden fazla tek dereceli düğüm olduğu için Königsberg şehrinde köprülerin her birinden tam olarak bir kez geçerek bir tur atmak mümkün değildir.
Eğer Königsberg'e uygun bir yere bir köprü daha (8. köprü) eklenseydi ve bu sayede tek dereceli düğüm sayısı sıfıra veya ikiye inseydi, o zaman böyle bir yürüyüş mümkün olabilirdi.
Not: Königsberg Köprü Problemi, gerçek dünya problemlerinin matematiksel modelleme (özellikle graf teorisi) ile nasıl çözülebileceğinin harika bir örneğidir.
Graf Teorisine Giriş
Grafın Temel Kavramları
Graflar, farklı noktaları (düğümleri) çizgilerle birleştirerek bir ağ oluşturan matematiksel yapılardır. Bir graf, kenarları kırmadan, azaltmadan veya yeni birleşme noktaları eklemeden hareket ettirilerek manipüle edilir.
Ana Terimler:
- Düğüm (Köşe): Grafın kenarların buluştuğu noktaları.
- Kenar: Düğümleri birleştiren çizgiler.
- Derece: Bir düğüme bağlı kenarların sayısı.
Not: Birden fazla kenarı birleştirmeyen bir kenar üzerindeki bir nokta, düğüm olarak kabul edilmez.
Graf Dönüşümleri
Graflar, temel yapılarını korurken çeşitli şekillerde dönüştürülebilir. Geçerli dönüşümler, kenarları kırmadan veya yeni düğümler oluşturmadan düğümler arasındaki bağlantıları korur.
Geçerli Dönüşüm Örnekleri:
Düzlemsel Graflar
Düzlemsel graflar, kenarların yalnızca düğümlerde kesişmesi dışında hiçbir kenarın kesişmediği şekilde bir düzlem üzerine çizilebilen graflardır. Düğümlerin (\( V \)), kenarların (\( E \)) ve dış bölge dahil bölgelerin (\( R \)) sayısı arasında özel bir ilişki vardır.
Düzlemsel Graflar için Euler Formülü:
\[ V + R = E + 2 \]
Euler Yolu ve Euler Devresi
Graf teorisinde, Euler Yolu ve Euler Devresi, bir grafın kenarlarını belirli kurallara göre dolaşmayı tanımlayan önemli kavramlardır.
- Euler Yolu: Bir grafın her kenarını tam olarak bir kez ziyaret eden bir yoldur. Başlangıç ve bitiş düğümleri farklı olabilir.
- Euler Devresi: Bir Euler Yolu olup aynı zamanda başlangıç ve bitiş düğümünün aynı olduğu bir döngüdür.
Euler Yolu ve Devresi Koşulları:
Euler Yolu ve Euler Devresi’nin varlığı, grafın düğümlerinin derecelerine bağlıdır:
- Euler Devresi için: Grafın tüm düğümlerinin derecesi çift olmalıdır. Bu, her düğümden girip çıkarken kenarların tükenmesini sağlar.
- Euler Yolu için: Grafın tam olarak iki düğümünün derecesi tek olmalı, diğer tüm düğümlerin derecesi ise çift olmalıdır. Tek dereceli düğümler yolun başlangıç ve bitiş noktalarıdır.
- Eğer grafın ikiden fazla düğümünün derecesi tekse, ne Euler Yolu ne de Euler Devresi yoktur.
Örnek Açıklamaları:
- Soldaki Graf: Tüm düğümlerin derecesi 2 (çift). Bu nedenle bir Euler Devresi vardır.
- Sağdaki Graf: İki düğümün derecesi 1 (tek), iki düğümün derecesi 2 (çift). Tam olarak iki tek dereceli düğüm olduğu için Euler Yolu vardır, ancak Euler Devresi yoktur.