Olimpiade Sains Provinsi (OSP) 2014 - Komputer, Nomor 12
Di sebuah kota yang terdiri dari 13 persimpangan (yang diberi angka), terdapat jalan-jalan yang menghubungkan beberapa persimpangan. Fathin ingin berjalan-jalan dari tempat tinggalnya di persimpangan berlabel X ke suatu persimpangan berlabel Y. Y bisa saja sama dengan X. Tanpa dia sadari, rute yang dia tempuh dalam perjalanannya melewati semua jalan (bukan persimpangan) tepat satu kali. Berapakah label X terkecil yang mungkin ?
1 jawaban
Anthony Anthony11 tahun lalu
8
Untuk soal ini kita akan mencari Eulerian Path atau Eulerian Cycle.
Dari degree (derajat, banyaknya jalan yang terhubung dengan suatu persimpangan) setiap persimpangan, kita dapat melihat bahwa terdapat tepat 2 persimpangan yang memiliki degree ganjil, maka dijamin bahwa terdapat Eulerian Path, yaitu persimpangan 6 dan 8 sebagai kedua ujungnya.
Maka label X yaitu 6
Contoh rute yang dilalui: 6 4 3 9 10 6 7 5 4 1 2 8 13 12 10 11 7 8
Masuk untuk menulis jawaban