Königsberg köprüleri probleminin çözümünde, her bir kara parçası bir köşe (vertex) ve her bir köprü bir kenar (edge) olarak modellenmiştir. Bu modele göre aşağıdakilerden hangisi yanlıştır?
A) Graf dört köşeye sahiptir
B) Graf yedi kenara sahiptir
C) Grafın tüm köşelerinin dereceleri tektir
D) Graf bağlantılı değildir
Königsberg köprüleri problemi, graf teorisinin temelini oluşturan klasik bir matematik problemidir. Bu problemde, Königsberg şehrindeki dört kara parçası ve bu kara parçalarını birbirine bağlayan yedi köprü bulunmaktadır. Problemin graf modellemesi şu şekildedir:
- Her bir kara parçası bir köşe (vertex) olarak temsil edilir.
- Her bir köprü bir kenar (edge) olarak temsil edilir.
Bu modellemeye göre, grafın özelliklerini adım adım inceleyelim:
- 1. Köşe Sayısı: Königsberg'de dört farklı kara parçası (iki ada ve iki nehir kıyısı) bulunduğundan, graf modelinde dört köşe vardır.
- 2. Kenar Sayısı: Kara parçalarını birbirine bağlayan toplam yedi köprü bulunduğundan, graf modelinde yedi kenar vardır.
- 3. Köşelerin Dereceleri: Bir köşenin derecesi, o köşeye bağlı olan kenar sayısıdır. Königsberg grafının standart modellemesinde köşelerin dereceleri şöyledir:
- İki kara parçasının derecesi $4$'tür (çift sayı).
- Diğer iki kara parçasının derecesi $3$'tür (tek sayı).
- Yani, grafın köşelerinin dereceleri $4, 4, 3, 3$'tür.
- 4. Bağlantılılık: Königsberg'deki tüm kara parçaları köprüler aracılığıyla birbirine bağlıdır. Herhangi bir kara parçasından diğerine köprüler üzerinden ulaşmak mümkündür. Bu nedenle, graf bağlantılıdır.
Şimdi seçenekleri bu bilgiler ışığında değerlendirelim:
- A) Graf dört köşeye sahiptir
- Königsberg'de dört kara parçası olduğu için, grafın dört köşesi vardır. Bu ifade doğrudur.
- B) Graf yedi kenara sahiptir
- Königsberg'de yedi köprü olduğu için, grafın yedi kenarı vardır. Bu ifade doğrudur.
- C) Grafın tüm köşelerinin dereceleri tektir
- Grafın köşelerinin dereceleri $4, 4, 3, 3$'tür. Bu derecelerden $4$ çift sayıdır. Dolayısıyla, grafın tüm köşelerinin dereceleri tek değildir. Bu ifade yanlıştır.
- D) Graf bağlantılı değildir
- Königsberg grafında tüm kara parçaları köprülerle birbirine bağlıdır ve herhangi bir kara parçasından diğerine ulaşılabilir. Bu nedenle graf bağlantılıdır. "Graf bağlantılı değildir" ifadesi, grafın gerçek yapısıyla çeliştiği için yanlıştır.
Yukarıdaki analizde C ve D seçeneklerinin her ikisinin de yanlış ifadeler olduğu görülmektedir. Ancak, sorunun doğru cevabı D olarak belirtilmiştir. Bu durumda, D seçeneğinin grafın özellikleriyle çelişen yanlış bir ifade olduğu kesindir.
Cevap D seçeneğidir.
