Soru:
Aşağıda bir çizge verilmiştir. Bu çizgede, her kenardan tam olarak bir kez geçen ve başladığı noktaya dönen bir Euler devresi (Eulerian circuit) var mıdır? Nedenini açıklayınız. Çizge düğümleri: P, Q, R, S. Kenarlar: P-Q, P-R, P-S, Q-R, R-S.
Çözüm:
💡 Bir çizgede Euler devresinin var olması için, çizgenin bağlı olması ve tüm düğümlerinin çift dereceye sahip olması gerekir.
- ➡️ Adım 1: Çizgeyi Görselleştir/Anla Verilen kenar listesine göre çizge şu şekildedir: P düğümü Q, R ve S'ye bağlıdır. Q düğümü P ve R'ye bağlıdır. R düğümü P, Q ve S'ye bağlıdır. S düğümü P ve R'ye bağlıdır.
- ➡️ Adım 2: Düğüm Derecelerini Hesapla Her bir düğümün derecesini (bağlı olduğu kenar sayısını) bulalım.
- d(P) = 3 (P-Q, P-R, P-S)
- d(Q) = 2 (P-Q, Q-R)
- d(R) = 3 (P-R, Q-R, R-S)
- d(S) = 2 (P-S, R-S)
- ➡️ Adım 3: Euler Devresi Kriterini Kontrol Et Euler devresi için tüm düğümlerin derecesi çift olmalıdır. Bu çizgede P ve R düğümlerinin dereceleri 3'tür (tek sayı).
✅ Sonuç olarak, bu çizgede tek dereceli düğümler bulunduğu için bir Euler devresi yoktur. Yani, her köprüden bir kez geçip başlangıç noktasına dönmek mümkün değildir.
