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: