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

Bir çizgede Euler devresi olması için gerekli ve yeterli koşul aşağıdakilerden hangisidir?

A) Çizgenin tamamen bağlı olması ve tüm köşelerin derecelerinin tek olması
B) Çizgenin tamamen bağlı olması ve tüm köşelerin derecelerinin çift olması
C) Çizgenin tamamen bağlı olması ve en fazla iki köşenin derecesinin tek olması
D) Çizgenin tamamen bağlı olması ve köşe sayısının kenar sayısına eşit olması

• Bir çizgede Euler devresi (veya Euler turu) olması için gerekli ve yeterli koşulu anlamak, çizge teorisindeki temel kavramlardan biridir. Euler devresi, bir çizgedeki her kenarı tam olarak bir kez kullanan ve başladığı köşeye geri dönen bir yoldur.
• Bu soruyu çözmek için, Euler'in çizge teorisine yaptığı katkıları ve Euler devresi teoremini hatırlamamız gerekir.
• Euler Devresi İçin Koşullar:
  • 1. Çizgenin Bağlı Olması: Bir Euler devresi oluşturabilmek için çizgenin bağlı olması şarttır. Eğer çizge bağlı değilse (yani, bazı köşelerden diğerlerine ulaşılamıyorsa), tüm kenarları ziyaret etmek mümkün olmaz. Örneğin, iki ayrı bileşenden oluşan bir çizgede, bir bileşendeki kenarları gezdikten sonra diğer bileşendeki kenarlara geçilemez ve başladığınız yere geri dönülemez.
  • 2. Tüm Köşelerin Derecelerinin Çift Olması: Bu, Euler devresinin en kritik koşuludur. Bir Euler devresi boyunca bir köşeye her girdiğinizde, o köşeden çıkmak için de bir kenar kullanırsınız. Bu, köşeye gelen ve köşeden giden kenarların çiftler halinde olması gerektiği anlamına gelir. Başlangıç ve bitiş köşesi aynı olduğu için, bu kural başlangıç/bitiş köşesi için de geçerlidir. Dolayısıyla, bir köşenin derecesi (o köşeye bağlı kenar sayısı) her zaman çift olmalıdır. Eğer bir köşenin derecesi tek ise, o köşeye girip çıktıktan sonra geriye tek sayıda kenar kalır ve bu da devreyi tamamlamayı imkansız kılar.
• Şimdi seçenekleri inceleyelim:
  • A) Çizgenin tamamen bağlı olması ve tüm köşelerin derecelerinin tek olması: Bu yanlıştır. Tüm köşelerin derecelerinin tek olması durumunda bir Euler devresi oluşturulamaz. Bu durum, daha çok Euler yolu (başlangıç ve bitiş köşesi farklı olan, her kenarı bir kez kullanan yol) ile ilişkilidir ve onda da en fazla iki köşenin derecesi tek olabilir.
  • B) Çizgenin tamamen bağlı olması ve tüm köşelerin derecelerinin çift olması: Bu, Euler devresi için gerekli ve yeterli koşuldur. Yukarıda açıkladığımız gibi, hem bağlılık hem de tüm köşe derecelerinin çift olması, bir Euler devresinin varlığını garanti eder.
  • C) Çizgenin tamamen bağlı olması ve en fazla iki köşenin derecesinin tek olması: Bu, bir Euler yolu için gerekli ve yeterli koşuldur, Euler devresi için değil. Eğer tam olarak iki köşenin derecesi tek ise, bu köşeler Euler yolunun başlangıç ve bitiş noktaları olur. Eğer hiç tek dereceli köşe yoksa (yani tüm dereceler çiftse), bu aynı zamanda bir Euler devresi anlamına gelir. Ancak "en fazla iki" ifadesi, devreden ziyade yolu işaret eder.
  • D) Çizgenin tamamen bağlı olması ve köşe sayısının kenar sayısına eşit olması: Bu, bir Euler devresi için genel bir koşul değildir. Köşe sayısı ile kenar sayısı arasındaki ilişki, çizgenin yapısına (örneğin, ağaçlar veya döngüler) bağlıdır ancak Euler devresinin varlığı için doğrudan bir kriter değildir.

Cevap B seçeneğidir.