Geçit Törenleri – Königsberg Köprüleri 2 – 7
Bu, Königsberg'in içinden geçen nehri, nehrin ortasındaki adayı ve nehri geçen yedi köprüyü gösteren bir harita. Königsberg halkı, köprülerinin her birinden tam olarak bir kez geçecek bir geçit töreni düzenlemek istiyordu. Ancak yedi köprünün tamamını ziyaret edecek bir geçit töreni güzergahı bulamadılar.
CHALLENGE
Mümkünse, köprülerinin her birinden tam olarak bir kez geçen bir geçit töreni güzergahı bulun. Eğer bulamıyorsanız, bunun neden imkansız olduğunu açıklayın.
KEŞİF
Nehrin üzerine bir köprü daha eklersek, bu sorunu kolaylaştırır mı yoksa zorlaştırır mı?
notlar
CHALLENGE
Öncelikle bu problemi, geçmemiz gereken kenarları olan bir probleme dönüştürelim. Daha önceki "Geçit Törenleri" Haftanın Bulmacası'nda, tek sayıda kenarın geldiği düğüm noktalarının sayısının ikiden fazla olmamasının çok önemli olduğunu görmüştük.
Dört düğümün de kendilerine gelen kenar sayısının tek olması nedeniyle, bir geçit töreni güzergahı bulmak imkansız olacaktır!
KEŞİF
Nehrin herhangi bir yerine bir köprü daha eklerseniz, çözümü çok kolaylaştıracaksınız.
Bu sorun. Çünkü o zaman dört düğümden ikisine çift sayıda kenar gelecek.
Bu durumda, kendilerine tek sayıda kenar gelen yalnızca iki düğüm kalacaktır.