TUGAS MANDIRI 4 – MATEMATIKA DISKRIT 1 KAMPUS ITBI MILENIAL

Nama       : IDE KRISTIANI ZEGA

Jurusan   : TEKNIK INFORMATIKA S1

Kelas       : PAGI

1.      3 contoh soal dan penyelesaian teori Graf:

1)     Berilah contoh graf berikut dengan paling banyak 6 titik

a.       Graf Hamilton yang bukan euler

Penyelesaian:

Graf Hamilton adalah graf yang memuat sikel Hamilton. Sikel Hamilton sendiri adalah jalan tertutup yang semua sisi dan titik interalnya berbeda serta melalui seluruh titik pada graf tersebut, sedangkan graf euler adalah graf yang semua sisinya berbeda dan setiap sisi dilalui tepat satu kali.

 

Graf G diatas mengandung sikel Hamilton dengan barisan titik a b d c a. Jelas bahwa jalan tersebut tertutup (kembali pada titik semula), melalui semua titik pada graf, dan titik internalnya berbeda (hanya di lalui 1 kali). Oleh karena itu, graf diatas disebut graf Hamilton dan bukan graf Euler karena ada sisi yang tidak dilaluinya, yaitu sisi bc

2)     Tuliskan matriks keterhubungan langsung dari graf berikut

 

 

 

Penyelesaian:

Matriks keterhubungan dari graf G diatas adalah sebagai berikut:

 

3)     Benar atau salahkah pernyataan berikut:

a.       Jika graf G dan H isomorfik, maka keduanya mempunyai banyak titik yang sama dan banyak titik yang sama pula

Penyelesaian:

Benar. Jika tidak, maka fungsi yang terbentuk bukan bijektif (korespondensi satu-satu) padahal itu adalah syarat keisomorfikan graf

2.      Buatlah representasi relasi berikut dalam diagram:

1)     R={(A, B)} = {(1, 2), (1, 3), (-1, 5), (0, 2)

2)     R={(M, N)} = {(10, 2), (11, 3), (12, 2), (13, 3), (13, 2), (14, 0)}

3)     R={(X, Y)} = {(1, 1,), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}

Penyelesaian:

UTS 1 – MATEMATIKA DISKRIT 1 KAMPUS ITBI MILENIAL

Nama       : IDE KRISTIANI ZEGA

Jurusan   : TEKNIK INFORMATIKA S1

Kelas       : PAGI

4.      Tentukan PBB dari 321 dan 843 menggunakan algoritma Euclid

Penyelesaian:

m = 843, n = 321

843 = 2(321) + 201                                      Iterasi 1

321 = 1(201) + 120                                      Iterasi 2

201 = 1(120) + 81                                        Iterasi 3

120 = 1(81) + 39                                           Iterasi 4

81 = 2(39) + 3                                               Iterasi 5

39 = 3(13) + 0                                               Iterasi 6

 

Karena pada Iterasi 6, sisa hasil baginya 0, maka PBB dari 321 dan 843 adalah 3, yang merupakan sisa hasil bagi pada Iterasi 5

 

5.      Tentukan kombinasi lanjar dari 247 dan 299 gunakan algoritma Euclid untuk mencari PBB terlebih dahulu

Penyelesaian:

299 = 1(247) + 52                                        (1)

247 = 4(52) + 39                                           (2)

52 = 1(39) + 13                                             (3)

39 = 3(13) + 0                                               (4)

Maka PBB (247, 299) = 13

 

Susun pembagian nomor (3) dan (2) menjadi:

13 = 52 – 1 ·39                                              (5)

39 = 247 – 4 · 52                                           (6)

Sulihkan (6) kedalam (5) menjadi:

13 = 52 – 1(247-4·52) = 1·52 - 1·247 + 4·52 = 5·52 - 1·247                  (7)

Susun pembagian nomor (1) menjadi:

52 = 299 - 1·247                                           (8)

Sulihkan (8) kedalam (7) menjadi:

13 = 5·52 - 1·247 = 5(299-1·247) - 1·247 = 5·299 - 5·247

Jadi, PBB (247, 299) = 13 = 5·299 - 5·247

 

7.      S = {1, 2, 3, 4, . . . , 10}

A = {1, 4, 7, 10}

B = {1, 2, 3, 4, 5}

C = {2, 4, 6, 8}

Tentukan:

a.       B ∩ (C – A)

b.      A’ ∩ ( B ∪ C)

c.       A Δ B

Penyelesaian:

a.       B ∩ (C – A)

(C – A) = {2, 4, 6, 8} – {1, 4, 7, 10} = C – A = {2, 6, 8}

B = {1, 2, 3, 4, 5}

B ∩ (C – A) = {2}

b.      A’ ∩ ( B ∪ C)

( B ∪ C) = B = {1, 2, 3, 4, 5} dan C = {2, 4, 6, 8} B ∪ C = {1, 2, 3, 4, 5, 6, 8}

       S = {1, 2, 3, 4, . . . , 10} dan A = {1, 4, 7, 10} A’ = {2, 3, 5, 6, 8, 9}

A’ ∩ (B ∪ C) = {2, 3, 5, 6, 8}

c.       A Δ B

A = {1, 4, 7, 10} dan B = {1, 2, 3, 4, 5}, A Δ B = (A · B) – (4 · A)

A Δ B = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5),

(7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (10, 1) (10, 2), (10, 3), (10, 4), (10, 5)} – {(4, 1), (4, 4), (4, 7), (4, 10)}

A Δ B = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (4, 2), (4, 3), (4, 5), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (10, 1), (10, 2), (10, 3), (10, 4), (10, 5)}

 

