Olimpiade Sains Provinsi (OSP) 2014 - Komputer, Nomor 16–18

Untuk soal 16 dan 17, perhatikan bahwa graf yang terbentuk berupa cactus (graf di mana 2 buah simple cycle paling banyak memiliki satu buah vertex yang sama). Pada 2 soal ini, persoalannya adalah ada berapa cara mereduce cactus menjadi tree (graf tanpa cycle dan semua vertex terhubung).

Perhatikan bahwa pada setiap simple cycle, kita hanya bisa "menghapus" satu buah jalan. Dengan kata lain, banyak cara membuat jalannya sama dengan hasil kali ukuran (banyak jalan) tiap simple cycle.

Untuk nomor 16, ada 2 simple cycle, yaitu A-B-C-D dan E-F-G, sehingga banyak cara = 4 × 3 = 12

Untuk nomor 17, ada 3 buah simple cycle, yaitu C-D-I-H-E, E-F-G, I-L-K-J, sehingga banyak cara = 5 × 3 × 4 = 60

Untuk nomor 18, yang ditanyakan adalah : "Pada sebuah graf yang complete (semua terhubung), ada berapa spanning tree yang terbentuk?" Berdasarkan Cayley's formula, banyak cara untuk graf dengan banyak vertex n adalah n^{(n - 2)}, sehingga banyak caranya = 4^{4 - 2} = 16

ya memang ada teori seperti di atas, tapi untuk soal ini dia memiliki syarat bahwa sebuah rute valid jika melewati N-1 jalan dengan begitu otomatis kita harus melewati semua kota tepat 1x sedangkan teori diatas berlaku jika kita boleh melewati tiap kota minimal 1x dan boleh lebih dari 1x. Jadi untuk soal ini tidak berlaku teori yg disebutkan oleh Muhammad Ayaz Dzulfikar, caranya kita harus menggambar sebuah peta yg terdiri dari jalan2 dan kota/titik (ingat jalan itu bukan rute, jadi jumlah jalan tidak harus N-1) dan tinggal cari kemungkinannya

16) setelah mengikuti instruksi di atas kita temukan bahwa ada 4 rute 17) setelah mengikuti instruksi di atas kita temukan bahwa ada 0 rute, kenapa? karena jika kalian lihat di peta dan mencoba membuat rute PASTI ada kota yg dilewati 2x 18) ikuti instruksi jwb = 24, cara cepatnya karena semua terhubung = jumlah jalan yg tersedia x jumlah kota, 6 x 4 = 24