Soru:
Königsberg şehrinde, 18. yüzyılda ortaya atılan ünlü problemde, şehir iki büyük ada ve ana karadan oluşmaktadır. Bu bölgeler arasında 7 köprü bulunmaktadır. Problemin temel sorusu şudur: "Bir kişi, Königsberg şehrindeki köprülerin her birinden tam olarak bir kez geçerek, başladığı noktaya dönmeden bir yürüyüş yapabilir mi?" Bu problemi bir çizge (graf) modeli kullanarak analiz ediniz. Çizgeyi oluştururken nelere dikkat edilmelidir?
Çözüm:
💡 Bu problemi çözmek için şehir topoğrafyasını bir çizgeye dönüştürmek gerekir. Çizge teorisinde, bölgeler (kara parçaları) düğümler (köşeler), köprüler ise bu düğümleri birleştiren kenarlar olarak modellenir.
- ➡️ Adım 1: Çizge Modelini Kurma Königsberg şehrinde dört ana kara parçası vardır: Sol kıyı (A), Sağ kıyı (B), Büyük Ada (C) ve Küçük Ada (D). Bu dört bölge, çizgemizin dört düğümünü (A, B, C, D) oluşturur.
- ➡️ Adım 2: Kenarları (Köprüleri) Yerleştirme Yedi köprü, bu düğümleri birleştiren kenarlardır. Örneğin, A ve C arasında iki köprü varsa, bu A ve C düğümleri arasında iki kenar olduğu anlamına gelir. Königsberg çizgesinin kenar bağlantıları şöyledir: A ve C arasında 2 kenar, A ve D arasında 1 kenar, B ve C arasında 2 kenar, B ve D arasında 1 kenar, C ve D arasında 1 kenar.
- ➡️ Adım 3: Problemi Çizge Teorisi Diline Çevirme Problemin sorusu artık şu hale gelir: "Bu çizgede, her kenardan tam bir kez geçen ve başlangıç düğümüne dönmeyen bir yol (Euler yolu) var mıdır?"
- ➡️ Adım 4: Euler Yolu Kriterini Uygulama Bir çizgede Euler yolu olması için, çizgenin ya 0 ya da 2 tane tek dereceli düğüme sahip olması gerekir. Bir düğümün derecesi, ona bağlı olan kenar sayısıdır. Königsberg çizgesindeki düğüm derecelerini hesaplayalım: d(A)=3, d(B)=3, d(C)=5, d(D)=3. Görüldüğü gibi dört düğümün de derecesi tektir.
✅ Sonuç olarak, Königsberg çizgesinde 4 tane tek dereceli düğüm vardır. Euler yolunun var olması için en fazla 2 tek dereceli düğüm olmalıydı. Bu nedenle, Königsberg köprülerinden her birini tam bir kez geçerek bir yürüyüş yapmak imkansızdır.