8.      Misalkan semesta S adalah himpunan bilangan riil R dan

A = {𝑥 ϵ R | -1 < 𝑥 ≤ 0}

B = {𝑥 ϵ R | 0  ≤  𝑥 < 0}

Tentukan:

a.       A ∩ B

b.      A ∪ B

c.       Aᶜ

Penyelesaian:

S = {0}

A = {0}

B = {-1, 0}

a.       A ∩ B = {0}

b.      A ∪ B = {-1, 0}

c.       Aᶜ = {0}

 

10.  Tulislah kovers, invers dan kontraposisi dari kalimat dibawah ini:

a.       Jika r bilangan rasional maka angka-angka desimalnya berulang

b.      Jika n adalah bilangan prima maka n adalah bilangan ganjil atau n=2

c.       Jika P adalah bujur sangkar, maka P adalah 4 persegi panjang

Penyelesaian:

a.       Jika r bilangan rasional maka angka-angka desimalnya berulang

-        Konvers = Jika angka-angkanya berulang maka r bilangan rasional (q¦p)

-        Invers = Jika r bukan bilangan rasional maka angka-angka desimalnya        tidak berulang (~p¦~q)

-        Kontraposisi = Jika angka-angka desimalnya tidak berulang maka r bukan bilangan rasional

b.      Jika n adalah bilangan prima maka n adalah bilangan ganjil atau n=2

-        Konvers = Jika n adalah bilangan ganjil atau n=2 maka n adalah bilangan prima

-        Invers = Jika n bukan bilangan prima maka n bukan bilangan ganjil atau n=2

-        Kontraposisi = Jika n bukan bilangan ganjil atau n=2 maka n bukan bilangan prima

c.       Jika P adalah bujur sangkar, maka P adalah 4 persegi panjang

-        Konvers = Jika P adalah 4 persegi panjang, maka P adalah bujur sangkar

-        Invers = Jika P bukan bujur sangkar, maka P bukan 4 persegi panjang

-        Kontraposisi = Jika P bukan 4 persegi panjang, maka P bukan bujur sangkar

TUGAS MANDIRI 3 – MATEMATIKA DISKRIT 1 KAMPUS ITBI MILENIAL

Nama       : IDE KRISTIANI ZEGA

Jurusan   : TEKNIK INFORMATIKA S1

Kelas       : PAGI

3 CONTOH SOAL DAN PENYELESAIAN TABEL KEBENARAN

1.       [p ˅ ~q]¦ p

 

Penyelesaian:

 

p	q	~q	p ˅ ~q	[p ˅ ~q]¦ p
B	B	S	B	B
B	S	B	B	B
S	B	S	S	B
S	s	B	B	S

 

2.       [~p ˅ q] ˄ [q¦ ~p]

 

Penyelesaian:

 

p	q	~q	[~p ˅ q]	[q¦ ~p]	[~p ˅ q] ˄ [q¦ ~p]
B	B	S	B	S	S
B	S	S	S	B	S
S	B	B	B	B	B
S	S	B	B	B	B

 

3.       [~q ˄ p]¦ ~q

 

Penyelesaian:

 

p	q	~q	~q ˄ p	[~q ˄ p]¦ ~q
B	B	S	S	B
B	S	B	B	B
S	B	S	S	B
S	S	B	S	B

 

 

                Konsep dari Matematika Graf dan Contoh Soal

·         Pengertian

Graf digunakan untuk mempresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut, sehingga secara sederhana graf didefenisikan sebagai kumpulan titik yang dihubungkan oleh garis-garis/sisi. Sedangkan definisi matematis untuk graf adalah pasangan terurut himpunan (V,E), dimana V merupakan himpunan beranggotakan titik-titik (vertex) dan E merupakan himpunan beranggotakan sisi-sisi (edges).

·         Definisi Graf

Graf G = (V,E) yang dalam hal ini:

         V = himpunan tidak kosong dari simpul-simpul (vertices)

             = {v₁, v₂, …. , vₙ}

        E = himpunan sisi (edges) yang menghubungkan sepasang simpul

            = {e₁, e₂, … , eₙ}

 

·         Jenis-jenis Graf

Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:

1)     Graf Sederhana (simple graph)

Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana

2)     Graf tak-sederhana (unsimple graph)

Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph)

                Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:

1)     Graf tak-berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah

2)     Graf Berarah (directed graph atau digraph)

Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah

 

                Contoh soal

1.       Gambarkan graf dengan 5 titik dan 8 sisi serta:

a.       Sederhana

b.       Memuat loop dan sisi rangkap

c.       Tidak sederhana dan memuat sisi rangkap

 

Penyelesaian:

 

a.       Contoh graf sesuai dengan syarat yang diberikan bisa dilihat digambar berikut:

Graf diatas memiliki 5 titik, yaitu A, B, C, D, dan E. graf itu memiliki 8 sisi (dapat dihitung dari jumlah garis yang ada), yaitu sisi, AB, AC, AE, BC, BE, CD, dan DE. Graf itu sederhana karena tidak memiliki sisi rangkap maupun loop.

 

b.       Contoh graf sesuai dengan syarat yang diberikan bisa dilihat digambar berikut:

Perhatikan bahwa sisi penghubung AB ada sebanyak 3 sisi sehinggap di sebut sisi rangkap (multiple edges) dan CC merupakan gelang (loop)

 

c.       Contoh graf sesuai dengan syarat yang diberikan bisa dilihat digambar berikut:

Perhatikan bahwa AB terhubung oleh sisi rangkap, begitu juga dengan BC. Oleh karena graf ini mengandung sisi rangkap, maka graf ini dikatakan tidak sederhana.