Hamilton Döngüsü Problemi

Selam Elif, bu güzel bir graf teorisi problemi. Salih'in hangi şehirden başlarsa başlasın tüm şehirleri birer kez gezip başladığı yere dönebilmesi, yani bir Hamilton çevrimi yapması isteniyor.

Önce görseldeki şehirleri ve aralarındaki yolları bir çizimle daha net görelim. A, B, C, D ve E şehirlerimiz var.

Kuralımız şu: Beş şehrin her birine birer kez uğrayıp geri döneceğiz. Yani topam beş yoldan oluşan kapalı bir döngü bulmalıyız.

Şimdi grafımızı tekrar inceleyelim ve bu çevrimi kurmaya çalışalım. Görsele baktığımızda en dıştaki yolların bir çerçeve oluşturduğunu görüyoruz.

A'dan başlayalım. B'ye gidelim.

B'den sonra devam ederek C şehrine uğrayalım.

C'den sonra D şehrine gidelim.

D'den sonra henüz uğramadığımız E şehrine geçelim.

Ve son olarak E'den başladığımız A şehrine dönersek tüm şehirleri gezmiş oluruz.

Bulduğumuz rotayı yazalım: A tire B tire C tire D tire E tire A. Dikkat edersen bu döngüde iki yol hiç kullanılmadı.