UAS – MATEMATIKA DISKRIT 1 KAMPUS ITBI MILENIAL

Nama       : IDE KRISTIANI ZEGA

Jurusan   : TEKNIK INFORMATIKA S1

Kelas       : PAGI

Soal dan jawaban :

1.      Tentukan apakah graf dibawah ini memiliki sirkuit Hamilton. Jika tidak, berikan alasannya. Jika memiliki, carilah sirkuit Hamilton tersebut

Penyelesaian :

 

Sirkuit Hamilton adalah sirkuit yang melalui tiap simpul di dalam graf tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali. Graf diatas termasuk graf Hamilton, yaitu graf yang memiliki sirkuit Hamilton {a,b,c,d,e,a}

2.      Tentukan apakah graf dibawah ini isomorfis. Jika ya atau tidak berikan alasannya

Penyelesaian :

 

 

Dua buah graf yang isomorfis adalah graf yang sama, kecuali penamaan simpul dan sisinya saja yang berbeda. Ini benar karna sebuah graf dapat digambarkan dalam banyak cara. Jika G dan G^' isomorfis, maka terdapat beberapa hal yang pasti terpenuhi :

-        Jumlah titik G = jumlah titik G^'

-        Jumlah garis G = jumlah garis G^'

-        Jumlah garis sama dengan derajat tertentu dalam G dan G^' sama

Perhatikan kedua gambar diatas, dari syarat yang ada hanya 2 dari 3 syarat yang terpenuhi. Jumlah titik G adalah 5 = jumlah titik G^' adalah 5, kemudian jumlah garis G adalah 7 = jumlah garis G^' adalah 7. Tetapi pada derajat G ada yang tidak berkesinambungan dengan G^' . Derajat d pada G adalah 3 tetapi pada G^' derajat d' hanya memiliki 2. Dari penjelasan ini, maka disimpulkan bahwa kedua graf diatas tidak isomorfis.

3.      Misalkan A = {2,3,4} dan B = {6,8,10}. Didefinisikan relasi biner R dari A ke B sebagai berikut : untuk semua (x,y) ϵ A × B (x,y) ϵ R jika dan hanya jika x habis membagi y.

a.       Tulis R sebagai pasangan berurut

b.      Buatlah R dalam bentuk graf

Penyelesaian :

a.       R = {(2,6), (2,8), (2,10), (3,6), (4,8)}

b.      

4.      Misalkan W = {1, 2, 3, 4}. Perhatikan relasi-relasi dalam W berikut ini :

R­­­­_{1 ­}= {(1,1), (1,2)}, R₂ = {(1,2), (2,4)}, R₃ = {(1,1), (2,2), (3,3)}. Selidiki apakah masing-masing relasi diatas bersifat Refleksif, Simetris, Transitif.

Penyelesaian :

-        R disebut relasi refleksif jika tiap-tiap anggota W berelasi dengan dirinya sendiri. Diketahui W = {1, 2, 3, 4} dan R₁ = {(1,1), (1,2)} tidak bersifat refleksif karena {(2,2), (3,3), (4,4)} tidak termasuk dalam elemen R. Hal ini juga berlaku pada R₂ dan R₃

-        Relasi R pada himpunan W disebut simetris jika (w, x) ϵ R, maka (x, w) ϵ R untuk w, x ϵ W. diketahui W = {1, 2, 3, 4} dan R₁ = {(1,1), (1,2)} tidak setangkup karena ada (w, x) ϵ R, tetapi (x, w) ∉ R, (1,2) ϵ R → (2,1) ∉ R.Relasi R₂ = {(1,2), (2,4)} tidak setangkup karena ada (w, x) ϵ R, tetapi (x, w) ∉ R, (2,4) ϵ R → (4,2) ∉ R. Sedangkan R₃ = {(1,1), (2,2), (3,3)} merupakan relasi yang simetris sekaligus relasi yang anti simetris. Suatu relasi R pada himpunan W dikatakan anti simetris jika untuk setiap w, x  ϵ W (w,x) ϵ R dan (x, w) ϵ R berlaku hanya jika w = x . Perhatikanlah bahwa istilah simetris dan anti simetris tidaklah berlawanan, karena suatu relasi dapat memiliki kedua sifat itu sekaligus. Namun, relasi tidak dapat memiliki kedua sifat tersebut sekaligus jika ia mengandung beberapa pasangan terurut berbentuk (w,x) yang mana w ≠ x

