🎓 9. Sınıf Königsberg Şehrindeki Yürüyüş Rotası Problemini Çizgeler Yardımıyla Çözümleme Nedir? Test 2 - 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ı, özellikle Euler yolları ve devrelerini anlamanıza yardımcı olacaktır.
📌 Königsberg Köprüleri Problemi: Bir Tarihçe
Bu problem, 18. yüzyılda Prusya'nın Königsberg şehrinde ortaya çıkmış ve ünlü matematikçi Leonhard Euler tarafından çözülmüştür. Çözümü, günümüzdeki "çizge teorisi"nin temellerini atmıştır.
- Königsberg şehri, Pregolya Nehri üzerinde iki büyük ada ve nehrin iki yakasından oluşuyordu.
- Şehirde bu adaları ve nehir kıyılarını birbirine bağlayan toplam yedi köprü bulunuyordu.
- Problemin amacı, bir kişinin her köprüden sadece bir kez geçerek tüm köprüleri dolaşıp başlangıç noktasına geri dönüp dönemeyeceğini (veya dönmeyebileceğini) bulmaktı.
💡 İpucu: Bu problem, karmaşık bir fiziksel durumu (şehir ve köprüler) basit bir matematiksel modele (çizge) dönüştürmenin ilk önemli örneklerinden biridir.
📌 Çizge (Graf) Nedir? Temel Kavramlar
Çizgeler, belirli nesneler arasındaki ilişkileri görselleştirmek ve analiz etmek için kullanılan matematiksel yapılardır. Bir çizge, "köşeler" ve bu köşeleri birbirine bağlayan "kenarlardan" oluşur.
- Köşe (Nokta / Vertex): Bir çizgedeki temel nesnelerdir. Königsberg probleminde adalar ve nehir kıyıları birer köşe olarak düşünülebilir.
- Kenar (Yay / Edge): İki köşeyi birbirine bağlayan çizgilerdir. Königsberg probleminde köprüler birer kenar olarak temsil edilir.
- Yönsüz Çizge: Kenarların belirli bir yönü olmadığı çizgelerdir. Yani, A'dan B'ye gitmekle B'den A'ya gitmek aynı kabul edilir. Königsberg problemi yönsüz bir çizge ile modellenir.
- Çoklu Kenar: İki köşe arasında birden fazla kenarın bulunması durumudur (Örn: iki şehir bölümü arasında birden fazla köprü). Königsberg probleminde bu durum mevcuttur.
⚠️ Dikkat: Çizgelerde köşeler arasındaki kenarların uzunluğu veya şekli önemli değildir, sadece hangi köşelerin birbirine bağlı olduğu ve kaç kenarla bağlı olduğu önemlidir.
📌 Bir Köşenin Derecesi Nedir?
Bir köşenin derecesi, o köşeye bağlı olan kenar sayısını ifade eder. Bu kavram, Euler yolu ve devresi problemlerini çözmek için kritik öneme sahiptir.
- Bir köşeye kaç tane kenarın geldiğini veya çıktığını sayarak dereceyi buluruz.
- Çift Dereceli Köşe: Derecesi çift sayı olan köşelerdir (örn: 2, 4, 6...).
- Tek Dereceli Köşe: Derecesi tek sayı olan köşelerdir (örn: 1, 3, 5...).
💡 İpucu: Günlük hayatta bir kavşaktan çıkan yol sayısı o kavşağın derecesi gibi düşünülebilir. Königsberg probleminde her köprü, bağlı olduğu iki köşenin derecesine 1 ekler.
📌 Euler Yolu ve Euler Devresi (Çevrimi) Nedir?
Euler, Königsberg problemini çözerken, bir çizgedeki tüm kenarları sadece bir kez kullanarak bir yol veya döngü oluşturmanın koşullarını belirlemiştir.
- Euler Yolu: Bir çizgedeki tüm kenarları, her kenardan sadece bir kez geçerek bir başlangıç noktasından bir bitiş noktasına kadar takip eden yoldur. Başlangıç ve bitiş noktası farklı olabilir.
- Euler Devresi (Çevrimi): Bir çizgedeki tüm kenarları, her kenardan sadece bir kez geçerek başlangıç noktasına geri dönen yoldur. Başlangıç ve bitiş noktası aynıdır.
⚠️ Dikkat: Euler yolu veya devresi ararken, köşeleri birden fazla kez ziyaret edebiliriz; önemli olan her kenardan (köprüden) sadece bir kez geçmektir.
📌 Euler Yolu ve Euler Devresi'nin Varlık Koşulları
Bir çizgede Euler yolu veya devresinin olup olmadığını anlamak için köşelerin derecelerine bakarız. Bu koşullar, Königsberg probleminin çözümünün temelidir.
- Euler Devresi İçin Koşul: Bir çizgede Euler devresi bulunabilmesi için, çizgedeki tüm köşelerin derecelerinin **çift sayı** olması gerekir.
- Euler Yolu İçin Koşul: Bir çizgede Euler yolu bulunabilmesi için, çizgedeki **tam olarak iki köşenin derecesinin tek sayı** olması gerekir. Diğer tüm köşelerin dereceleri çift olmalıdır.
- Eğer çizgede ikiden fazla tek dereceli köşe varsa, ne Euler devresi ne de Euler yolu vardır.
💡 İpucu: Tek dereceli köşeler, bir Euler yolunun "başlangıç" veya "bitiş" noktası olma potansiyeli taşır. Eğer iki tane tek dereceli köşe varsa, yol o tek dereceli köşelerden birinde başlar ve diğerinde biter.
📌 Königsberg Probleminin Çözümü
Euler, Königsberg şehrinin haritasını bir çizge olarak modellemiş ve yukarıdaki koşulları uygulayarak problemin çözümüne ulaşmıştır. Şimdi bu modellemeyi inceleyelim:
- Köşeler (Şehir Bölümleri): A (Kuzey Yakası), B (Güney Yakası), C (Batı Ada), D (Doğu Ada).
- Kenarlar (Köprüler): Haritadaki yedi köprü, ilgili köşeler arasına kenar olarak çizilir.
- Derecelerin Hesaplanması:
- A köşesi (Kuzey Yakası): 3 köprüye bağlı (tek derece).
- B köşesi (Güney Yakası): 3 köprüye bağlı (tek derece).
- C köşesi (Batı Ada): 5 köprüye bağlı (tek derece).
- D köşesi (Doğu Ada): 3 köprüye bağlı (tek derece).
- Sonuç: Çizgede tam olarak dört adet tek dereceli köşe bulunmaktadır (A, B, C, D).
⚠️ Dikkat: Euler'in koşullarına göre, bir çizgede Euler yolu veya devresi olması için ya tüm köşelerin derecesi çift olmalı ya da tam olarak iki köşenin derecesi tek olmalıdır. Königsberg çizgesinde dört tek dereceli köşe olduğundan, her köprüden sadece bir kez geçerek tüm köprüleri dolaşan bir yol veya döngü **mümkün değildir**.
