Königsberg şehrindeki 7 köprü problemi için aşağıdaki çizge gösterimi yapılmıştır. Çizgedeki köşeler şehrin bölgelerini, kenarlar ise köprüleri temsil etmektedir.
Bu çizge üzerinde Euler yolu bulunup bulunmadığını belirlemek için hangi özellik kontrol edilmelidir?
A) Tüm köşelerin derecelerinin eşit olup olmadığı
B) Tek dereceli köşe sayısının 0 veya 2 olup olmadığı
C) Çizgenin bağlı olup olmadığı
D) Kenar sayısının köşe sayısından fazla olup olmadığı
Königsberg'deki 7 köprü problemi, çizge teorisinin temelini oluşturan klasik bir problemdir. Bu problem, bir şehrin tüm köprülerinden her birini tam olarak bir kez kullanarak geçip başlangıç noktasına dönmenin veya farklı bir noktada bitirmenin mümkün olup olmadığını sorgular. Bu tür bir yolculuğa çizge teorisinde Euler yolu veya Euler devresi denir.
Bir çizge üzerinde Euler yolu bulunup bulunmadığını belirlemek için kontrol etmemiz gereken temel özellik, çizgedeki köşelerin dereceleridir. Bir köşenin derecesi, o köşeye bağlı olan kenar (köprü) sayısıdır.
- Euler Yolu Nedir? Bir çizgedeki tüm kenarları (köprüleri) her birini tam olarak bir kez kullanarak geçen bir yoldur. Başlangıç ve bitiş noktaları farklı olabilir.
- Euler Devresi (Euler Turu) Nedir? Bir çizgedeki tüm kenarları (köprüleri) her birini tam olarak bir kez kullanarak geçen ve başlangıç noktasına geri dönen bir yoldur. Yani başlangıç ve bitiş noktaları aynıdır.
Şimdi seçenekleri inceleyelim:
-
A) Tüm köşelerin derecelerinin eşit olup olmadığı: Bu özellik, bir Euler yolu veya devresi için doğrudan bir koşul değildir. Bir çizgede Euler devresi olması için tüm köşelerin derecelerinin çift olması gerekir, ancak eşit olması şart değildir (örneğin, bir köşenin derecesi 2, diğerinin 4 olabilir). Euler yolu için ise durum daha farklıdır. Bu nedenle A seçeneği doğru değildir.
-
B) Tek dereceli köşe sayısının 0 veya 2 olup olmadığı: Bu, bir çizgede Euler yolu veya devresi bulunup bulunmadığını belirlemek için kullanılan temel ve en önemli özelliktir.
- Eğer çizgedeki tüm köşelerin dereceleri çift ise (yani tek dereceli köşe sayısı 0 ise), çizgede bir Euler devresi (ve dolayısıyla bir Euler yolu) vardır. Bu durumda herhangi bir köşeden başlayıp aynı köşede bitirebiliriz.
- Eğer çizgede tam olarak iki tane tek dereceli köşe varsa, çizgede bir Euler yolu vardır ancak bir Euler devresi yoktur. Bu durumda Euler yolu, tek dereceli köşelerden birinden başlar ve diğer tek dereceli köşede biter.
- Eğer çizgede ikiden fazla tek dereceli köşe varsa (örneğin 4, 6, 8...), o zaman çizgede ne bir Euler yolu ne de bir Euler devresi bulunmaz.
Königsberg köprüleri probleminde, çizgenin tek dereceli köşe sayısı 4'tür, bu yüzden Euler yolu veya devresi yoktur. Ancak genel kuralı sorduğu için bu seçenek doğru koşulu ifade eder.
-
C) Çizgenin bağlı olup olmadığı: Bir çizgede Euler yolu veya devresi bulunabilmesi için çizgenin bağlı olması (yani tüm köşeler arasında bir yol olması) kesinlikle gereklidir. Eğer çizge bağlı değilse, tüm kenarları tek bir yolla geçmek mümkün olmaz. Ancak, bağlı olmak tek başına yeterli bir koşul değildir. Bağlı bir çizgede bile tek dereceli köşe sayısı ikiden fazlaysa Euler yolu bulunmaz. Bu nedenle C seçeneği gerekli bir koşul olsa da, Euler yolu varlığını belirleyen ana özellik değildir.
-
D) Kenar sayısının köşe sayısından fazla olup olmadığı: Kenar ve köşe sayıları arasındaki ilişki, bir çizgede Euler yolu bulunup bulunmadığını doğrudan belirleyen bir özellik değildir. Bu ilişki, çizgenin yoğunluğu veya farklı türdeki çizge özellikleri (örneğin ağaç olup olmadığı) hakkında bilgi verebilir, ancak Euler yolu varlığıyla doğrudan ilgili değildir. Bu nedenle D seçeneği doğru değildir.
Yukarıdaki açıklamalara göre, bir çizge üzerinde Euler yolu bulunup bulunmadığını belirlemek için kontrol edilmesi gereken en kritik özellik, tek dereceli köşe sayısının 0 veya 2 olup olmadığıdır.
Cevap B seçeneğidir.
