9. Sınıf Matematik 2. Ders Kitabı Sayfa 117-118-119-120 Cevapları Meb Yayınları

5. Uygulama

Königsberg Şehrindeki Yürüyüş Rotası Problemini Çizgeler Yardımıyla Çözümleme
Verilen bilgileri inceleyerek aşağıdaki soruları cevaplayınız.
1. Aşağıdaki tabloda verilen görsellerde bir şehirdeki belirli noktalar arasındaki farklı yolları temsil eden çizgeler yer almaktadır. Buna göre A noktasından yola çıkan bir kişi her yolu yalnızca bir kez kullanmak şartıyla başladığı noktaya dönüyorsa , dönemiyorsa sembolü kullanarak tabloyu örnekteki gibi doldurunuz.

Königsberg Şehrindeki Yürüyüş Rotası Problemi Çözümü

3. Soru Cevabı:

Tek ve çift sayıda ayrıtların çizimin kalemi kaldırmadan yapılabilmesine etkisi nedir?

Cevap: Bir çizgenin Euler çevrimi olup olmadığını anlamak için düğümlerin ayrıt sayıları incelenmelidir:

• Tüm düğümler çift sayıda ayrıt içeriyorsa, kalemi kaldırmadan başladığı noktaya dönebilir (Euler çevrimi vardır).
• Eğer sadece iki düğüm tek dereceli ise, Euler yolu vardır ama başladığı noktaya dönemez.

Bu nedenle, düğüm ayrıtlarının tek veya çift olması, bir rotanın çizilip çizilemeyeceğini belirleyen en önemli faktördür.

4. Soru Cevapları:

a) Çizgede her bir düğümün ayrıt sayısının tek ya da çift olmasının rota planlamasına etkisi var mıdır?

Düğümlerin ayrıt sayıları:

• A düğümü: 5 ayrıt (tek)
• B düğümü: 3 ayrıt (tek)
• C düğümü: 3 ayrıt (tek)
• D düğümü: 3 ayrıt (tek)

Sonuç:

• Tüm düğümler tek sayıda ayrıt içerdiği için Euler çevrimi ve Euler yolu mümkün değildir.
• Bu nedenle her köprüden yalnızca bir kez geçerek rotayı tamamlamak olanaksızdır.
• Alternatif çözüm: Eğer tüm köprüleri kullanarak geçiş yapmak istiyorsak, bazı köprülerden birden fazla geçmek gerekecektir.

Bu analiz, Euler yolu ve Euler çevrimi kurallarına uygun olarak doğru bir yaklaşımdır.

b) Her köprüden yalnızca bir kez geçmek şartıyla belirlediğiniz bir başlangıç noktasına dönmek mümkün mü? Eğer değilse, çözüm için bir algoritmanın çalışması için gereken girdileri ve beklenen çıktıları tanımlayınız.

Cevap: Hayır, mümkün değildir. Çünkü Königsberg Köprü Problemi'nde tüm düğümler tek derecelidir. Euler çevrimi veya Euler yolu için uygun şartlar sağlanmadığı için, her köprüden yalnızca bir kez geçerek başladığımız noktaya geri dönemeyiz.

Alternatif bir çözüm için algoritma girdileri ve çıktıları:

• Girdi: Şehirdeki noktalar (düğümler) ve köprüler (ayrıtlar).
• İşlem: Tüm düğümleri analiz ederek, hangi noktaların tek veya çift dereceli olduğunu belirlemek.

Çıktı:

• Eğer tüm düğümler çift ise: Euler çevrimi mümkündür, bir rota oluşturulabilir.
• Eğer iki düğüm tek ise: Euler yolu mümkündür, ancak başladığı noktaya dönemez.
• Eğer ikiden fazla tek düğüm varsa: Hiçbir Euler yolu veya çevrimi mümkün değildir. Alternatif olarak, bazı yolları birden fazla kez kullanmayı gerektiren bir çözüm aranmalıdır.

Bu sayede, rota planlamasında Euler yolu ve çevrimi prensipleri kullanılarak uygun algoritmalar geliştirilebilir.

c) Algoritmik doğal dil ve akış şeması yardımıyla algoritmanın işleyişini açıklayınız.

Akış Şeması için Adımlar

1-Başla
2- Düğümleri ve ayrıt sayılarını al

• A düğümü → 5 ayrıt (tek)
• B düğümü → 3 ayrıt (tek)
• C düğümü → 3 ayrıt (tek)
• D düğümü → 3 ayrıt (tek)

3- Düğümlerin tek ya da çift olup olmadığını kontrol et

• Eğer tüm düğümler çiftse → Euler çevrimi vardır → "Başladığın noktaya dönebilirsin" yazdır
• Eğer yalnızca iki düğüm tekse → Euler yolu vardır → "Başladığın noktaya dönemezsin" yazdır
• Eğer ikiden fazla tek düğüm varsa → Euler çevrimi de Euler yolu da yoktur → "Her ayrıtı bir kez kullanarak aynı noktaya dönülemez" yazdır

4- Sonucu ekrana yazdır
5- Bitir

Akış Şeması Tasarımı

