My first Magazine pemrograman-kompetitif-dasar | Page 28

2 Matematika Diskret Dasar
Apabila kita hitung satu per satu, maka cara yang berbeda untuk menuju kota C dari kota A
adalah sebagai berikut:
•
•
•
•
•
•
Melalui jalur e 1
Melalui jalur e 1
Melalui jalur e 2
Melalui jalur e 2
Melalui jalur e 3
Melalui jalur e 3
kemudian jalur e 4 .
kemudian jalur e 5 .
kemudian jalur e 4 .
kemudian jalur e 5 .
kemudian jalur e 4 .
kemudian jalur e 5 .
Dengan kata lain, terdapat 6 cara berbeda untuk menuju kota C dari kota A. Namun, apabila
jumlah kota dan jalur yang ada sangatlah banyak, kita tidak mungkin menulis satu per satu cara
yang berbeda. Karena itulah kita dapat menggunakan aturan perkalian.
Misalkan suatu proses dapat dibagi menjadi N subproses independen yang mana terdapat a i
cara untuk menyelesaikan subproses ke-i. Menurut aturan perkalian, banyak cara yang berbeda
untuk menyelesaikan proses tersebut adalah a 1 × a 2 × a 3 × ... × a N .
Kita akan mencoba mencari banyaknya cara menuju kota C dari kota A menggunakan aturan
perkalian. Anggaplah bahwa:
• Perjalanan dari kota A menuju kota B merupakan subproses pertama, yang mana terdapat
3 cara untuk menyelesaikan subproses tersebut.
• Perjalanan dari kota B menuju kota C merupakan subproses kedua, yang mana terdapat 2
cara untuk menyelesaikan subproses tersebut.
Karena perjalanan dari kota A menuju kota B dan dari kota B menuju kota C merupakan 2
subproses yang berbeda, maka kita dapat menggunakan aturan perkalian. Banyak cara berbeda
dari kota A menuju kota C adalah 3 × 2 = 6.
Contoh Soal 2.3: Kota 2
Contoh soal ini merupakan lanjutan dari Kota 1.
Deskripsi soal, jumlah kota dan jalur serta susunan jalur yang ada sama persis dengan soal
tersebut.
Tambahkan 1 jalur lagi, yaitu e 6 yang menghubungkan kota A dan C. Berapa banyak cara
berbeda untuk menuju kota C dari kota A?
e 4
e 1
A
e 2
e 3
B
e 5
C
e 6
Dengan mencoba satu per satu setiap cara, maka terdapat 7 cara yang berbeda, yaitu 6 cara
sesuai dengan soal sebelumnya, ditambah dengan menggunakan jalur e 6 .
Apabila kita menggunakan aturan perkalian, maka didapatkan banyak cara yang berbeda
adalah 3 × 2 × 1 = 6 yang mana jawaban tersebut tidaklah tepat. Kita tidak dapat menggunakan
18