Tugas Mandiri 4 Matematika Diskrit

Nama : Sinta
Jurusan: Sistem Informasi
Kelas : Pagi

A. Buatlah 3 contoh soal dan penyelesaian teori Graf yang sudah anda pelajari di pertemuan 8.

Jawaban:

1. Misalkan $G$ adalah graf dengan barisan derajat: $(4,3,2,1)$. Tentukan banyaknya sisi di $G$ dan gambarkan graf $G$.

Pembahasan

Menurut Lema Jabat Tangan (Handshaking Lemma), jumlah derajat titik pada suatu graf sama dengan $2$ kali banyak sisi. Diketahui bahwa jumlah derajat titik-titik graf itu adalah $4+3+2+1=10$. Dengan demikian, banyak sisi di $G$ adalah $\frac{1}{2}\times 10=5$. Gambar graf $G$ dapat dilihat sebagai berikut.

Tampak pada gambar di atas bahwa derajat titik $A,B,C$, dan $D$ berturut-turut adalah $1,4,3$, dan $2$. Tampak pula ada $5$ sisi pada graf tersebut.

2. Misalkan $G$ adalah graf dengan barisan derajat: $(4,3,2,1)$. Tentukan banyaknya sisi di $G$ dan gambarkan graf $G$.

Pembahasan

Menurut Lema Jabat Tangan (Handshaking Lemma), jumlah derajat titik pada suatu graf sama dengan $2$ kali banyak sisi. Diketahui bahwa jumlah derajat titik-titik graf itu adalah $4+3+2+1=10$. Dengan demikian, banyak sisi di $G$ adalah $\frac{1}{2}\times 10=5$. Gambar graf $G$ dapat dilihat sebagai berikut.

Tampak pada gambar di atas bahwa derajat titik $A,B,C$, dan $D$ berturut-turut adalah $1,4,3$, dan $2$. Tampak pula ada $5$ sisi pada graf tersebut.

3.  Perhatikankembali graf yang diberikan pada soal nomor 2. Tentukan graf mana yang:
a. sederhana;
b. memuat loop;
c. memuat sisi rangkap.

Pembahasan

Graf yang memuat sisi rangkap adalah graf $G_2$, yaitu pada sisi penghubung titik $u$ dan $v$.
Graf yang memuat loop adalah $G_3$, yaitu pada titik $2$.
Graf sederhana adalah $G_1$ karena tidak memuat sisi rangkap maupun loop.

[

B. Buat representasi relasi berikut dalam diagram

Contoh:

R = {(P, Q)} = {(2,2), (2,4), (4,4), (2,8)}

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: