Soru:
Aşağıdaki çizgede, her kenardan tam olarak bir kez geçen bir Euler yolu bulunabilir mi? Bulunabilirse, bu yolun başlangıç ve bitiş düğümleri neler olmalıdır? Çizge düğümleri: K, L, M, N. Kenarlar: K-L, K-M, K-N, L-M, M-N.
Çözüm:
💡 Bir çizgede Euler yolu olması için, çizgenin bağlı olması ve ya 0 ya da 2 tane tek dereceli düğüme sahip olması gerekir. 2 tek dereceli düğüm varsa, yol bu düğümlerden birinde başlar, diğerinde biter.
- ➡️ Adım 1: Çizgenin Bağlılığını Kontrol Et Tüm düğümler birbirine kenarlarla bağlı olduğu için çizge bağlıdır.
- ➡️ Adım 2: Düğüm Derecelerini Hesapla Her bir düğümün derecesini hesaplayalım.
- d(K) = 3 (K-L, K-M, K-N)
- d(L) = 2 (K-L, L-M)
- d(M) = 3 (K-M, L-M, M-N)
- d(N) = 2 (K-N, M-N)
- ➡️ Adım 3: Tek Dereceli Düğüm Sayısını Belirle Hesaplamalara göre, K ve M düğümlerinin dereceleri 3 (tek), L ve N düğümlerinin dereceleri ise 2 (çift)'tir. Yani çizgede 2 tane tek dereceli düğüm (K ve M) vardır.
- ➡️ Adım 4: Euler Yolu Varlığını ve Uç Noktalarını Belirle Euler yolunun var olması için gereken koşul (0 veya 2 tek dereceli düğüm) sağlanmıştır. Bu durumda, Euler yolu kesinlikle vardır ve bu yol, iki tek dereceli düğüm olan K ve M düğümlerinden birinde başlayıp diğerinde bitecektir.
✅ Sonuç olarak, bu çizgede bir Euler yolu bulunabilir. Bu yol ya K'da başlayıp M'de biter, ya da M'de başlayıp K'da biter.
