Matematika Diskrit adalah cabang matematika yang berfokus pada objek-objek diskrit, yaitu objek-objek yang terpisah dan tidak kontinu

 Matematika Diskrit adalah cabang matematika yang berfokus pada objek-objek diskrit, yaitu objek-objek yang terpisah dan tidak kontinu, seperti bilangan bulat, graf, dan struktur diskrit lainnya. Berikut adalah beberapa contoh soal matematika diskrit beserta penyelesaiannya.

---

Soal 1: Kombinasi

Tentukan berapa banyak cara yang dapat dipilih 3 orang dari 5 orang untuk membentuk sebuah tim.

Penyelesaian:

Soal ini meminta kita untuk menghitung jumlah kombinasi, yang dapat dihitung dengan rumus kombinasi $C(n, r)$, di mana $n$ adalah jumlah total elemen, dan $r$ adalah jumlah elemen yang dipilih. Rumus kombinasi adalah:

$$C(n, r) = \frac{n!}{r!(n - r)!}$$

Diketahui:

• $n = 5$ (jumlah orang)
• $r = 3$ (jumlah orang yang dipilih)

Substitusikan ke dalam rumus:

$$C(5, 3) = \frac{5!}{3!(5 - 3)!} = \frac{5!}{3!2!}$$

Hitung faktorialnya:

$$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$$ $$3! = 3 \times 2 \times 1 = 6$$ $$2! = 2 \times 1 = 2$$

Sekarang, substitusikan nilai faktorial ke dalam rumus:

$$C(5, 3) = \frac{120}{6 \times 2} = \frac{120}{12} = 10$$

Jadi, ada 10 cara untuk memilih 3 orang dari 5 orang.

---

Soal 2: Permutasi

Berapa banyak cara untuk menyusun huruf dari kata "MATEMATIKA"?

Penyelesaian:

Untuk menghitung jumlah permutasi, kita dapat menggunakan rumus permutasi dengan objek yang sama. Rumusnya adalah:

$$P = \frac{n!}{k_1! k_2! \cdots k_m!}$$

Di mana $n$ adalah jumlah total elemen, dan $k_1, k_2, \dots, k_m$ adalah jumlah masing-masing elemen yang berulang.

Kata "MATEMATIKA" terdiri dari 10 huruf, dengan huruf-huruf yang berulang sebagai berikut:

• M: 1 kali
• A: 2 kali
• T: 2 kali
• E: 1 kali
• I: 1 kali
• K: 1 kali

Jumlah total huruf adalah 10, jadi kita hitung permutasinya:

$$P = \frac{10!}{2!2!1!1!1!1!}$$

Hitung faktorialnya:

$$10! = 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 3,628,800$$ $$2! = 2 \times 1 = 2$$ $$1! = 1$$

Sekarang, substitusikan nilai faktorial ke dalam rumus:

$$P = \frac{3,628,800}{2 \times 2 \times 1 \times 1 \times 1 \times 1} = \frac{3,628,800}{4} = 907,200$$

Jadi, jumlah cara untuk menyusun huruf dari kata "MATEMATIKA" adalah 907,200.

---

Soal 3: Graf

Diberikan graf berikut, tentukan apakah graf tersebut terhubung (connected) atau tidak.

Penyelesaian:

Untuk menjawab soal ini, kita perlu memeriksa apakah ada jalur antara setiap pasang simpul dalam graf tersebut. Jika ada jalur antara semua pasangan simpul, maka graf tersebut terhubung (connected).

Jika graf memiliki lebih dari satu komponen terpisah, maka graf tersebut tidak terhubung.

Karena soal ini membutuhkan gambar graf, saya akan menjelaskan langkah-langkah yang perlu dilakukan:

1. Periksa apakah ada jalur antara setiap pasang simpul.
2. Jika semua simpul dapat dijangkau dari simpul lainnya, maka graf tersebut terhubung.
3. Jika ada simpul yang tidak dapat dijangkau dari simpul lainnya, maka graf tersebut tidak terhubung.

---

Soal 4: Relasi

Diberikan relasi $R$ pada himpunan $A = \{1, 2, 3, 4\}$ yang didefinisikan sebagai $R = \{(1, 2), (2, 3), (3, 4), (4, 1)\}$. Tentukan apakah relasi $R$ adalah refleksif, simetris, dan transitif.

Penyelesaian:

Untuk memeriksa sifat relasi, kita harus mengecek apakah relasi tersebut memenuhi definisi dari refleksif, simetris, dan transitif.

1. Refleksif: Relasi dikatakan refleksif jika untuk setiap elemen $a$ di himpunan $A$, pasangan $(a, a)$ ada dalam $R$.

   • Pada himpunan $A = \{1, 2, 3, 4\}$, kita periksa apakah setiap pasangan $(a, a)$ ada dalam $R$.
   • Pasangan yang diperlukan adalah $(1, 1), (2, 2), (3, 3), (4, 4)$, tetapi pasangan ini tidak ada dalam $R$.
   • Jadi, relasi $R$ bukan refleksif.

2. Simetris: Relasi dikatakan simetris jika setiap kali $(a, b) \in R$, maka $(b, a)$ juga harus ada dalam $R$.

   • Dalam relasi $R$, kita memiliki pasangan $(1, 2)$, tetapi pasangan $(2, 1)$ tidak ada dalam $R$.
   • Jadi, relasi $R$ bukan simetris.

3. Transitif: Relasi dikatakan transitif jika setiap kali $(a, b) \in R$ dan $(b, c) \in R$, maka $(a, c)$ juga harus ada dalam $R$.

   • Misalnya, $(1, 2) \in R$ dan $(2, 3) \in R$, maka menurut sifat transitif, $(1, 3)$ harus ada dalam $R$. Namun, $(1, 3)$ tidak ada dalam $R$.
   • Jadi, relasi $R$ bukan transitif.

Kesimpulannya, relasi $R$ bukan refleksif, bukan simetris, dan bukan transitif.

---

Soal 5: Pohon

Tentukan jumlah pohon biner dengan 3 simpul.

Penyelesaian:

Pohon biner adalah pohon di mana setiap simpul memiliki paling banyak dua anak. Untuk menghitung jumlah pohon biner dengan $n$ simpul, kita dapat menggunakan Bilangan Catalan. Jumlah pohon biner dengan $n$ simpul diberikan oleh rumus:

$$C_n = \frac{1}{n+1} \binom{2n}{n}$$

Untuk $n = 3$:

$$C_3 = \frac{1}{3+1} \binom{6}{3} = \frac{1}{4} \times 20 = 5$$

Jadi, jumlah pohon biner dengan 3 simpul adalah 5.