Bilgisayar Olimpiyatı 2015, 1. Aşama, Soru 16

## [15 – 17] Sorular için Açıklama
Çizgeler, aşağıdaki şekilde görüldüğü gibi, düğümlerden ve bu düğümleri birbirine bağlayan kenarlardan oluşan veri yapılardır. Kenarlar üzerindeki sayılar, düğümlerin birbirine olan mesafesini göstermektedir. Bir kenarla bağlı iki düğüm birbirinin komşusu sayılmaktadır.
Çizgelerde, kenarları kullanarak bir düğümden başka düğümlerle gitmeye güzergah denilmektedir.
Örneğin, a düğümünden g düğümüne giden güzergahlardan biri a-b-c-e-g şeklindedir.
[GÖRSEL]
Bir düğümden başlayarak, tüm kenarlardan tam olarak bir kere geçerek gidilen güzergaha Euler güzergahı denilmektedir. Euler güzergahında, güzergahın bitişi başlangıç düğümü ile aynı olursa bu güzergaha Euler döngüsü denilmektedir.
Aşağıda Euler döngüsü için geçerli olabilecek bir algoritma tanımlanmıştır:
1. Boş bir yığıt ayarlanır ve bir düğüm başlangıç düğümü olarak seçilir (A düğümü diyelim).
2. A düğümünün komşusu varsa en yakın olan komşusu alınır (B diyelim)
(a) A düğümü yığıta eklenir.
(b) A düğümü ile B düğümü arasındaki kenar silinir.
(c) B düğümü için 2. adımdan itibaren A düğümü gibi işlemler yinelenir.
3. A düğümünün komşusu yoksa
(a) A düğümü çıktıya yazdırılır.
(b) Yığıta bakılır. Eğer yığıtta eleman varsa, yığıttan eleman çıkarılır ve bu eleman için 2. adımdan itibaren A düğümü gibi islemler yinelenir. Yığıtta eleman yoksa 4. adıma gidilir.
4. İşlem bitirilir.
Algoritmada 2-(b) adımında çizgede silinen kenarın tekrar eklenmediğine, sonraki adımların kenarın silinmiş olduğu çizgeye göre yapıldığına dikkat ediniz. Algoritmada bahsi geçen yığıt (stack) ise “son giren ilk çıkar” prensibine göre çalışan veri yapısıdır. Yığıttan bir eleman çıkarılmak istendiğinde, eklenme sırasına göre en son eklenen eleman çıkar.

---

Yukarıda özellikleri verilen parçalı olmayan çizgelerden (her düğümden diğer tüm düğümlere gidebilecek bir güzergah var) hangilerinde Euler güzergahı bulunur? [Bir düğümün derecesi bu düğümün komşu sayısını ifade etmektedir. Çift dereceli düğümler için, bu soruda, O dereceden büyük dereceler kastedilmektedir]

Şıklar:
A) Yalnız I | B) I ve II | C) II ve III | D) I ve IV | E) I, II ve III

Cevap: D I ve IV

Çözüm:
4.adıma götüren şartı inceleyelim. Bu şart, bir düğüme gidilebilmesi fakat o düğümden geri dönebilecek bir kenarın bulunmama durumudur. Yani o düğümün komşu kenarlarını 'git-gel' şeklinde isimlendirirsek (o düğüme geldiye 'gel', o düğümden gittiyse 'git' dersek) 'gel' kenarıyla bitme durumudur.
- Her güzergahta; başlangıç düğümü 'git' ile, diğer düğümler 'gel' ile başlar.
- Yine her güzergahta; bitiş düğümü 'gel' ile, diğer düğümler 'git' ile biter.
Yani, Eğer başlangıç düğümüyle bitiş düğümü farklıysa:
- Başlangıç düğümü 'git' ile başlar 'git' ile biter, tek sayıda komşusu vardır.
- Bitiş düğümü 'gel' ile başlar 'gel' ile biter, tek sayıda komşusu vardır.
- Diğer düğümler 'gel' ile başlar 'git' ile biter, çift sayıda komşusu vardır.
Eğer başlangıç düğümüyle bitiş düğümu aynıysa:
- Başlangıç ve bitiş düğümü 'git' ile başlar 'gel' ile biter, çift sayıda komşusu vardır.
[GÖRSEL]
- Diğer düğümler 'gel' ile başlar'git' ile biter, çift sayıda komşusu vardır.
Sonuç olarak bir çizgedeki bütün kenarları içeren bir güzergah oluşması için en fazla 2 tane tek dereceli düğüm bulunabilir. Tek dereceli düğüm varsa tek dereceliden başlayıp tek dereceliden bitirilmeli. Tek dereceli düğüm yoksa herhangi bir düğümden başlanıp aynı düğümde bitirilebilir. Dolaşma esnasında bitiş düğümüne giden yolu her zaman sona bırakırsak, başka hiçbir düğümde bitemeyeceği için, bitiş düğümüne gelindiğinde bütün yollar alınmış olur. Yani bu şartların sağladığı bir çizgede Euler güzergahı bulunur.