Hamiltonian Cycle and Graph Connections
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. 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) ... (remaining options not visible)
Soruda görsel içerik var: A map with 5 labeled points forming vertices of a graph: A, B, C, D, and E. Red line segments represent bidirectional roads connecting: A-B, A-E, A-C, B-D, B-C, C-D, and D-E.
Animasyonlu Video Çözüm
İlk yarısı ücretsiz izlenebilir, tamamı uygulamada.
Adım Adım Yazılı Çözüm
Merhaba Muhammed, seninle birlikte bu güzel grafik teorisi sorusunu çözelim.
Yol Analizi
Soru bizden Salih'in herhangi bir şehirden başlayıp tüm şehirleri tam bir kez ziyaret ederek geri dönebildiği bir yol bulmamızı istiyor. Matematikte buna Hamilton döngüsü denir.
Salih her şehre bir kez uğrayıp başlangıç noktasına dönebiliyorsa, tüm şehirleri kapsayan bir döngü olmalı.
Şimdi grafiği basitleştirerek şehirler ve aralarındaki yolları daha net görelim.
Şehirler ve Yollar
Görüldüğü üzere A, B, C, D ve E şehirleri var. Her şehrin kaç tane yolu olduğuna bakalım, yani derecelerini bulalım.
| Şehir | Yol Sayısı (Derece) |
|---|---|
| A | 3 (B, E, C) |
| B | 3 (A, D, C) |
| C | 2 (A, B) |
| D | 2 (B, E) |
| E | 2 (A, D) |
Tabloya dikkat edersen, C şehri sadece A ve B şehirlerine bağlı. C'ye girmek ve C'den çıkmak için bu iki yolu da kullanmak zorundadır.
Eğer bir döngü kuruyorsak ve C şehri sadece A ve B'ye bağlıysa, A tire C ve B tire C yollarının her ikisi de mecburen kullanılır.
Çözümün devamı Solvi’de
5 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