-        Sebuah relasi disebut transitif jika memiliki sifat, jika a berhubungan dengan b, dan b berhubungan dengan c, maka a berhubungan dengan c secara langsung.

W = {1, 2, 3, 4}

R­­­­_{1 ­}= {(1,1), (1,2)} jelas menghantar

R₂ = {(1,2), (2,4)} tidak menghantar karena (1,2) dan (2,4) ϵ R, tetap (1,4) ∉ R begitu juga dengan R₃ = {(1,1), (2,2), (3,3)}

5.      Hitunglah P(8,5) dan C(12,6)

Penyelesaian :

Permutasi P(n,r) = n!/(n-r)!

P(8,5) = 8!/ (8-5)!

= 8!/3!

= 8·7·6·5·4·3!/3!

=6. 720

Kombinasi C(n,r) = n!/r!(n-r)!

C(12,6) = 12!/6!(12-6)!

= 12·11·10·9·8·7·6!/6!·6!

= 12·11·10·9·8·7/6·5·4·3·2·1

=665.280/720

= 924

6.      Berapa banyak plat nomor kendaran yang bisa dibuat dari 2 huruf dan diikuti dengan 4 angka?

Penyelesaian :

P(26,2) × P(10,4) = 3. 276. 000

7.      Suatu komite yang beranggotakan paling sedikit 5 orang akan dipilih dari 9 calon yang ada. Berapa macam komite yang dapat dibuat?

Penyelesaian :

Komite adalah kelompok yang tidak berurut, artinya setiap anggota didalam kedudukannya sama. Misal 5 orang yang dipilih adalah A, B, C, D, dan E maka urutan penempatan masing-masingnya didalam panitia tidak penting. Maka banyaknya cara memilih anggota panitia yang terdiri dari 5 orang anggota adalah C(9,5) = 126

8.      Suatu kode akses komputer terdiri dari 3 huruf dengan mengizinkan perulangan. Berapa banyak di antara kode-kode tersebut memuat perulangan huruf?

Penyelesaian :

Misalnya ketiga huruf tersebut adalah = a, b, c

Karna terdiri dari tiga, maka banyaknya cara = 3×3×3 = 27 cara

9.      Buktikan deret dibawah ini dengan menggunakan induksi matematika di mana

 n ≥ 1 :

1 + 2 · 2 + 3 · 2² + … + n · 2^(n-1) = 1 + (n-1)2ⁿ

Penyelesaian :

Basis induksi : p(1) benar, karena untuk n = 1 kita peroleh

1 = 1 + (1-1)2¹

     = 1 + (0)2

 1 = 1 (benar)

Langkah induksi : kita juga harus memperlihatkan bahwa p(n-1) juga benar

1 + 2 · 2 + 3 · 2² + … + n · 2^(n-1) = 1 + (n-1)2ⁿ

Misal n = 1, maka

1 + 2 · 2 + 3 · 2² + … + 1 · 2^(1-1) = 1 + (1-1)2¹

                                                       = 1 + (0)2¹

                                                       = 1 + 0

                                                       = 1 maka terbukti benar

10.   Tuliskan pengaruh Algoritma terhadap komputasi atau program yang kita buat.

Algoritma adalah urutan langkah-langkah logis penyelesaian sebuah masalah yang disusun secara logis dan sistematis. Pada dasarnya fungsi utama dari algoritma adalah untuk memecahkan suatu masalah. Lebih jelasnya, adapun ketika kita sedang membuat sebuah program, algoritma punya pengaruh besar untuk membantu dalam membuat sebuah program untuk masalah tertentu. Algoritma juga memudahkan dalam membuat program yang lebih rapid an terstruktur sehingga lebih mudah dipahami dan dikembangkan. Ketika misalnya terjadi kesalahan, algoritma dapat membantu menemukannya karena alur kerja yang jelas