9. SINIF MATEMATİK
Algoritma Temelli Problemler
Algoritma ve Bilişim • Mart
Soru metinleri ve çözümler
Soru 1 En az bir kenarı bulunan bağlı, basit yönsüz bir çizgenin her düğümünün derecesi çifttir. Bu çizge için hangi sonuç doğrudur? A) Çizgede hiçbir kapalı yürüyüş olamaz. B) Kenar sayısı mutlaka düğüm sayısının yarısıdır. C) Düğümlerden her birine tam bir kez uğrayan Hamilton döngüsü kesin vardır. D) Bütün düğümlerin derecesi mutlaka 2’dir. E) Her kenardan tam bir kez geçip başlangıca dönen bir Euler döngüsü vardır. Doğru cevap E. Bağlı yönsüz çizgede bütün dereceler çiftse Euler döngüsü vardır. Bu koşul tek başına Hamilton döngüsünü veya bütün derecelerin 2 olmasını garanti etmez. Soru 2 Bağlı basit yönsüz bir çizgede tam iki düğümün derecesi tek, kalanların derecesi çifttir. Hangi sonuç uygundur? A) Çizgede hiçbir yol bulunamaz. B) Başlangıca dönen Euler döngüsü kesin vardır. C) Her düğümün derecesi zorunlu olarak aynıdır. D) Bütün düğümlerin derecesi tektir. E) Her kenarı tam bir kez kullanan açık Euler yolu vardır. Doğru cevap E. Tam iki tek dereceli düğüm bağlı çizgede açık Euler yolunun uçlarıdır. Başlangıca dönen Euler döngüsü için bütün dereceler çift olmalıdır. Soru 3 Bir öğrenci Euler yolunu “Her düğüme yalnız bir kez uğramak” diye tanımlıyor. Doğru düzeltme hangisidir? A) Euler yolu yalnız bütün düğümlerin adını sıralamaktır. B) Euler yolu ile Hamilton yolu her çizgede aynı tanımdır. C) Euler yolunda hiçbir kenar kullanılamaz. D) Euler yolunda temel koşul her kenarın tam bir kez kullanılmasıdır; düğüm tekrar edebilir. E) Euler yolunda kenarlar sınırsız tekrarlanmak zorundadır. Doğru cevap D. Euler kavramı kenar kullanımına odaklanır. Hamilton yolu düğümleri tam bir kez ziyaret etme koşuluyla ilgilidir; iki kavram karıştırılmaz.