Olimpiade Sains Provinsi (OSP) 2014 - Komputer , Nomor 16 - 18
Deskripsi untuk soal nomor 16 - 18
Walikota Budi ingin membuat sebuah rute transonjek di sebuah provinsi Bagus. Sebuah rute transojek harus memenuhi beberapa kriteria di bawah ini :
-
Sebuah rute harus menghubungkan semua kota-kota yang berada pada provinsi Bagus
-
Dari setiap kota hanya boleh terdapat tepat 1 jalur menuju setiap kota lainnya
-
Jumlah jalur yang dipakai harus berjumlah N-1 (N adalah jumlah kota)
-
Tidak diperbolehkan membuat jalur baru (hanya diperbolehkan menggunakan jalur yang telah disediakan)
- Apabila sebuah kota x terhubung dengan kota y, maka kota y juga terhubung dengan kota x
Apabila dalam provinsi Bagus terdapat 7 kota A,B,C,D,E,F,G berapa banyak konfigurasi rute yang memenuhi jika jalur yang ada sebagai berikut?
-
Kota A terhubung dengan kota B dan C
-
Kota D terhubung dengan kota B, C , dan E
-
Kota E terhubung dengan kota F dan G
- Kota F terhubung dengan G
Apabila dalam provinsi Bagus terdapat 12 kota A,B,C,D,E,F,G,H,I,J,K, dan L berapa banyak konfigurasi rute yang memenuhi jika jalur yang ada sebagai berikut?
-
Kota B terhubung dengan kota A dan C
-
Kota D terhubung dengan kota C dan I
-
Kota E terhubung dengan kota C,F,G, dan H
-
Kota F terhubung dengan kota G
-
Kota I terhubung dengan kota H,J,dan L
- Kota K terhubung dengan kota J dan L
Apabila pada provinsi Bagus semua kota yang ada saling terhubung dengan kota lainnya berapa banyak konfigurasi rute transojek yang dapat dibentuk apabila jumlah kota yang ada dalam provinsi Bagus berjumlah 4?
