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

Question

Bu problemi anlamakta biraz zorlanıyorum. Königsberg'deki yedi köprüyü kullanarak her köprüden sadece bir kez geçerek şehri dolaşmanın mümkün olup olmadığını çizgelerle (graf teorisi) nasıl çözeceğimizi merak ediyorum. Özellikle düğüm noktaları ve kenarlar arasındaki ilişkiyi tam kavrayamadım.

Answer 1

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

Königsberg (günümüzde Kaliningrad) şehrindeki yedi köprü problemi, çizge teorisinin temelini oluşturan ünlü bir matematik problemidir. 18. yüzyılda Leonhard Euler tarafından çözülmüştür.

Problemin Tanımı

Königsberg şehrinde, Pregel Nehri üzerinde 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 şehirde bir tur atılabilir mi?
• Başlangıç ve bitiş noktası aynı olmak zorunda değildir.

Çizge Teorisi ile Modellenmesi

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

• Kara parçaları düğüm (node) olarak gösterilir.
• Köprüler ise bu düğümleri birleştiren kenarlar (edges) olarak temsil edilir.

Euler Yolu ve Euler Devresi

Çözüm için iki kavram önemlidir:

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

Çözümün Matematiksel Koşulları

Bir çizgede Euler devresi olması için:

• Çizge bağlantılı olmalıdır (tüm düğümler birbirine kenarlarla bağlı olmalı).
• Tüm düğümlerin derecesi çift sayı olmalıdır (düğüme bağlı kenar sayısı).

Euler yolu için ise:

• Çizge bağlantılı olmalıdır.
• Sadece iki düğümün derecesi tek olmalı, diğerleri çift olmalıdır.

Königsberg Probleminin Sonucu

Königsberg köprüleri çizgesinde:

• Her düğümün derecesi tek sayıdır (3, 3, 3 ve 5).
• Bu nedenle ne Euler devresi ne de Euler yolu vardır.

Sonuç: Her köprüden bir kez geçerek tur atmak imkansızdır.

Answer 2

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

Soru 1: Königsberg köprüleri probleminin çözümünde kullanılan çizge teorisi kavramı aşağıdakilerden hangisidir?
a) Düğüm derecesi
b) Euler yolu
c) Hamilton çevrimi
d) Renklendirme teoremi
e) Minimum kapsayan ağaç
Cevap: b) Euler yolu
Çözüm: Königsberg köprüleri probleminin çözümü, Euler yolu kavramıyla ilişkilidir. Bir çizgede tüm kenarları bir kez kullanarak yürüyüş yapılabilmesi için Euler yolunun varlığı gerekir.

Soru 2: Aşağıdaki çizgelerden hangisinde Euler yolu vardır?
a) Tüm düğümlerin derecesi tek olan çizge
b) İki düğümün derecesi tek, diğerleri çift olan çizge
c) Tüm düğümlerin derecesi 3 olan çizge
d) Bağlantısız çizge
e) Döngü içermeyen çizge
Cevap: b) İki düğümün derecesi tek, diğerleri çift olan çizge
Çözüm: Euler yolu için en fazla iki düğümün derecesi tek olmalıdır. Bu düğümler yolun başlangıç ve bitiş noktalarını oluşturur.

Soru 3: Königsberg köprüleri probleminin modern çizge teorisi gösteriminde köprüler hangi elemana karşılık gelir?
a) Düğümler
b) Kenarlar
c) Çevreler
d) Ağırlıklar
e) Yönler
Cevap: b) Kenarlar
Çözüm: Çizge teorisinde köprüler kenarlarla, şehrin bölümleri ise düğümlerle temsil edilir. Königsberg probleminin çizgesinde 4 düğüm ve 7 kenar vardır.

Soru 4: Aşağıdaki ifadelerden hangisi Königsberg köprüleri probleminin sonucunu doğru şekilde açıklar?
a) Tüm köprüler tek seferde geçilebilir
b) Sadece belirli bir rota izlenerek tüm köprüler geçilebilir
c) Hiçbir rota tüm köprüleri tek seferde geçmeye izin vermez
d) Köprülerin yarısı geçilebilir
e) Sadece bir köprü atlanarak geçilebilir
Cevap: c) Hiçbir rota tüm köprüleri tek seferde geçmeye izin vermez
Çözüm: Königsberg köprüleri çizgesinde tüm düğümlerin derecesi tektir. Euler yolu için en fazla iki düğümün derecesi tek olabileceğinden, bu problemde çözüm yoktur.