Soal Soal Latihan It105 Teori Graph [PDF]

Citation preview

Soal-Soal Latihan – Teori Graph MataKuliah : IT105 – Matematika Diskrit/SI107 – Logika Matematika Dosen : M. A. Ineke Pakereng, M. Kom. 1.



Hitunglah jumlah titik, jumlah garis dan derajat masing-masing titik graf berikut ini. Jika ada, tentukan titik terasing dan titik pendan. a



b



c



f



e



d



a



b



c



e



(a)



d (b)



b



a



c



g



h



d



e



f (c)



2.



Dalam graf berikut ini, tentukan : a. Himpunan titik-titik, himpunan garis-garis, titik-titik ujung masing-masing garis, dan garis paralel. b. Loop dan titik terasing. v1 e1 v2



3.



v4



e5



e3



e2 e4



v5



e7



v6 e6



v3



Tentukan apakah graf-graf berikut ini adalah graf bipartite ATAU B LENGKAP a b c b c b e



a d



c



e



(a) a



b f



e



d



a



(b)



d (c)



b a c



c (d)



d



f



d e



(e)



4.



Dalam graf di bawah ini, apakah H merupakan subgraf G ? a.



v1 e4



e7



e1 e5



v4



v2



e6



e3



e2



e4



v3



v4



e7



e1



v1



e6



e5



v2 e2 v3



e3 H



G b.



e1



v1 e3



v2



e3



e2



v1



v3



v4 5.



v4



H G Tanpa menggambarkan graf-nya, tentukan apakah graf yang memiliki matriks hubung berikut ini merupakan graf yang terhubung, memiliki loop, memiliki titik terasing. Tentukan juga derajat tiap titiknya.  1   0



a. 



0   0 



0 1 2  0 1 0 2 1 1  1 1 0 



 0   2



1 0



0 1



1  0 



2 0



1 1



b.  



0  0



 1  c.  0  1 



0  0 



0 1 2



1  2 0 



 0  d.  2  0 



2 1 0



0  0



1 



6.



Gambarlah graf yang memiliki matriks hubung dalam soal nomor 5!.



7.



Apakah kedua graf yang memiliki matriks hubung berikut ini isomorfis ?  0  a.  0  1 



1



0 



 0   1



1 0



0 0



0 0



1  1



1  1



 1 



8.



1



1



 1 



dan



b.  0 0 0 1 



 0   1



dan







0 



1 0



1  0



0



0 



 0   1



1 0



1 0



0 1



0 1



 1   1 



1  1 1  0 



Perhatikan graf berikut ini : e3 e1



v1 a. b. c. 9.



e2 v2



e4



v3



e5



v4



Berapa jumlah path sederhana dari v1 ke v4 ? Berapa jumlah path dari v1 ke v4 ? Berapa jumlah walk dari v1 ke v4?



Suatu graf disebut self-complement jika G dan G isomorfis. Tunjukkan bahwa graf berikut ini self-complement. a



b



d



c



10. Tentukan mana di antara graf-graf berikut ini yang memiliki sirkuit Euler. Carilah sirkuit Euler untuk graf yang memilikinya. v



t s r



11.



a



b



a



c



b



w z



u



c d



x



y



f



e



e d



(c) (b) (a) Pada graf berikut ini, tentukan apakah memiliki sirkuit Hamilton. Jika tidak, berikan alasannya. Jika mempunyai, carilah sirkuit Hamilton tersebut ! b



a c



a e



d



b



d



c



g



f



b



c



d



g



g



f



(a)



a



e



b



e f (c)



(b) b’ b



a’



c’



c



f’



d’



e a.



f d



e’ a



b.



a’ e



d



b



b’



c’



c a c.



e’



d’



f



a’



b’



c’



b h’



e



c d



13. Perhatikan graf berarah G berikut ini!



g’



d’



f’



e h



f g



d (d)



12. Tentukan mana di antara pasangan graf berikut ini yang isomorfis a



a



e’



c



v6



Tentukan : a. Himpunan titik-titik, himpunan garis-garis dan fungsi perkawanan . b. Derajat masuk dan derajat keluar tiap-tiap titik. c. Titik terasing dan titik pendan. d. Garis pararel. e. Komplemen dari graf tersebut f. Matriks hubung g. Matriks biner