9. Sınıf Çizge Kuramı (Königsberg Şehri) Nedir?

Question

"Çizge kuramını yeni öğreniyorum ve Königsberg köprüleri sorusu kafamı karıştırdı. Bu problemde, şehrin köprülerinden geçerek her köprüyü sadece bir kez kullanarak tur atılıp atılamayacağı soruluyor. Ama mantığını tam kuramadım, neden böyle bir yolun mümkün olmadığını anlamak istiyorum."

Answer 1

Çizge Kuramı ve Königsberg Köprüleri Problemi

Çizge kuramı (graf teorisi), matematiksel yapılar arasındaki ilişkileri inceleyen bir alandır. Düğümler (noktalar) ve bu düğümleri birleştiren kenarlar (çizgiler) ile modellenir. Königsberg köprüleri problemi, bu kuramın temelini oluşturan ünlü bir örnektir.

Königsberg Şehri ve 7 Köprü

18. yüzyılda Königsberg (bugünkü Kaliningrad) şehrinde, Pregel Nehri üzerinde 7 köprü vardı. Şehir, 4 ana bölgeye ayrılıyordu:

• Kuzey kıyı (A)
• Güney kıyı (B)
• Doğu adası (C)
• Batı adası (D)

Problemin sorusu şuydu: "Her köprüden tam bir kez geçerek tüm şehri dolaşmak mümkün mü?"

Euler'in Çözümü

Matematikçi Leonhard Euler, bu problemi çizge kuramıyla çözdü:

• Her bölgeyi bir düğüm (A, B, C, D), köprüleri de kenarlar olarak gösterdi.
• Bir çizgede Euler yolu (tüm kenarlardan bir kez geçen yol) olması için:
• Ya tüm düğümlerin derecesi çift olmalı (kapalı yol),
• Ya da sadece iki düğümün derecesi tek olmalı (açık yol).

Königsberg'in çizgesinde tüm düğümlerin derecesi tek olduğundan, böyle bir yolun olmadığını kanıtladı.

Sonuç

Bu problem, çizge kuramının başlangıcı kabul edilir. Günümüzde ağ tasarımı, bilgisayar bilimi ve ulaşım planlamasında kullanılır.

Answer 2

9. Sınıf Çizge Kuramı (Königsberg Şehri) Çözümlü Test Soruları

1. Königsberg şehrindeki 7 köprü problemini çözmek isteyen Euler, bu problemi çizge kuramına dönüştürürken aşağıdaki kavramlardan hangisini kullanmıştır?
a) Düğümler (köşeler) ve kenarlar
b) Fonksiyonlar ve türevler
c) Matrisler ve determinantlar
d) Olasılık dağılımları
e) Kümeler ve alt kümeler
Cevap: a) Düğümler (köşeler) ve kenarlar. Çözüm: Euler, köprüleri kenarlar, karaları ise düğümler olarak modelleyerek çizge kuramının temelini atmıştır.

2. Bir çizgede tüm düğümlerin derecesi çift sayı ise bu çizge için aşağıdakilerden hangisi kesinlikle doğrudur?
a) Euler devresi vardır
b) Hamilton devresi vardır
c) Ağaç yapısındadır
d) Düzlemsel çizgedir
e) Asimetrik yapıdadır
Cevap: a) Euler devresi vardır. Çözüm: Euler'in teoremine göre, bir çizgede tüm düğüm dereceleri çift ise o çizge üzerinde Euler devresi bulunur.

3. Königsberg köprüleri probleminin çizge kuramındaki karşılığı aşağıdakilerden hangisidir?
a) 4 düğümlü ve 7 kenarlı çizge
b) 7 düğümlü ve 4 kenarlı çizge
c) 3 düğümlü ve 5 kenarlı çizge
d) 5 düğümlü ve 3 kenarlı çizge
e) 2 düğümlü ve 7 kenarlı çizge
Cevap: a) 4 düğümlü ve 7 kenarlı çizge. Çözüm: Königsberg'de 4 ana kara parçası (düğüm) ve bunları birleştiren 7 köprü (kenar) vardır.

4. Aşağıdaki çizgelerden hangisinde Euler yolu bulunabilir?
a) Tüm düğüm dereceleri tek olan çizge
b) İki düğümün derecesi tek, diğerleri çift olan çizge
c) Düğüm derecelerinin toplamı tek olan çizge
d) Tamamen bağlantısız çizge
e) Döngü içermeyen çizge
Cevap: b) İki düğümün derecesi tek, diğerleri çift olan çizge. Çözüm: Euler yolunun var olması için çizgede ya 0 ya da 2 tane tek dereceli düğüm olmalıdır.