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

Bir postacı, görev bölgesindeki tüm sokakları (her sokağı tam bir kez kullanarak) dolaşmak ve deposuna geri dönmek istiyor. Aşağıdaki sokak ağını temsil eden çizgede bu mümkün müdür? Çizge düğümleri: X, Y, Z, T. Kenarlar: X-Y, X-Z, X-T, Y-Z, Z-T, T-Y. (Not: X-Y kenarı X ve Y arasında bir sokaktır.)

💡 Postacının istediği rotayı bulabilmesi için, çizgede bir Euler devresi olması gerekir. Euler devresinin var olma koşulu, çizgenin bağlı olması ve tüm düğümlerin çift dereceli olmasıdır.

• ➡️ Adım 1: Çizgenin Bağlı Olup Olmadığını Kontrol Et Verilen kenar listesine bakıldığında, her düğüm diğer düğümlere bir veya daha fazla kenarla bağlıdır. Örneğin, X, Y, Z ve T'ye bağlıdır. Bu, çizgenin bağlı olduğunu gösterir.
• ➡️ Adım 2: Düğüm Derecelerini Hesapla Her bir düğüme bağlı olan kenar sayısını hesaplayalım.
  • d(X) = 3 (X-Y, X-Z, X-T)
  • d(Y) = 3 (X-Y, Y-Z, T-Y)
  • d(Z) = 3 (X-Z, Y-Z, Z-T)
  • d(T) = 3 (X-T, Z-T, T-Y)
• ➡️ Adım 3: Euler Devresi Kriterini Uygula Tüm düğümlerin derecesi 3'tür, yani tektir. Euler devresi için tüm düğümlerin çift dereceli olması şartı sağlanmamaktadır.

✅ Sonuç olarak, bu sokak ağında (çizgede) Euler devresi bulunmamaktadır. Dolayısıyla, postacı her sokağı tam bir kez kullanarak deposuna dönemez.