Terdapat beberapa buah kota yang terhubung dengan penerbangan satu arah (arah penerbangan ditunjukkan dengan tanda panah) sebagai berikut:
15. Jika diketahui Pak Dengklek melakukan perjalanan dari Kota-0 ke Kota-9 melewati tepat 4 penerbangan, berapa banyak kemungkinan rute berbeda yang bisa diambil?
Pembahasan Soal OSP Informatika Komputer 2019 no 15.
Dari 0 menuju 9 dengan 4 penerbangan artinya sebelum sampai 9 harus singgah 3 kali (TitikA menuju titik B dihitung 1) atau dapat ditulis 0XXX9.
9 dapat dituju lewat 4 dan 8 serta 5
Dari 0 bercabang 3 yaitu menuju 1 2 dan 6
Dari 2 pernyataan diatas didapat pertama 1 2 atau 6 dan singgahan ketiga 4 8 atau 5. Selanjutnya cari singgahan ke 3 melalui gambar yang diberikan. Didapat kombinasi
- 01349
- 01389
- 01259
- 02349
- 02389
- 02549
- 02589
- 02749
- 02789
- 06749
- 06789
- 06259
16. Untuk menghindari kemungkinan cuaca buruk, beberapa rute penerbangan akan dibatalkan. Berapa rute penerbangan minimal yang harus ditutup sedemikian sehingga banyaknya rute yang bisa diambil dari Kota-0 ke Kota-9 masih tersisa tepat 2 kemungkinan rute?
Pembahasan Soal OSP Informatika Komputer 2019 no 16.
9 dapat dituju dari 4 5 dan 8. Titik 5 hanya dapat diakses melalui titik 2 dan 0 ke 2 memerlukan 3 jalur berbeda. Sehingga dengan memangkas 2 rute selain 5 ke 9 yaitu 4 ke 9 dan 8 ke 9 kita sudah mendapatkan 3 rute utama yaitu
0-1-2-5-9
0-2-5-9
0-6-2-5-9
Agar hanya tersisa 2 rute pangkas salah satu dari 3 rute penerbangan dari titik 0 (misanya 0 ke 2) sehingga ada 3 rute yang dipangkas agar ada 2 rute dari 0 ke 9.
0 komentar:
Post a Comment