9. Sınıf Königsberg Şehrindeki Yürüyüş Rotası Problemini Çizgeler Yardımıyla Çözümleme Nedir?

Question

Königsberg köprüleri sorusunda, şehirdeki yedi köprüyü kullanarak her köprüden sadece bir kez geçerek tüm rotayı tamamlamak mümkün mü diye soruluyor. Grafik teorisiyle çözülüyor ama tam olarak nasıl yapıldığını anlamadım. Özellikle çizgelerde düğümler ve kenarların nasıl yerleştirileceği kafamı karıştırıyor.

Answer 1

Königsberg Şehrindeki Yürüyüş Rotası Problemi

Königsberg Şehri (günümüzde Kaliningrad) problemi, çizge teorisinin temelini oluşturan ünlü bir matematiksel problemdir. 18. yüzyılda Leonhard Euler tarafından çözülmüştür.

Problemin Tanımı

Königsberg şehrinde, iki ada ve bu adaları birbirine ve ana karaya bağlayan 7 köprü bulunmaktadır. Problem şudur:

• Her köprüden tam bir kez geçerek
• Başlangıç noktasına dönmeden
• Şehrin tamamını dolaşmak mümkün müdür?

Çizge Teorisi ile Modellenmesi

Euler, bu problemi çözmek için şehri bir çizge (graf) olarak modellemiştir:

• Düğümler (köşeler): Kara parçaları (A, B, C, D)
• Kenarlar: Köprüler

Bu modelleme sonucunda, Königsberg'ün çizgesi 4 düğüm ve 7 kenar ile ifade edilir.

Euler Yolu ve Euler Devresi

Euler'in çözümünde iki önemli kavram vardır:

• Euler Yolu: Bir çizgede her kenardan tam bir kez geçen yoldur (başlangıç ve bitiş düğümleri farklıdır).
• Euler Devresi: Başlangıç ve bitiş düğümleri aynı olan Euler yoludur.

Çözümün Matematiksel Temeli

Bir çizgede Euler yolu veya devresinin olup olmadığını belirlemek için:

• Euler Devresi: Tüm düğümlerin dereceleri çift olmalıdır.
• Euler Yolu: Tam olarak iki düğümün derecesi tek, diğerleri çift olmalıdır.

Königsberg çizgesinde tüm düğümlerin dereceleri tek sayı olduğundan (3, 3, 3, 5), ne Euler yolu ne de Euler devresi vardır.

Sonuç

Bu analiz, Königsberg köprüleri probleminin çözümsüz olduğunu gösterir. Euler'in bu çalışması, modern çizge teorisinin temelini atmıştır.