9. Sınıf Çizge Kuramı (Königsberg Şehri) Nedir? Test 2

Bir postacı tüm sokakları her biri sadece bir kez kullanarak turunu tamamlamak istiyor. Bu problem hangi tür çizge problemine örnektir?

A) Hamilton yolu problemi
B) Renklendirme problemi
C) En kısa yol problemi
D) Euler yolu problemi

Bu problem, çizge teorisinin temel konularından biridir ve günlük hayattaki birçok optimizasyon problemine benzer. Soruyu adım adım inceleyelim:

• Problemi Anlamak: Bir postacı, tüm sokakları (yolları) her biri sadece bir kez kullanarak turunu tamamlamak istiyor. Çizge teorisi açısından düşündüğümüzde:
  • "Sokaklar" çizgedeki kenarları (edges) temsil eder.
  • "Kavşaklar" veya sokakların kesişim noktaları çizgedeki düğümleri (vertices) temsil eder.
  Problemin ana odağı, tüm kenarları (sokakları) sadece bir kez ziyaret etmektir.
• Seçenekleri Değerlendirmek:
• A) Hamilton yolu problemi: Bu problem, bir çizgedeki tüm düğümleri (kavşakları) her biri sadece bir kez ziyaret eden bir yol veya döngü bulmakla ilgilidir. Postacının problemi sokakları (kenarları) ziyaret etmekle ilgili olduğundan, bu seçenek doğru değildir.
• B) Renklendirme problemi: Bu problem, bir çizgenin düğümlerine veya kenarlarına belirli kurallara göre (örneğin, komşu düğümlerin farklı renkte olması) renk atamakla ilgilidir. Postacının turuyla doğrudan bir ilgisi yoktur.
• C) En kısa yol problemi: Bu problem, iki belirli düğüm (kavşak) arasındaki en kısa yolu bulmakla ilgilidir. Postacının problemi tüm sokakları ziyaret etmek olduğundan, bu seçenek de doğru değildir.
• D) Euler yolu problemi: Bu problem, bir çizgedeki tüm kenarları (sokakları) her biri sadece bir kez kullanarak geçen bir yol veya döngü bulmakla ilgilidir. Eğer yol başladığı noktaya geri dönüyorsa buna Euler devresi (Euler circuit) denir. Postacının tüm sokakları birer kez kullanarak turunu tamamlaması, tam olarak Euler yolu veya Euler devresi probleminin tanımına uymaktadır. Bu tür problemler, Königsberg'in Yedi Köprüsü problemi gibi klasik örneklerle tanınır.
• Sonuç: Postacının tüm sokakları (kenarları) sadece bir kez kullanarak turunu tamamlaması, çizgedeki tüm kenarları dolaşmayı gerektirdiğinden, Euler yolu problemi kategorisine girer.

Cevap D seçeneğidir.