Hamiltonian Cycle Analysis
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.
[Visual Representation of Graph with vertices A, B, C, D, E]
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: A planar graph with 5 vertices labeled A, B, C, D, and E. The edges (roads) are as follows: A-B, A-C, A-E, B-C, B-D, C-D, C-E, and D-E. D is connected to B, C, E. C is connected to A, B, D, E. A is connected to B, C, E. B is connected to A, C, D. E is connected to A, C, D.
Animasyonlu Video Çözüm
İlk yarısı ücretsiz izlenebilir, tamamı uygulamada.
Adım Adım Yazılı Çözüm
Merhaba Elif. Bu soruda bir graf teorisi problemi ile karşı karşıyayız. Şehirler arası yolları inceleyerek Salih'in hangi yolu hiç kullanmadığını bulalım.
Şehirler Arası Yollar ve Hamilton Döngüsü
Soru, Salih'in herhangi bir şehirden başlayıp, diğer tüm şehirlere tam birer kez uğrayarak başladığı şehre dönebildiğini söylüyor. Matematikte biz buna Hamilton döngüsü diyoruz.
Salih her şehre tam 1 kez uğrayıp geri dönebiliyorsa, tüm şehirleri kapsayan bir döngü bulmalıyız.
Önce elimizdeki yolları yani grafı daha net görelim. Şehirleri nokta, yolları çizgi olarak çiziyorum.
Şehir Grafı
Grafı incelediğimizde dikkat çeken bir durum var. D şehri sadece B ve E şehirlerine bağlıdır.
Bir döngü oluşturmak için, her şehre bir yoldan girip diğerinden çıkmamız gerekir. D şehri için tek seçenek B'den gelip E'ye gitmek veya tam tersidir. Yani B - D ve D - E yolları mutlaka kullanılmalıdır.
D'nin derecesi 2'dir. O halde B-D ve D-E yolları mecburidir.
Peki A ve C şehirlerine bakalım. A'dan B'ye, C'ye ve E'ye yollar var. C'den ise sadece A ve B'ye yollar var.
Çö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
