Şehirler Arası Yolculuk Problemi
Yayınlanma:
24. A, B, C, D ve E şehirleri arasındaki çift yönlü yollar aşağıdaki şekilde kırmızı renkli doğru parçaları ile gösterilmiştir. [Şekil] Salih, yolculuğuna bu beş şehrin hangisinden başlarsa başlasın geri kalan tüm şehirlere birer kez uğrayıp başladığı şehre geri dönebilmektedir. Buna göre Salih yolculuğu boyunca hangi iki şehir arasındaki yolu kesinlikle kullanmamıştır? A) A-B B) B-C C) A-E D) E-D E) A-C
Soruda görsel içerik var: Bir düzlem üzerinde A, B, C, D ve E noktaları (şehirler) bulunmaktadır. Bu noktalar arasında kırmızı doğru parçalarıyla gösterilen yollar vardır: A-B, A-C, A-E, B-C, B-D, C-D, D-E. Şekil genel olarak bir çokgeni ve içindeki bağlantıları andırmaktadır.
Animasyonlu Video Çözüm
İlk yarısı ücretsiz izlenebilir, tamamı uygulamada.
Adım Adım Yazılı Çözüm
Merhaba Irmak, bu güzel graf teorisi sorusunu birlikte adım adım inceleyelim.
Şehirler Arasındaki Yollar
Sorudaki grafı daha net görebilmek için şehirleri ve aralarındaki kırmızı yolları tahtamıza çizelim.
Salih'in yapmak istediği yolculuk, başladığı şehre geri dönüp tüm şehirlere tam olarak birer kez uğramaktır. Matematikte buna Hamilton Çevrimi diyoruz.
Hamilton Çevrimi (Hamiltonian Cycle)
Her köşeye tam olarak bir kez uğrayıp başlangıç noktasına dönen kapalı yol.
Bir Hamilton çevriminde, her şehre bir kez girilip bir kez çıkılacağı için, her şehre bağlı olan yollardan tam olarak iki tanesi kullanılmalıdır.
Şimdi tek tek şehirlerin bağlantı sayılarına yani derecelerine bakalım. İlk olarak C şehrine dikkat edelim.
Köşelerin Derecelerini İnceleyelim
- C şehri yalnızca A ve B şehirlerine bağlıdır. Dolayısıyla bu iki yol da kesinlikle kullanılmalıdır.
C şehrine girip çıkabilmek için A C ve B C yollarını yeşil renkle kesin kullanılacak şekilde işaretleyelim.
Aynı mantıkla D şehrine bakalım. D şehri yalnızca B ve E şehirlerine bağlıdır, yani derecesi ikidir.
Çözümün devamı Solvi’de
7 adım daha kilitli. Tamamını animasyonlu ve sesli anlatımla ücretsiz izle.
Fotoğrafını çek, her soruyu böyle çöz.
Çözümün Devamını Ücretsiz İzle
İndirmesi ücretsiz · İlk çözümler hediye
