Gambar di bawah menunjukkan jaringan jalan yang menghubungkan sembilan desa. Angka-angka manyatakan jarak (dalam mil) jalan tersebut. Seorang pagawai Kota Praja yang bertempat tinggal di desa A bertugas untuk menginspeksi semua jalan dengan mobilnya. Berapakah jarak rute terpendek yang dapat ditempuhnya bila ia harus kembali ke A.
Jawaban
A, C, E, G, H dan I merupakan noktah ganjil dan karena itu salah satu jalan akan dilalui dua kali. Untuk meminimalkan jarak yang ditempuh, jalan yang dilewati dua kali dapat ditetapkan sebagai AG, HC, dan IE. Salah satu rute yang mungkin adalah sebagai berikut
A – B – C – D – E – F – A – G – F – I – E – I – D – H – C – H – B – G – H – I – G – A.
Dengan total jarak ( 6 x 13 ) + ( 9 x 12 ) + ( 6 x 5 ) = 216 mil
Selamat mencoba!