🎓 9. Sınıf Königsberg Şehrindeki Yürüyüş Rotası Problemini Çizgeler Yardımıyla Çözümleme Nedir? Test 1 - Ders Notu
Bu ders notu, Königsberg Köprüleri Problemi'ni ve bu problemi çözmek için kullanılan temel çizge (graf) teorisi kavramlarını, 9. sınıf seviyesindeki öğrencilerin kolayca anlayabileceği şekilde özetlemektedir. Bu test, çizge teorisinin günlük hayatta nasıl kullanılabileceğini anlamanıza yardımcı olacak.
📌 Königsberg Köprüleri Problemi Nedir?
Königsberg, Prusya'da (şimdiki Kaliningrad, Rusya) Pregel Nehri üzerinde kurulu bir şehirdi. Şehrin ortasında iki büyük ada ve bu adaları birbirine ve anakaraya bağlayan yedi köprü bulunuyordu. İnsanlar, her köprüden tam olarak bir kez geçerek bir yürüyüş rotası oluşturup başlangıç noktalarına geri dönüp dönemeyeceklerini merak ediyorlardı.
- Problem: Her köprüden sadece bir kez geçerek, şehirde bir yürüyüş rotası çizmek mümkün müdür?
- Tarihsel Önemi: Bu problem, modern matematiğin önemli bir dalı olan çizge teorisinin doğuşuna yol açmıştır.
💡 İpucu: Bu problemi, bir kuryenin her sokağa sadece bir kez uğrayarak tüm teslimatları yapıp başlangıç noktasına dönmesi gibi düşünebilirsiniz.
📌 Çizge (Graf) Nedir? Temel Kavramlar
Königsberg problemini çözmek için, bu yapıyı matematiksel bir modelle, yani bir "çizge" ile temsil etmemiz gerekir.
- Düğüm (Köşe/Tepe Noktası - Vertex): Bir çizgedeki noktalar veya elemanlardır. Königsberg probleminde bunlar, kara parçalarını (adalar ve anakara) temsil eder.
- Kenar (Ayrıt - Edge): Düğümleri birbirine bağlayan çizgilerdir. Königsberg probleminde bunlar, köprüleri temsil eder.
- Derece (Degree): Bir düğüme bağlı olan kenarların sayısıdır. Yani, bir kara parçasından çıkan köprü sayısıdır.
- Yönlü/Yönsüz Çizgeler: Königsberg probleminde köprülerin tek yönlü bir kuralı olmadığından, bu bir "yönsüz çizge"dir.
📝 Örnek: Eğer bir ada, 3 köprü ile diğer kara parçalarına bağlıysa, bu adayı temsil eden düğümün derecesi 3'tür.
📌 Königsberg Problemini Çizgeye Dönüştürme
Königsberg problemini bir çizge olarak modellemek oldukça basittir:
- Şehrin dört ana kara parçasını (iki ada ve iki anakara kıyısı) birer düğüm olarak düşünürüz. Bu düğümlere A, B, C, D gibi isimler verebiliriz.
- Yedi köprüyü ise bu düğümleri birbirine bağlayan kenarlar olarak düşünürüz.
⚠️ Dikkat: Amacımız, bu çizgedeki her kenarı (köprüyü) tam olarak bir kez kullanarak bir yol bulmaktır. Kenarları tekrar kullanamayız.
📌 Euler Yolu ve Euler Devresi (Tur)
Königsberg probleminde aradığımız şey, özel bir tür yoldur: Euler yolu veya Euler devresi.
- Euler Yolu (Eulerian Path): Bir çizgedeki her kenarı tam olarak bir kez kullanarak geçilen bir yoldur. Bu yolun başlangıç ve bitiş noktaları farklı olabilir.
- Euler Devresi (Eulerian Circuit/Tour): Bir çizgedeki her kenarı tam olarak bir kez kullanarak geçilen ve başlangıç noktasına geri dönülen bir yoldur.
💡 İpucu: Bir Euler devresi, aynı zamanda bir Euler yoludur, ancak başlangıç ve bitiş noktası aynıdır. Bir "tur" kelimesi genellikle başlangıç noktasına geri dönmeyi ifade eder.
📌 Euler Yolu ve Devresi İçin Koşullar
Bir çizgede Euler yolu veya devresi olup olmadığını anlamak için düğümlerin derecelerine bakarız. Bu kurallar, Leonard Euler tarafından bulunmuştur:
- Euler Devresi Varlığı: Bir çizgede Euler devresi (yani başladığımız yere dönerek her köprüden bir kez geçme) olması için, çizgedeki **tüm düğümlerin derecesi çift sayı olmalıdır.**
- Euler Yolu Varlığı (Devre Değil): Bir çizgede Euler yolu (yani her köprüden bir kez geçme, ancak başladığımız yere dönme zorunluluğu yok) olması için, çizgede **tam olarak iki tane tek dereceli düğüm olmalıdır.** Diğer tüm düğümlerin derecesi çift sayı olmalıdır. Bu iki tek dereceli düğüm, yolun başlangıç ve bitiş noktaları olacaktır.
- Ne Euler Yolu Ne de Devresi: Eğer çizgede ikiden fazla tek dereceli düğüm varsa, o çizgede her kenarı tam olarak bir kez kullanarak bir yol oluşturmak mümkün değildir.
📝 Örnek Dereceler: Bir düğümün derecesi 2, 4, 6... ise çift; 1, 3, 5... ise tek derecelidir.
📌 Königsberg Probleminin Çözümü
Şimdi, öğrendiğimiz bu kuralları Königsberg Köprüleri problemine uygulayalım:
- Königsberg şehrinin dört kara parçasını (düğümlerini) incelediğimizde, her bir düğümün derecesinin (yani o kara parçasından çıkan köprü sayısının) tek sayı olduğunu görürüz.
- Örneğin, bir kara parçasından 3 köprü, diğerinden 5 köprü, diğerinden 3 köprü ve sonuncusundan yine 3 köprü çıktığını varsayalım. Bu durumda, $d(A)=3$, $d(B)=5$, $d(C)=3$, $d(D)=3$ gibi. (Gerçek Königsberg haritasında bu derecelerin hepsi tek sayıdır.)
- Euler'in koşullarına göre, bir çizgede Euler yolu veya devresi olması için ya tüm düğümlerin derecesi çift olmalı ya da tam olarak iki düğümün derecesi tek olmalıdır.
- Königsberg probleminde ise **dört adet tek dereceli düğüm** bulunmaktadır.
⚠️ Dikkat: Dört adet tek dereceli düğüm olduğu için, Euler yolu veya devresi için gereken koşullardan hiçbiri sağlanmamaktadır.
Sonuç: Bu nedenle, Königsberg Köprüleri probleminde her köprüden tam olarak bir kez geçerek bir yürüyüş rotası oluşturmak mümkün **değildir**.
