9. Sınıf Königsberg Şehrindeki Yürüyüş Rotası Problemini Çizgeler Yardımıyla Çözümleme Nedir? Test 1

Bir şehirdeki köprülerin %75'i yıkıldığında, Königsberg köprüleri probleminin sonucu nasıl değişir?

A) Euler yolu her zaman mümkün hale gelir
B) Euler yolu hiçbir zaman mümkün olmaz
C) Graf bağlantılı olmayabilir
D) Köşe dereceleri her zaman çift olur

Merhaba sevgili öğrenciler!

Bu soru, ünlü Königsberg Köprüleri Problemi'nin temel mantığını ve graf teorisindeki Euler yolu/devresi kavramlarını ne kadar iyi anladığınızı ölçüyor. Adım adım bu problemi inceleyelim:

• 1. Königsberg Köprüleri Problemi'nin Temeli:

  Orijinal Königsberg Köprüleri Problemi, Prusya'nın Königsberg şehrindeki (şimdiki Kaliningrad, Rusya) dört kara parçasını birbirine bağlayan yedi köprüden oluşuyordu. Problem, her köprüden tam olarak bir kez geçerek bir turu tamamlamanın (Euler devresi) veya bir yolculuk yapmanın (Euler yolu) mümkün olup olmadığını soruyordu.

• 2. Euler Yolu/Devresi İçin Koşullar:

  Matematikçi Euler, bu problemi graf teorisi kullanarak çözdü ve bir graf üzerinde Euler yolu veya devresi olabilmesi için belirli koşullar olduğunu gösterdi:

  • Euler Yolu İçin: Grafın bağlantılı olması ve en fazla iki köşesinin (kara parçaları) derecesinin (o köşeye bağlı köprü sayısı) tek olması gerekir.
  • Euler Devresi İçin: Grafın bağlantılı olması ve tüm köşelerinin derecelerinin çift olması gerekir.

  Orijinal Königsberg grafında, dört kara parçasının da dereceleri tek sayıdaydı (3, 3, 3, 5). Bu nedenle, ne bir Euler yolu ne de bir Euler devresi mümkün değildi.

• 3. Köprülerin %75'inin Yıkılmasının Etkisi:

  Şehirde başlangıçta 7 köprü vardı. Bu köprülerin %75'i yıkılırsa:

  • Yıkılan köprü sayısı: $7 \times 0.75 = 5.25$. Köprüler bütün olduğu için, bu yaklaşık olarak 5 veya 6 köprünün yıkıldığı anlamına gelir.
  • Geriye kalan köprü sayısı: Eğer 5 köprü yıkılırsa, $7 - 5 = 2$ köprü kalır. Eğer 6 köprü yıkılırsa, $7 - 6 = 1$ köprü kalır.

  Görüldüğü gibi, geriye çok az sayıda köprü kalacaktır.

• 4. Grafın Bağlantılılığına Etkisi:

  Bir grafın Euler yolu veya devresi içerebilmesi için en temel koşul, grafın bağlantılı olmasıdır. Yani, tüm kara parçaları arasında bir şekilde köprüler aracılığıyla geçiş mümkün olmalıdır. Orijinalde 7 köprü varken bile, bu köprüler kara parçalarını belirli şekillerde bağlıyordu.

  Ancak, köprülerin %75'i yıkıldığında (yani sadece 1 veya 2 köprü kaldığında), dört farklı kara parçasını birbirine bağlı tutmak neredeyse imkansız hale gelir. Büyük olasılıkla, bazı kara parçaları diğerlerinden tamamen izole olacaktır. Örneğin, sadece bir köprü kalırsa, o köprü sadece iki kara parçasını birbirine bağlar; diğer iki kara parçası izole kalır. Bu durumda, graf bağlantısız hale gelir.

• 5. Seçeneklerin Değerlendirilmesi:
  • A) Euler yolu her zaman mümkün hale gelir: Bu kesinlikle yanlış bir ifadedir. Graf bağlantısız hale gelirse, Euler yolu mümkün olamaz. Ayrıca, kalan köprüler her zaman uygun köşe dereceleri sağlamayabilir.
  • B) Euler yolu hiçbir zaman mümkün olmaz: Bu da çok güçlü bir ifadedir. Çok düşük bir olasılıkla da olsa, kalan köprüler grafı bağlantılı tutar ve Euler yolu koşullarını (en fazla iki tek dereceli köşe) sağlarsa, mümkün olabilir. "Hiçbir zaman" demek, bu olasılığı tamamen dışlar.
  • C) Graf bağlantılı olmayabilir: Bu, köprülerin büyük bir kısmının yıkılmasının en olası ve önemli sonucudur. Sadece 1 veya 2 köprü ile dört kara parçasını birbirine bağlı tutmak çok zordur. Eğer graf bağlantılı değilse, Euler yolu veya devresi arayışının bir anlamı kalmaz. Bu, Euler yolu probleminin sonucunu kökten değiştirir.
  • D) Köşe dereceleri her zaman çift olur: Bu da doğru değildir. Kalan az sayıdaki köprüler, köşelerin derecelerini rastgele etkiler. Örneğin, tek bir köprü kalırsa, o köprünün bağladığı iki kara parçasının derecesi 1 (tek) olur.

Sonuç olarak, köprülerin %75'inin yıkılmasıyla geriye kalan az sayıdaki köprü, grafın bağlantılılığını büyük ölçüde tehlikeye atar. Bir graf bağlantılı değilse, üzerinde bir Euler yolu veya devresi bulunamaz. Bu yüzden, Königsberg köprüleri probleminin sonucu üzerindeki en belirgin ve temel değişiklik, grafın bağlantılı olmayabilmesidir.

Cevap C seçeneğidir.