15-01 Latihan Soal (Erlangga A.O.) [PDF]

Citation preview

Nama : Erlangga Alvito Oktavian (20416257201059) Kelas : SI20B Nomor 1 Gambarkan graf dengan



7 titik dan 8 sisi/garis serta:



a. sederhana. b. memuat loop dan sisi rangkap.  c. tidak sederhana dan memuat sisi rangkap.



Nomor 2



G adalah graf dengan barisan derajat: (4,3,2,1). Tentukan banyaknya sisi di G dan gambarkan graf G. P=4, R= 2, O=3, S=1 Misalkan



Nomor 3 Dalam sebuah pesta, enam orang saling berjabat tangan. Tiap orang hanya berjabat tangan satu kali dengan orang lainnya. Hitung jumlah jabat tangan yang terjadi dan modelkan dalam graf.



Nomor 4 Ada n buah komputer yang akan dihubungkan dengan sejumlah kabel, baik secara langsung atau terhubung melalui komputer lainnya. Berapa jumlah minimum potongan kabel yang dibutuhkan?



Nomor 5 Perhatikan graph dibawah ini, tentukan: a. himpunan titiknya; b. himpunan sisinya. a b



Soal 4.



Berdasarkan graph dibawah ini, tentukan adjacency matrix graph dan insidensi matrik gprah:



Jawaban 1.



2. 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 1 4+3+2+1=10. Dengan demikian, banyak sisi di G adalah × 10 = 5. Gambar graf G dapat dilihat 2 sebagai berikut Tampak pada gambar di atas bahwa derajat titik A,B,C, dan D berturutturut adalah 1,4,3, dan 2 .Tampak pula ada 5 sisi pada graf tersebut.



3. Perhatikan graf sederhana pada lampiran







Titik menunjukkan orang (ada 10 titik berarti ada 10 orang)







Sisi menunjukan jabat tangan antar dua orang (banyak sisi pada graf menunjukkan jumlah jabat tangan yang terjadi)



Banyak jabat tangan yang terjadi dari 10 orang adalah   = 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45



4. Misalkan komputer itu direpresentasikan sebagai titik pada suatu graf. Himpunan titiknya adalah(a,b,c,d,...) , yaitu sebanyak n titik. Agar semua titik ini terhubung baik secara langsung maupun melalui komputer lainnya dengan sisi minimum, titik-titik tersebut harus diposisikan sedemikian sehingga tidak ada sisi yang bercabang seperti berikut. (Catatan: sisi yang terkait dengan titik d selain sisi cd menunjukkan representasi sisi yang berlaku umum sampai titik-titik selanjutnya, bukan sisi yang hanya memiliki satu titik ujung) Jadi, dalam hal ini, titik a adjacent dengan titik b, titik b adjacent dengan titik c, dan seterusnya, sehingga banyak sisi graf sama dengan 1 kurangnya dari banyak titik graf, yaitu n-1 . Jadi, jumlah minimum potongan kabel yang dibutuhkan adalah n-1



5. a. Himpunan titiknya : {1,2,3,4,5,6} dan {1,2,3,4,5,6,7,8,9} b. Himpunan sisinya : {12,22,23,24,25,26,45,46} dan { 12, 16, 17, 18, 19, 12, 23, 24, 25, 26, 23, 34, 35, 36, 24, 34, 45, 25, 35, 45, 16, 26, 36, 17, 78, 79, 18, 78, 89, 19, 79, 89} 6.



Matrik adjacency v1 v2 v3 v4 v5



v1 0 1 1 1 1



v2 1 0 1 0 0



v3 1 1 0 1 1



v4 1 0 1 0 1



v5 1 0 1 1 0



Matrik incidence v1 v2 v3 v4 v5



e1 1 1 0 0 0



e2 1 0 1 0 0



e3 0 1 1 0 0



e4 1 0 0 1 0



e5 1 0 0 0 1



e6 0 0 1 1 0



e7 0 0 1 0 1



e8 0 0 0 1 1