• Başlangıç noktası: "Başla"
• Girdi: "Düğümleri ve ayrıt sayılarını al"

Karar Bloğu: "Tüm düğümler çift mi?"

• Evet → Euler çevrimi var → "Başladığın noktaya dönebilirsin" yazdır
• Hayır → İkiden fazla tek düğüm var mı?
  • Evet → Euler yolu da çevrimi de yoktur → "Her ayrıtı bir kez kullanarak aynı noktaya dönülemez" yazdır
  • Hayır → Euler yolu vardır ama çevrim yok → "Başladığın noktaya dönemezsin" yazdır
• Çıkış: "Bitir"

ç) Elde ettiğiniz algoritmayı farklı durumlar (köprülerden birinin kullanım dışı kalması, bir düğüm noktasına yeni ayrıtlar eklenmesi vb.) için test ediniz.

Görselde Königsberg Köprü Problemi'nin farklı bir durumu test edilmiş. Düğümlerin ayrıt sayıları şu şekilde belirlenmiş:

• A düğümü → 4 ayrıt (çift)
• B düğümü → 3 ayrıt (tek)
• C düğümü → 3 ayrıt (tek)
• D düğümü → 2 ayrıt (çift)

Bu Durumda Euler Yolu ve Çevrimi Kontrolü:

Euler Çevrimi Var mı?

• Tüm düğümler çift sayıda ayrıt içermelidir.
• B ve C düğümleri tek dereceli olduğu için Euler çevrimi mümkün değildir.
• Sonuç: Euler çevrimi yok.

Euler Yolu Var mı?

• Eğer sadece iki düğüm tek sayıda ayrıt içeriyorsa, Euler yolu mümkündür.
• B ve C tek sayıda ayrıt içerdiği için Euler yolu mümkündür.
• Bu durumda bir noktadan başlayıp diğer tek dereceli düğümde bitirebiliriz.
• Sonuç: Euler yolu var ama başladığımız noktaya dönemeyiz.

6. Uygulama

Temiz Çevre En İyileme Problemi
Verilen bilgileri inceleyerek aşağıdaki soruları cevaplayınız.

1. Tablodaki verileri kullanarak toplam mesafeyi en aza indirmeye çalışınız.

Önerilen Rota ve Toplam Mesafe:

• A → B = 133 birim
• B → C = 96 birim
• C → D = 103 birim
• D → A = 70 birim

Toplam Mesafe:

133+96+103+70=402 birim

Bu rota, çöp depoları arasında en kısa toplam mesafeyi veren yollardan biridir. Alternatif rotalar da kontrol edilebilir ancak bu rota, en kısa mesafeyi veren optimal çözümlerden biri olarak görünmektedir.

2. Tablodaki verileri kullanarak düğümler A, B, C ve D; ayrıtlar mesafeleri verilen sorumluluk sahasındaki yollar olacak şekilde bir çizge oluşturunuz.

Çizge Bilgileri ve Rota

Önerilen A → B → C → D → A rotası şu mesafelerle belirlenmiştir:

• A → B = 133 birim
• B → C = 96 birim
• C → D = 103 birim
• D → A = 70 birim

Bu rota, çöp arabasının tüm noktaları en kısa toplam mesafe ile dolaşmasını sağlar.

3. Soru: Toplam mesafeyi en aza indiren algoritmanın çalışması için gereken girdi verilerini ve beklenen çıktıları tanımlayınız.

Girdi ve Beklenen Çıktılar

Girdi Verileri:

Düğümler (Çöp Depoları): A, B, C, D

Düğümler arasındaki mesafeler:

• A → B = 133
• B → C = 96
• C → D = 103
• D → A = 70

Beklenen Çıktı:

• En kısa mesafeyi veren rota:
  • A → B → C → D → A
• Toplam minimum mesafe: 133+96+103+70=402 birim133 + 96 + 103 + 70 = 402 \text{ birim}133+96+103+70=402 birim
• Sonuç: Çöp arabasının tüm noktaları en kısa toplam mesafe ile dolaştığı optimal rota belirlenmiş olur.

Bu yanıt, Gezgin Satıcı Problemi (TSP) mantığıyla toplam mesafeyi en aza indiren en uygun rotayı belirlemeye yönelik doğru bir yaklaşımdır.

4. En Kısa Mesafeyi Bulan Algoritma Tasarımı

Bu bölümde algoritmik doğal dil, akış şeması ve sözde kod (pseudo code) kullanarak en kısa mesafeyi hesaplayan algoritmayı tanımlayacağız.

Algoritmik Doğal Dil ile Açıklama

1. Başla
2. Düğümleri ve mesafeleri tanımla (A, B, C, D ve aralarındaki mesafeler)
3. Tüm olası rotaları oluştur
4. Her rotanın toplam mesafesini hesapla
5. En kısa mesafeye sahip olan rotayı belirle
6. Sonucu ekrana yazdır (Örneğin: "En kısa rota: A → B → C → D → A, Toplam mesafe: 402 birim")
7. Bitir

Akış Şeması Tasarımı

1. Başlangıç
2. Düğümler ve mesafeler tanımlanır
3. Tüm rotalar oluşturulur
4. Rotaların toplam mesafesi hesaplanır
5. Minimum mesafeli rota belirlenir
6. Sonuç ekrana yazdırılır
7. Bitiş

Sözde Kod (Pseudo Code)

Başla Düğümler = {A, B, C, D}
Mesafeler = { (A, B) = 133, (B, C) = 96, (C, D) = 103, (D, A) = 70, (C, A) = 100, (B, D) = 200 }

minMesafe = ∞
enKısaRota = []

Tüm olası rotalar için:
toplamMesafe = seçilen rotadaki mesafelerin toplamı
Eğer toplamMesafe < minMesafe ise:
minMesafe = toplamMesafe
enKısaRota = seçilen rota
En kısa rotayı ve toplam mesafeyi yazdır
Bitir

5. En Kısa Rota ve Mesafe

Önceki hesaplamalar doğrultusunda en kısa rota:

• A → B → C → D → A
• Toplam mesafe: 402 birim

Bu algoritma, Gezgin Satıcı Problemi (TSP) yaklaşımıyla optimal rotayı belirleyerek çöp arabasının en kısa mesafeyi kat etmesini sağlar.

6. En İyi Rotanın Belirlenmesi

Toplam mesafeyi en aza indiren rotalar arkadaşlarınkiyle karşılaştırılarak en iyi rota seçilmelidir. En kısa mesafeyi sağlayan rota şu şekilde hesaplanmıştı:

• A → B → C → D → A
• Toplam Mesafe: 402 birim
  Diğer rotalarla karşılaştırıldığında bu rota en düşük toplam mesafeyi veriyorsa, bu rota en iyi rota olarak belirlenmelidir.

7. Çöp Deposu Sayısı Artarsa Algoritmanın Performansı Nasıl Etkilenir?

• Daha fazla düğüm (çöp deposu) eklenirse, olası rotaların sayısı üstel olarak artar.
• Gezgin Satıcı Problemi (TSP) için klasik çözüm yolları (brute-force gibi) çok daha uzun sürede çalışır.
• N düğüm varsa, olası rotaların sayısı (N-1)! kadar artar.
• Çözüm süresi arttığı için algoritma daha yavaş çalışır ve performans düşer.

8. Performansı Artırmak İçin Stratejiler ve Alternatif Algoritmalar

Performansı artırmak için aşağıdaki yaklaşımlar önerilebilir:

✅ Yaklaşık Algoritmalar Kullanma:

• Gezgin Satıcı Problemi (TSP) için Yakın Komşu Algoritması (Nearest Neighbor) veya Genetik Algoritmalar kullanılabilir.
• Dinamik Programlama (Held-Karp Algoritması) kullanılabilir.

✅ Heuristik ve Optimizasyon Teknikleri:

• Simulated Annealing (Benzetilmiş Tavlama)
• Ant Colony Optimization (Karınca Kolonisi Optimizasyonu)
• Branch and Bound (Dallanma ve Budama) gibi algoritmalar tercih edilebilir.

✅ Hızlı Hesaplama İçin Graf Optimizasyonu:

• Dijkstra veya Floyd-Warshall Algoritmaları ile en kısa mesafeler önceden hesaplanabilir.
• Yaklaşık en iyi çözüm veren algoritmalar tercih edilebilir.

9. Tablo mu, Çizge mi Daha Verimli?

Tablo ve çizge farklı avantajlar sunar:

• Tablo: Mesafeleri sayısal olarak net gösterdiği için hesaplamalar kolaydır.
• Çizge: Görsellik sağladığı için algoritmaların mantığını anlamayı kolaylaştırır.
• Hız açısından tablo verileri daha pratik olsa da, büyük ölçekli problemlerde çizgeler kullanılarak grafik tabanlı algoritmalarla çözüm daha verimli hale getirilebilir.

Sonuç: Küçük ölçekli problemlerde tablo daha iyi; büyük ölçekli problemlerde çizge kullanımı daha avantajlıdır.

10. Gerçek Yaşamda Benzer Problemler

Bu problem birçok gerçek dünya uygulaması ile benzerlik gösterir:

Lojistik ve Dağıtım Problemleri:

• Kargo şirketlerinin en kısa sürede teslimat yapması (DHL, UPS, Amazon vb.).
• Marketler için tedarik zinciri optimizasyonu.

Atık Toplama ve Çöp Kamyonu Rotalaması:

• Şehirlerde çöp kamyonlarının en kısa sürede çöp toplaması.
• Belediyeler için yakıt tüketimini azaltarak maliyet optimizasyonu.

Taksi ve Uber Rotaları:

• Uber, Lyft gibi uygulamalarda en kısa sürede müşteri almak ve bırakmak için rota planlaması.

Depo Yönetimi ve Üretim Hatları:

• Amazon gibi şirketlerin depo içi robotları için en hızlı yolu bulma.
• Üretim hatlarında en kısa sürede malzeme taşıma planlaması.

Bu tarz problemler Gezgin Satıcı Problemi (TSP) ile benzerlik gösterir ve optimizasyon algoritmalarıyla çözülür.