Matematika Diskrit [PDF]

Citation preview

BAB I PENDAHULUAN



A. Deskripsi Mata kuliah ini merupakan pengantar tentang Teori Kombinatorik yang meliputi permutasi, kombinasi, fungsi pembangkit, relasi rekursif, fungsi inklusi-eksklusi. Selain itu, mata kuliah ini juga membahas tentang Teori Graph yang meliputi konsep dan teorema dalam graph, graph bagian, graph isomorfik, jalan, jejak, dan lintasan, graph bipartisi, derajat titik, penyajian graph dalam komputer, graph Euler dan Hamilton, pohon, graph planar dan bidang, pewarnaan, algoritma Dijkstra, algoritma Prim, algoritma Kruskal, serta pemakaian graph dalam kehidupan sehari-hari.



B. Prasyarat Materi prasyarat yang dibutuhkan adalah sebagai berikut. 1. Konsep Fungsi 2. Komputer dan pemrogramannya. 3. Geometri Dasar.



C. Petunjuk Belajar Mahasiswa pemakai Buku Ajar ini diharapkan melakukan langkah-langkah belajar sebagai berikut. (1) Membaca dengan cermat isi Buku Ajar ini. (2) Mendengarkan dengan seksama penjelasan Dosen. (3) Bertanya kepada Dosen jika belum jelas. (4) Mengerjakan semua tugas atau latihan soal yang ada pada Buku Ajar ini. (5) Mengembangkan sendiri materi Buku Ajar ini dengan jalan membaca dan mempelajari buku-buku yang terkait dengan Matematika Diskrit.



D. Kompetensi dan Indikator Kompetensi:



1



1. Menjelaskan Teori Kombinatorik yang meliputi permutasi, kombinasi, fungsi pembangkit, relasi rekursif, fungsi inklusi-eksklusi. 2. Menjelaskan Teori Graph yang meliputi konsep dan teorema dalam graph, graph bagian, graph isomorfik, jalan, jejak, dan lintasan, graph bipartisi, derajat titik, penyajian graph dalam komputer, graph Euler dan Hamilton, pohon, graph planar dan bidang, pewarnaan, algoritma Dijkstra, algoritma Prim, algoritma Kruskal, serta pemakaian graph dalam kehidupan sehari-hari. 3. Memecahkan permasalahan yang terkait dengan Matematika Diskrit.



Indikator: 1. Dapat menjelaskan Teori Kombinatorik yang meliputi permutasi, kombinasi, fungsi pembangkit, relasi rekursif, fungsi inklusi-eksklusi. 2. Dapat menjelaskan Teori Graph yang meliputi konsep dan teorema dalam graph, graph bagian, graph Tujuan Penulisan Buku Ajar 4. Agar para mahasiswa memiliki pokok-pokok materi perkuliahan Matematika Diskrit. 3. Agar para mahasiswa sekurang-kurangnya memiliki materi bahan kuliah siap pakai yang ditulis berdasarkan kebutuhan riel di kelas dalam mata kuliah Matematika Diskrit. isomorfik, jalan, jejak, dan lintasan, graph bipartisi, derajat titik, penyajian graph dalam komputer, graph Euler dan Hamilton, pohon, graph planar dan bidang, pewarnaan, algoritma Dijkstra, algoritma Prim, algoritma Kruskal, serta pemakaian graph dalam kehidupan sehari-hari. 4. Dapat memecahkan permasalahan yang terkait dengan Matematika Diskrit.



2



BAB II KEGIATAN BELAJAR 1



A. Kompetensi dan Indikator 1. Menjelaskan Teori Kombinatorik yang meliputi permutasi, kombinasi, fungsi pembangkit, relasi rekursif, fungsi inklusi-eksklusi. 2. Memecahkan permasalahan yang terkait dengan Teori Kombinatorik.



Indikator: 5. Dapat menjelaskan Teori Kombinatorik yang meliputi permutasi, kombinasi, fungsi pembangkit, relasi rekursif, fungsi inklusi-eksklusi. 6. Dapat memecahkan permasalahan yang terkait dengan Teori Kombinatorik.



B. Uraian Materi Pendahuluan Matematika diskrit merupakan cabang matematika yang banyak mempelajari tentang teori kombinatorik dan teori graph. Beberapa topik yang akan kita pelajari dalam teori kombinatorik antara lain Fungsi Pembangkit, Relasi Rekursif, dan Inklusif-Eksklusif. Sedangkan untuk Teori Graph antara lain adalah Definisi dan Terminologi Graph, Derajat Titik, Penyajian Graph dalam Komputer,



Mencari



Lintasan Terpendek Sebuah Graph Bobot, Pewarnaan, juga Graph Pohon.



1. Notasi Faktorial Definisi. Misalkan n bilangan bulat positif, maka 1. 2 . ... . (n-2).(n-1).n disebut “ n faktorial” dan dinotasikan dengan n!.



Ditulis, n! = 1.2.3. ... . (n-2).(n-1).n Dalam hal ini diberlakukan, 0!=1.



Soal latihan 1) 4! = ...



2)



11!  ... 9!



6 3)   !  ... 2



3



4)



n  3!  ... n  1!



5)



n  5!  ... n  3!



2. Notasi Sigma : “ ∑ ” Pandang, jumlah 10 bilangan asli pertama, 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10. Bentuk di atas dapat ditulis dengan: 10



1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 =  i i 1



yang dibaca “sigma i, untuk i dari 1 sampai dengan 10”. Teorema



a.



c konstanta



b. c.



+d



Soal A. Tulis dengan menggunakan notasi sigma 1) a1 + a 2 + a3 + ... + an = ... 2) 12 + 22 + 32 + ... +(50)2 = ... 3)



1 1 1 1 + + + ... + = ... 2. n 1 2 . 3  1 2 . 4  1 2 .5 1



4) 2 + 4 + 6 + 8 + 10 + 12 + 14 + 16 + 18 = ... 5) 2 + 5 + 10 +17 + 26 + 37 +50 +65 +82 +101 = ...



B. Hitunglah 6



1)



 5 = ... i 1



5



2)







5



(i2 + 4i – 5) = ...



3)



i 1



 i 1



4



(i2 + 4i – 5) =



.....



 i 4



..........



3. Permutasi dan Kombinasi Permutasi Suatu susunan r ≤ n objek yang diambil dari n objek berbeda dalam suatu himpunan disebut suatu “permutasi” dari n objek setiap kali diambil r objek dan dinotasikan dengan nPr.



nPr



=



, n dan r bilangan–bilangan bulat positif



Banyaknya permutasi berbeda dari n objek, apabila n1 di antaranya berjenis pertama, n2 berjenis kedua, ..., nk berjenis ke-k adalah:



Soal Latihan 1) Misalkan kita mempunyai tiga huruf a, b, dan c. Tentukan banyak permutasi apabila diambil (a) tiga huruf, (b) dua huruf, dan (c) satu huruf. 2) Diketahui enam buah angka bilangan bulat yaitu 1, 2, 3, 4, 5, dan 6. Berapa banyaknya susunan angka yang mungkin terjadi jika: (a) keenam angka disusun sembarang, (b) susunan keenam angka itu dapat dibagi dua. 3) Berapa banyaknya susunan huruf-huruf pada kata “SEKOLAH” dapat ditukar- tukar tempatnya, jika penukaran huruf tersebut dengan syarat bahwa huruf hidup hanya boleh menempati urutan yang ganjil saja. 4) Dengan berapa cara huruf-huruf dalam perkataan “SEMARANG” dapat disusun dengan menukar huruf-hurufnya.



Kombinasi Dalam kehidupan sehari–hari kita sering dihadapkan pada suatu masalah memilih r buah objek dari n buah objek yang tersedia (r ≤ n) tanpa memperhatikan urutannya. Pemilihan seperti ini disebut “kombinasi” dari n buah objek setiap kali diambil r buah objek dan dinotasikan dengan



5



C



Soal Latihan 1) Tentukan banyaknya cara memilih 3 orang calon anggota pengurus sebuah koperasi dari 4 orang yang memenuhi syarat. 2) Dari 10 orang anggota suatu himpunan akan dipilih 4 orang. (a) Dengan berapa cara dapat dilakukan pemilihan itu. (b) Dengan berapa cara pula jika salah seorang selalu terpilih.



FUNGSI PEMBANGKIT I.1. Deret Kuasa  ) Deret Kuasa adalah deret tak hingga berbentuk







a n 0







n



xn .



) Deret Kuasa yang hanya menekankan kepada koefisien-koefisien dari xn, dikenal sebagai Deret Kuasa Formal.



 ) Rumus-Rumus Dasar 1) ex =







1



 n! x



n



=1+x +



n 0



2) e – x = 1 – x +



1 2 1 3 x + x + ..., untuk x < ∞ 2! 3!



1 2 1 3 x – x +... 2! 3!



3)



1 = 1 – x + x2 – x3 + x4 – x5 +..., untuk x < 1 1 x



4)



1 = 1 x







x



n



= 1+ x + x2 + x3 + x4 +..., untuk x < 1



n 0



5)



1 = 1 + x2 + x4 + x6 + x8 +..., untuk -1< x < 1 2 1 x



6)



1 =1+ 2x + 3x2 + 4x3 + 5x4 +..., untuk x < 1 (1  x ) 2



x2 x3 x4 x 7) ln ( 1 + x ) = – + – + ... 3 2 4 1



6



8) ln ( 1 – x ) = –



x2 x3 x4 x – – – – ... 3 2 4 1



x3 x5 x 9) sin x = – +  ... 3! 1! 5! 10) cos x =



x2 x4 x0 x6 – + + ...  0! 6! 2! 4!



11)



e x  e x x2 x4 x0 x6 = + + + + ... 0! 6! 2! 4! 2



12)



e x  e x x5 x7 x x3 = + + + + ... 7! 5! 1! 3 ! 2



13)



1 = (1  x ) n



 n  k  1 k  x = ( 1+ x + x2 + x3 + x4 +...)n k k 0   



 



1 xn  1  x  x 2  ....  x n1 14) 1 x 15) Teorema Binomial Untuk bilangan real u, bilangan non negatif k , dan x < 1 berlaku: ( 1 + x )u =



, di mana



Rumus-rumus dasar tersebut dapat diperoleh dengan mengekspansikan suatu fungsi dengan Deret Taylor. Deret Taylor fungsi f(x) di sekitar x = 0 punya bentuk sebagai berikut. 



F (x) =



1



 n!f



(n)



(0) x n



n 0



= f(0) +



1 1 1 f’(0) x + f’’(0) x2 + f’’’’(0) x3 + ... 1! 2! 3!



I.2. Definisi Fungsi Pembangkit



Pandang (an) = (a0 , a1 , a2,...) suatu barisan.



7



Fungsi Pembangkit Biasa (FPB) dari barisan (an) didefinisikan sebagai:



= a0 + a1 x + a2 x2 + a3 x3 + a4 x4 + …



Fungsi pembangkit eksponensial (FPE) dari barisan ( an) didefinisikan sebagai:



= a0 + a1



+ a2



+ a3



+ a4



+ ...



Contoh : 1) e x = 1 + x +



1 2 1 3 x + x + ..., merupakan 2! 3!



FPB dari barisan (1 , 1,



1 1 , , ...) 2 ! 3!



FBE dari barisan ( 1, 1, 1, 1, ...) 2) Diketahui: barisan a) ( 0, 0,



1 1 1 , , ... ) 2 ! 3! 4 !



b) ( 0, 2, 4, 6, ..., 2n, ... ) Ditanyakan : Bentuk sederhana Fungsi Pembangkit Biasa. Jawab: a) FPB yang dimaksud adalah P (x) = 0 + 0x +



=



1 2 1 3 1 4 x + x + x + ... 2! 3! 4!



1 2 1 3 1 4 x + x + x + ... 2! 3! 4!



=(1+x +



1 2 1 3 1 4 x + x + x + ...) – x – 1 2! 3! 4!



=ex–x–1



8



b) FPB yang dimaksud adalah P (x) = 0 + 2x + 4x2 + 6x3 + ... + 2nxn + ... = 2x + 4x2 + 6x3 + ... + 2nxn + ... = 2x (1+ 2x + 3x2 + ... + nxn-1 + ...) = 2x (



=



1 ), untuk x < 1 (1  x ) 2



2x (1  x ) 2



Soal latihan 1) Tulis FPB dari barisan–barisan berikut. a) ( 0, 0, 0, 1, 1, 1, 1,...) b) ( 0, 0,



1 1 1 , , ,... ) 2 ! 3! 4 !



c) ( 0, 1, 0, 1, 0, 1, ...) 2) Tulis FPE dari barisan berikut. a) ( 3, 3, 3, 3, ...) b) ( 0, 1, 0, 1, 0, 1, ...) 3) P(x) adalah FPB dari barisan (an). Carilah barisan (an). a) P (x) = 1 +



1 1 x



b) P (x) =



2 + 3x2 + 6x +1 1 x



c) P (x) =



1 x e  e x 2











d) P (x) = 2x + e  x 4) Tulis barisan ( an), jika FPE adalah sebagai berikut. a) P (x) = 5 + 5x + 5x2 + 5x3 b) P (x) =



1 1  4x



9



1.3. Fungsi Pembangkit untuk Kombinasi Permasalahan Ada berapa cara, jika ada tiga macam objek a, b, dan c, diambil k objek dengan ketentuan bahwa a terambil maksimum 1, b terambil maksimum 2, dan c terambil maksimum 1. Penyelesaian: Permasalahan tersebut dapat ditulis menjadi: [ (ax)0 + (ax)1] [ (bx)0 + (bx)1 + (bx)2] [ (cx)0 + (cx)1] = (a0x0 + a1x1) (b0x0 + b1x1 + b2x2) (c0x0 + c1x1) = ( 1 + ax ) ( 1 + bx + b2x2 ) ( 1 + cx ) = 1 + (a + b + c )x + (ab +ac + bc + b2 )x2 + (abc +ab2 + b2 c)x3 + ab2c x4 Misalkan untuk 2 huruf , maka perhatikan koefisien dari x 2, yaitu ab, ac, bc, dan bb, sehingga terdapat 4 cara. Ini berarti (a + b + c ) x menyatakan ada 3 cara untuk 1 huruf (ab +ac + bc + b2 ) x2 menyatakan ada 4 cara untuk 2 huruf (abc +ab2 + b2 c) x3 menyatakan ada 3 cara untuk 3 huruf ab2c x4 menyatakan ada 1 cara untuk 4 huruf Permasalahan tersebut dapat dicari dengan menggunakan FPB. FPB dari permasalahan tersebut adalah: P (x) = (1 + x) ( 1 + x + x2 ) ( 1 + x ) = 1 + 3x + 4x2 + 3x3 + x4 Dari P(x) tersebut, pangkat dari x menyatakan banyaknya huruf sedangkan koefisien dari masing- masing suku menyatakan banyaknya cara. Misalnya untuk 4x2, maka untuk 2 huruf ada 4 cara. Contoh 1) Ada berapa cara untuk memilih n objek dari k macam objek sehingga tiap objek terpilih paling sedikit satu. Jawab: FPB dari permasalahan tersebut adalah: P( x ) = ( x + x2 + ...) ( x + x2 + ...)... ( x + x2 + ...) sebanyak k faktor = ( x + x2 + x3 + ...)k 10



= ( x(1 + x + x2 + x3 + ...))k = x k ( 1 + x + x2 + ...)k =xk



1 (1  x ) k



=xk



 k  t  1  x t t 0   



 



  k  t  1  x =   t t 0     n 1  x =   n k  n  k 



tk



t



,n=t+k



n



Jadi banyaknya cara untuk memilihnya = koefisien xn dalam P(x), yaitu {0 n1 ,n  k



 n  k  , n  k  



2) Tentukan banyaknya solusi bulat dari suatu persamaan linear x1+x2 + x3 = 50, xi ≥ 0,  i  {1, 2, 3} Jawab : FPB dari permasalahan tersebut di atas adalah: P ( x ) = (1 + x + x2 + ...)3 =



1 (1  x) 3



  3  k  1 k x =   k  k 0 



2  k  k  x k 0  k  



=



 



Jadi banyaknya solusi bulat yang dimaksud adalah = koefisien x50 dalam P( x )



 2  50   52      1326 =   50   50  Soal 1)



Tentukan banyak cara memilih k huruf dari huruf-huruf C, A, N, T, I, K sedemikian hingga memuat paling sedikit satu C.



11



2)



Tentukan banyaknya cara solusi bulat dari persamaan x1 + x2 + x3 + x4 = 80, 1 ≤ xi ≤ 30, i { 1, 2, 3, 4}.



1.4. Fungsi Pembangkit untuk Permutasi Permasalahan ) Bentuklah kata sandi yang panjangnya 3 huruf dengan syarat : a ≤ 2, b ≤ 2, c ≤ 1. ) Masalah tersebut bila diselesaikan dengan menggunakan FPB akan diperoleh koefisien x 3 hanya 5 suku ( mengapa?), padahal ada 18 permutasi. ) 18 permutasi tersebut adalah sebagai berikut. aab, aac, bba, bbc, abc, bca, aba, aca, bab, bcb, acb, cab, bba, baa, abb, cbb, bac, cba. ) Untuk menyelesaikan permasalahan tersebut digunakan FPE. Kalau banyak hurufnya 3, maka yang diperhatikan adalah koefisien dari



x3 3!



Fungsi pembangkit untuk permasalahan di atas adalah sebagai berikut. P( x ) = ( 1 +



x2 x2 x x x + )(1+ + )(1+ ) 2! 2! 1! 1! 1!



= 1 + 1! (



x2 1 1 1 x 1 1 1 1 1 + + ) +2!( + + + + ) 1! 1! 1! 1! 1!1! 1!1! 2! 2! 1!1! 2 !



1 1 1 1 1 x3 +3!( + + + + ) 2!1! 2!1! 1! 2! 2!1! 1!1!1! 3 !



+4!(



x4 1 1 1 + + ) 1!2!1! 2!2! 2!1!1! 4 !



+5!(



x5 1 ) 2!2!1! 5!



Jadi banyaknya kata sandi dengan panjang 3 yang memenuhi syarat tersebut = koefisien



= 3! (



x3 dalam P(x) 3!



1 1 1 1 + + + + 1 ) = 18 2 2 2 2



12



Barisan Biner Barisan Biner adalah barisan yang digitnya (angkanya 1 atau 0) Contoh:



a) ( 0, 0) b) ( 1, 1, 0 ) c) ( 1, 1, 1, 1) d) ( 1, 0, 1, 0)



Banyaknya barisan biner yang panjangnya 3 adalah 8 = 23 yaitu ( 0, 0, 0 ), ( 0, 0, 1 ), ( 0, 1, 0 ), ( 1, 0, 0 ), ( 1, 1, 0 ), ( 1, 0, 1 ), ( 0, 1, 1 ), dan ( 1, 1, 1 ) Banyaknya barisan biner yang 0 genap dan 1 ganjil dengan panjang 3 adalah ( 0, 0, 1 ), ( 0, 1, 0 ), ( 1, 0, 0 ).



Contoh Tentukan banyaknya barisan biner k angka ( panjangnya k), yang memuat angka nol sebanyak genap dan angka satu sebanyak ganjil . Penyelesaian: Fungsi Pembangkit untuk permasalahan di atas adalah:



x2 x4 x5 x6 x7 x x3 + + + ...) ( + + + + ...) 2! 4! 5! 1! 3 ! 6 7



P (x) = ( 1 +



e x  e x 2



ex  ex = 2 =







1 2x e  e 2 x 4



1 = 4 1 = 4







 k 0







2x k k!







1 4



2k x k 1  k! 4 k 0







 2x k



k 0



k!



 



 2k x k



k 0



k!







Jadi banyaknya barisan biner k angka yang diminta adalah: = koefisien dari



xk dalam P(x) k!



13



=



1 k 1 . 2 - .(-2)k 4 4



Soal 1) Sebuah kata sandi yang panjangnya k, dibentuk dengan menggunakan hurufhuruf a,b,dan c, sedemikian hingga memuat paling sedikit satu a, satu b, dan satu c. Ada berapa kata sandi yang dapat dibuat. 2) Tentukan banyaknya barisan biner n angka yang memuat angka “1” sebanyak bilangan genap.



RELASI REKURSIF Ilustrasi 1. Misal Pn adalah banyaknya permutasi dari n objek yang berbeda. Diperoleh hubungan: P1 = 1, Pn = n.Pn-1, n ≥ 2 ... (1) Bentuk (1) disebut relasi rekursif untuk Pn. P1 = 1 disebut kondisi awal. Pn = n.Pn-1 disebut bagian rekursif dari relasi rekursif tersebut. 2. Diketahui barisan bilangan fibonacci (1, 1, 2, 3, 5, 8, 13, ...) Fn = suku ke n. Diperoleh hubungan: F1 = F2 = 1 Fn = Fn-1 + Fn-2. n ≥ 3 F1 = 1 dan F2 = 1 disebut kondisi awal. II.1 Relasi Rekursif Linear dengan Koefisien Konstanta Bentuk umum bagian rekursif dari suatu relasi rekursif linear berderajat k adalah sebagai berikut. an + h1(n) an-1 + h2 (n) an-2 + ... + hk (n) an-k = f (n) Di mana hi(n) dan f (n) adalah fungsi dalam n dan hk(n) ≠ 0  ) Jika f(n) =0 maka relasi rekursifnya disebut homogen, jika tidak demikian disebut non homogen.



14



 ) Jika untuk setiap i  {1, 2, 3,...k}, hi (n) = konstanta, maka relasi rekursifnya disebut relasi rekursifnya dengan koefisien konstanta.  ) Suatu relasi rekursif berderajat k terdiri dari sebuah bagian rekursif dan k kondisi awal berurutan. Contoh 1. a1 = a2 = 0 ; an = an-1 + an-2 + 1, n ≥ 3 adalah relasi rekursif linear non homogen berderajat dua dengan koefisien konstanta. 2. a1 = a2 = 0 ; an = an-1 + an-2 , n ≥ 3 adalah relasi rekursif linear homogen berderajat dua dengan koefisien konstanta.



II.1 Relasi Rekursif Linear Homogen dengan Koefisien Konstanta Bentuk umum an + c1 an-1 + c2 an-2 + ... + ck an-k = 0 ; ck ≠ 0 dengan k kondisi awal, dan untuk 1 ≤ i ≤ k , ci = konstanta,



Menyelesaikan Relasi Rekursif dengan Metode Akar Karakteristik a. Untuk akar-akar berbeda. Langkah-langkah penyelesaian yang dapat dilakukan adalah sebagai berikut. 1) Misalkan an = xn , x ≠ 0 2) Jika x1, x2, ..., xk akar –akar yang berbeda, maka solusi umumnya: an = c1 .........(*) 3) Dengan k kondisi awal, diperoleh c1, c2, ..., ck. 4) Masukkan ke persamaan (*), diperoleh solusi dari relasi rekursifnya.



Contoh Selesaikan hubungan rekursif berikut. a1 = a2 = 1, an = an-1 + an-2 , n ≥ 3 Penyelesaian: Misal an = xn , x ≠ 0 Bentuk rekursif an = an-1 + an-2 menjadi: xn = xn-1 + xn-2



15



 xn - xn-1 - xn-2 = 0 ( bagi dengan xn-2 ) 



x2 - x -1 = 0 ( disebut persamaan karakteristik)







x1 =



1 5 1 5 , x2 = 2 2



Solusi umumnya adalah: an = c1 (



1 5 2



)n



+ c2 (



)n



1 5 2



Dari kondisi awal : a1 = 1 dan a2 = 1, jika disubstitusikan pada solusi umum, diperoleh: 1 = c1 (



1 5 2



)



1 = c1 (



1 5 2



)2



+ c2 (



1 5 2



+ c2 (



1 5 2



) )2



Selesaikan kedua persamaan tersebut, sehingga diperoleh nilai c1 dan c2. Dari perhitungan diperoleh c1= an =



5 5



( 1



5



2



)n



5  5 dan c2 = jadi solusi dari relasi rekursifnya: 5 5 -



5 1 5 ( 5 2



)n



Catatan an melibatkan bilangan irasional. Tetapi untuk setiap n ≥ 1, maka an merupakan bilangan bulat non negatif. b) Untuk akar rangkap Langkah –langkah penyelesaian yang dapat dilakukan sama dengan relasi rekursif yang mempunyai akar yang berbeda. Misalkan terdapat m akar rangkap, yang nilainya x1, di mana m ≤ k. Solusi umumnya adalah sebagai berikut. an = c0



Contoh Carilah formula untuk an yang memenuhi relasi berikut. an = 3 an-1 + 6 an-2 – 28 an-3 + 24 an-4 Dengan a0 = 1 ; a1 = 2; a2 = 3 dan a3 = 4



16



Penyelesaian: Misal an = xn ; x ≠ 0. Bagian rekursi dari relasi rekursinya adalah sebagai berikut. xn = 3 xn-1+ 6 xn-2 – 28 xn-3 + 24xn-4  xn - 3 xn-1 - 6 xn-2 + 28 xn-3 - 24xn-4 = 0 ( bagi dengan xn-4)  x4 - 3 x3 - 6 x2 + 28 x – 24 = 0 ( disebut persamaan karakteristik)  ( x – 2 )3 ( x + 3 ) = 0 Akar –akar dari persamaan karakteristiknya: x = 2 ( rangkap 3 ) dan x = -3 Solusi umum dari rekursi di atas : an = c1 2 n  c 2 n 2 n  c 3 n 2 2 n  c 4 (3) n



............(*)



Untuk a0 = 1 ; a1 = 2 ; a2 = 3 dan a3 = 4, dari (*) diperoleh sistem persamaan berikut. 1 = c1 + c4 2 = 2 c1 + 2 c2 + 2 c3 – 3 c4 3 = 4 c1 + 8 c2 + 16 c3 + 9 c4 4 = 8 c1 + 24 c2 + 72 c3 – 27 c4 Sehingga : C1 = 1



2 3 2 7 ; C2 = ; C3 =  ; C4 =  125 40 125 200



Substitusikan nilai-nilai tersebut dalam persamaan (*), maka penyelesaiannya: an = 1



2 3 2 n 2 7 (2)n + n (2)n  n (2)  ( -3 )n 125 40 125 200



Soal latihan Selesaikan relasi rekursi berikut dengan metode akar karakteristik. 1) a0 = 0 , a1 = -1 an = 7 an-1 – 12 an-2 , n ≥ 2 2) a0 = a1 = 1 an = 2 an-1 + 3 an-2 , n ≥ 2



C. Latihan BAB II Kerjakan soal berikut dengan benar, dengan memakai Lembar Kegiatan seperti ditulis dalam butir D di bawah.



17



1) Dari 6 pelamar pria dan 5 pelamar wanita akan diterima hanya 4 orang pelamar. Dengan berapa cara penerimaan pelamar dapat dilakukan, jika sekurang-kurangnya ada seorang wanita dari keempat pelamar. 2) P(x) adalah FPB dari barisan (an). Carilah barisan (an). P (x) = 2x + e  x . 3) Tulis barisan ( an), jika FPE adalah sebagai berikut. P (x) = 5 + 5x + 5x2 + 5x3. 4) Ada berapa cara untuk menentukan 50 koin yang sama kedalam 5 kotak yang berbeda sedemikian sehingga tidak ada kotak yang kosong. 5) Tentukan banyaknya barisan biner n –angka yang memuat angka “0” sebanyak ganjil dan “1” sebanyak genap.



6) Selesaikan relasi rekursi berikut dengan metode akar karakteristik. a1 = 2 , a2 = 6 an – 4 an-1 + 4 an-2 = 0 , n ≥ 3.



D. Lembar Kegiatan Kerjakan soal pada butir soal C dengan menggunakan Lembar Kegiatan berikut. No. 1.



Soal



Pengerjaan



Dari 6 pelamar pria dan 5



.......................................



pelamar wanita akan diterima



.......................................



hanya 4 orang pelamar. Dengan



.......................................



berapa cara penerimaan pelamar dapat dilakukan, jika sekurangkurangnya ada seorang wanita dari keempat pelamar. 2.



Dst.



3. 4. 5.



Tandatangan dosen pengampu



18



E. Rangkuman 



1) Deret Kuasa adalah deret tak hingga berbentuk



a n 0



n



xn .



2) Deret Kuasa yang hanya menekankan kepada koefisien-koefisien dari xn, dikenal sebagai Deret Kuasa Formal. 3) Pandang (an) = (a0 , a1 , a2,...) suatu barisan. Fungsi Pembangkit Biasa (FPB) dari barisan (an) didefinisikan sebagai: = a0 + a1 x + a2 x2 + a3 x3 + a4 x4 + …



Fungsi pembangkit eksponensial (FPE) dari barisan ( an) didefinisikan sebagai:



= a0 + a1



+ a2



+ a3



– a4



+ ...



4) Bentuk umum Relasi Rekursif Linear Homogen dengan Koefisien Konstanta Bentuk umum an + c1 an-1 + c2 an-2 + ... + ck an-k = 0 ; ck ≠ 0 dengan k kondisi awal, dan untuk 1 ≤ i ≤ k , ci = konstanta,



F. Tes Formatif Kerjakan dengan cermat dan benar! 1)



n  5!  ... n  3!



2) Tentukan banyaknya barisan biner n –angka yang memuat angka “0” sebanyak ganjil dan “1” sebanyak genap. 19



3) Selesaikan relasi rekursi berikut dengan metode akar karakteristik. a0 = 0, a1 = 1, a2 = 2 an = 9 an-1 – 15 an-2 + 7 an-3 , n ≥ 3



20



BAB III KEGIATAN BELAJAR 2



A. Kompetensi dan Indikator Kompetensi: 1. Menjelaskan Teori Graph yang meliputi konsep dan teorema dalam graph, graph bagian, graph isomorfik, jalan, jejak, dan lintasan, graph bipartisi, derajat titik, penyajian graph dalam komputer, graph Euler dan Hamilton, pohon, graph planar dan bidang, pewarnaan, algoritma Dijkstra, algoritma Prim, algoritma Kruskal, serta pemakaian graph dalam kehidupan sehari-hari. 2. Memecahkan permasalahan yang terkait dengan Teori Graph..



Indikator: 1. Dapat menjelaskan Teori Graph yang meliputi konsep dan teorema dalam graph, graph bagian, graph isomorfik, jalan, jejak, dan lintasan, graph bipartisi, derajat titik, penyajian graph dalam komputer, graph Euler dan Hamilton, pohon, graph planar dan bidang, pewarnaan, algoritma Dijkstra, algoritma Prim, algoritma Kruskal, serta pemakaian graph dalam kehidupan sehari-hari. 2. Dapat memecahkan permasalahan yang terkait dengan Teori Graph..



B. Uraian Materi



TEORI GRAPH Definisi dan Terminologi  Sebuah Graph G adalah pasangan (V(G), E(G)) di mana V(G) : Himpunan titik (berhingga, tak kosong) dan E(G) : Himpunan sisi (mungkin kosong) sedemikian sehingga setiap sisi e di dalam E(G) adalah pasangan tak berurutan dari titik-titik di V(G).  Jika u dan v adalah titik-titik di G dan e = {u,v}; (sering ditulis e = uv) adalah sisi dari G, kita katakan: 



Sisi e menghubungkan titik-titik u dan v;







u dan v berhubungan langsung (adjacent);







u dan v titik-titik akhir dari sisi e; 21







sisi e terkait (incident) dengan titik u dan v.



 Sebuah graph dapat dipresentasikan dalam bentuk diagram, di mana setiap titik digambarkan dengan sebuah noktah dan setiap sisi yang menghubungkan dua titik digambar dengan kurva sederhana (ruas garis) dengan titik-titk akhir di kedua titik tersebut. Contoh: Sebuah graph G = (V(G), E(G)) dengan V(G) = {u, v, w, x, y, z} dan E(G) = {e1, e2, e3, e4, e5, e6, e7} di mana e1 = uv , e2 = uw , e3 = ux , e4 = vx , e5 = wx , e6 = xz , e7 = xy dapat dipresentasikan dalam bentuk diagram seperti terlihat pada gambar berikut.



 Sebuah sisi di graph G yang menghubungkan sebuah titik v dengan dirinya sendiri disebut gelung (loop).  Dalam sebuah graph, apabila terdapat lebih dari satu sisi yang menghubungkan dua titik, maka sisi-sisi tersebut disebut sisi rangkap (multi edges)







Graph G dengan 5 titik dan 8 sisi; Sisi e8 disebut gelung Sisi-sisi e4, e5, e6 disebut sisi rangkap. 22



 Sebuah graph yang tidak memiliki gelung dan tidak memiliki sisi rangkap disebut graph sederhana.



 Graph yang memiliki sisi rangkap tetapi tidak memiliki gelung disebut graph rangkap (multi graph).



G



M



G : graph Sederhana



M : Graph Rangkap



Kn : graph komplit dengan n titik. : graph sederhana di mana untuk setiap dua titik dihubungkan dengan sebuah sisi. K n : Graph kosong dengan n titik.



: graph dengan n titik yang tidak punya sisi.



K5  Sebuah graph G disebut Graph Bipartisi jika V(G) dapat dipartisi menjadi dua himpunan A dan B sedemikian hingga setiap sisi dari G menghubungkan sebuah titik di A dan sebuah titik di B. Kita sebut (A,B) bipartisi dari G.



Selanjutnya apabila G sederhana dan bipartisi dengan partisi (A,B) sedemikian hingga setiap titik di A berhubungan langsung dengan setiap titik di B, maka G disebut Graph Bipartisi Komplit, dilambangkan dengan Km,n , di mana |A| = m dan |B| = n.



23



G : graph bipartisi tak komplit



K3,2 : graph bipartisi komplit



Dengan bipartisi (A,B) A = { a1, a2, a3, a4 } B = { b1, b2, b3 }  Grap H disebut graph bagian dari graph G, ditulis H  G, jika V(H)  V(G) dan E(H)  E(G). Jika H  G dan V(H) = V(G), maka H disebut Graph bagian rentang (Spanning Subgraph) dari G. Graph bagian dari G yang dibangun oleh V1 (V1  V(G)), ditulis G[V1], adalah graph bagian dari G yang himpunan titiknya adalah V1 dan himpunan sisinya beranggotakan semua sisi G yang mempunyai titik-titik akhir di V1.



G



H1



H2



H3



 H1 graph bagian dari G  H2 graph bagian rentang dari G  H3 graph bagian G yang dibangun oleh {u, w, x, z} atau H3 = G [{u, w,x, z}]  Dua graph G dan H isomorfik, ditulis G  H, apabila ( i ) terdapat korespondensi satu-satu antara V(G) dan V(H), ( ii ) banyaknya sisi yang menghubungkan dua titik u dan v di G, sama dengan banyaknya sisi yang menghubungkan dua titik di H yang berkorespondensi dengan titik u dan v.



24



G1 



G2



G3



G1  G2 lewat korespondensi : a t , d  q b s , e p c r , f  u







G1



G3



 Sebuah jalan (walk) di graph G adalah sebuah barisan berhingga (tak kosong) W = vo e1 v1 e2 v2



...



ek vk ,



yang suku-sukunya bergantian titik dan sisi, sedemikian hingga vi-1 dan vi adalah titik-titik akhir dari e1, untuk 1 ≤ i ≤ k. W adalah jalan dari vo ke v k, atau jalan(v 0 ,v k).  Titik awal dari W: v 0  Titik akhir dari W: v k  Titik-titik Internal W: v1 , v2 , ..., vk 1  Panjang W = k (banyak sisi di W).  Jika semua sisi e1 , e2 , ..., ek dalam jalan W berbeda, maka W disebut jejak (trail).  Jika semua titik v0 , v1 , v2 , ..., vk di jalan W juga berbeda, maka W disebut lintasan (path).  Jalan tertutup: jalan yang titik awal dan titik akhirnya sama (panjang jalan harus > 0 ).  Sebuah jejak tertutup (closed trail) yang titik awal dan semua titik internalnya berbeda disebut sikel (cycle).



25



Banyaknya sisi dalam suatu sikel disebut panjang dari sikel tersebut. Sikel dengan panjang k disebut sikel-k.  Perhatikan graph berikut ini.







Jalan (walk) : a f b f c d e







Jalan tertutup : a b f c g c f e a







Jejak (trail)







Jejak tertutup : a f e d c f b a







Lintasan



: a e f c g







Sikel



: a e d c f a



: a f c d f b



 Sebuah graph G disebut graph terhubung jika untuk setiap dua titik u dan v di G, terdapat lintasan (path) di G yang menghubungkan kedua titik tersebut. Sebaliknya, graph G disebut graph tak terhubung (terputus).  Sebuah Komponen dari graph G adalah sebuah graph bagian terhubung maksimal (titik dan sisi) dari G.



sebuah graph terhubung



26



 Sebuah graph terhubung, tanpa sikel disebut pohon (tree).



pohon (tree)



 Misalkan G adalah graph sederhana. Komplemen G, ditulis G , adalah graph sederhana yang himpunan titiknya sama dengan himpunan titik G, dan dua titik u dan v di G berhubungan langsung jika dan hanya jika u dan v tidak berhubungan langsung di G.



G  Misal G adalah sebuah graph. Apabila G  G , G disebut graph komplemen-diri (self-Complementary graph).



G Perhatikan bahwa G  G  Catatan. Jika G graph sederhana dengan n titik, maka G  G = Kn



Soal latihan 1. Perhatikan graph G di bawah ini. 27



a. Cari sebuah jalan tertutup denagn panjang 9. b. Cari sebuah jejak terbuka dengan panjang 9. c. Cari sebuah jejak tertutup dengan panjang 7. d. Cari sebuah lintasan dari a ke n e. Cari panjang sikel terpanjang dalam G f. Berapakah panjang lintasan terpanjang? g. Cari sebuah graph bagian bukan rentang dari G. h. Cari sebuah graph bagian rentang dari G i. Tulis graph bagian yang dibangun oleh {a, b, d, f, j, k, l} 2. Gambar sebuah graph yang: a. mempunyai lima titik, tanpa sikel, terhubung; b. mempunyai enam titik, dua komponen; c. sederhana sedemikian hingga G dan G mempunyai banyak sisi yang sama. 3. Manakah graph berikut yang bipartisi?



. G1



G2



G3



G4



4. Perhatikan graph-graph berikut ini



G



H



K



28



a. Apakah G isomorfik dengan H? b. Apakah H isomorfik dengan K? c. Apakah G isomorfik dengan K?



Derajat Titik  Misalkan v adalah sebuah titik di graph G. Banyaknya sisi G yang terkait di titik v (loop dihitungkan dua kali) disebut derajat titik v, dilambangkan dengan dG(v) atau d(v).  Derajat minimum dari G dinotasikan  (G), didefinisikan sebagai  (G) = minimum { d(v) : v  V(G) }. Derajat maksimum dari G dinotasikan  (G), didefinisikan sebagai  (G) = maksimum { d(v) : v  V(G) }.  Graph G disebut beraturan-k apabila setiap titik G berderajat k.  Lemma Jabat Tangan: Untuk setiap graph G berlaku



 d(V)  2 E(G) .



vV ( G )



 Banyaknya titik yang berderajat ganjil adalah genap.  Barisan derajat dari graph G adalah barisan monoton turun dari derajat titik-titk G. Sedangkan barisan derajat dari sebuah graph sederhana disebut graphik.  Barisan bilangan bulat non negatif ( d1, d2, d3, … ,dn) adalah barisan derajat dari sebuah graph jika dan hanya jika



 d genap. i 1



i



 Misalkan   d1, d 2 , d3 ,, d n  adalah barisan bilangan bulat non negatif yang monoton turun,  graphik jika dan hanya jika barisan:



d



2







 1, d3  1, d 4  1,, dd1 1  1, dd1  2 , dd1  3 ,, d n merupakan graphik.



Soal latihan 1. Apakah barisan-barisan berikut merupakan barisan derajat dari suatu graph? Mengapa? Jika graph, gambarkan graphnya! a) 6, 5, 4, 3, 3, 2, 2, 2 b) 5, 4, 4, 3, 3, 2, 1, 0 c) 3, 3, 3, 3, 3, 3 d) 5, 4, 3, 2, 1, 0 2. Yang manakah dari barisan-barisan berikut merupakan grafik?



29



a) 5, 4, 3, 3, 3, 3 b) 5, 5, 3, 3, 2, 2, 2



Penyajian Graph dalam Komputer Ada beberapa cara untuk menyajikan sebuah graph di dalam komputer. Matriks adalah cara yang sering digunakan. Ada dua matriks yang akan digunakan, yaitu: 



matriks berhubungan langsung (adjacency matrix)







matris keterkaitan (incidence matrix)



 Misalkan G sebuah graph dengan V(G) = {v1, v2, v3,…, vn}. Matriks berhubungan langsung dari G adalah matriks bujur sangkar berordo n, A(G) =(ai j) di mana elemen ai j menyatakan banyaknya sisi yang menghubungkan titik vi dan titik vj Contoh :



v1 v2 v3 v4 v5



v1 0 v2 1 v3 0  v4 0 v5 3



1 0 0 3 0 1 0 0 1 0 1 1  0 1 1 0 0 1 0 0 A(G)



G  Misalkan graph G mempunyai n buah titik : v1, v2, v3,…, vn dan s sisi : e1, e2, e3, . . . , en. Matriks keterkaitan (incidence matrix) dari G adalah matriks M(G) = (mi j) berordo n x s, di mana 0, jika sisi e j tidak terkait dengan titik v i . mi j =



1, jika ej terkait dengan vi dan ej bukan gelung. 2, jika ej terkait dengan vi dan ej adalah gelung.



Matriks keterkaitan dari graph G di bawah adalah:



30



e1 e2 e3 e4 e5 e6 e7



v1 2 v 2 0 M (G )  v 3 0  v 4 0



1 1 1 0 0 0 1 0 0 1 2 1 0 1 1 1 0 0  0 0 0 0 0 1



Soal latihan 1. Gambar graph G yang matriks berhubungan langsungnya sebagai berikut.



0 0  a. 1  0 1



0 1 0 1 0 1 1 0 1 0 1 1  1 1 0 1 0 1 1 0



0 2 b.  3  4



2 3 4 0 3 2 3 1 1  2 1 1



2. Tulis matriks berhubungan langsung dan matriks keterkaitan dari graph berikut.



a.



b.



Lintasan Terpendek Bila sisi e dalam graph G dikaitkan/dipetakan dengan sebuah bilangan real W(e), maka W(e) disebut bobot (weight) dari e. Graph bobot adalah sebuah graph yang setiap sisinya dikaitkan dengan bilangan real. Sedangkan bobot dari sebuah graph G, dilambangkan dengan W(G), adalah jumlah bobot semua sisi G.



31



Algoritma Dijkstra Untuk mencari panjang lintasan terpendek dari sebuah titik s ke sebuah titik t di graph bobot G, dapat diterapkan Algoritma Dijkstra, sebagai berikut. Input : Graph-bobot G dengan s, t  V(G) Step 1 : Label titik s dengan (s) = 0 dan untuk setiap v di G selain s, label v dengan (s) =  (dalam praktek  diganti dengan bilangan yang “sangat besar”). Tulis T = V(G). (T : himpunan titik yang berlabel sementara) Step 2 : Misalkan u  T dengan (u) minimum Step 3 : Jika u = t, Stop; dan beri pesan : panjang lintasan terpendek dari s ke t adalah (t). Step 4 :  sisi e = uv, v  T ; ganti label v dengan (v) = minimum {(v), (u) + w(e)} Step 5 : Tulis T = T – {u } dan selanjutnya pergi ke step 2. Perhatiakn graph bobot G dengan bobot W(G) = 50 di bawah ini .



d(v1 v5) = 7 (panjang lintasan terpendek dari v1 ke v5) W(v1 v2) = 3 (bobot sisi v1 v2) Terapkanlah Algoritma Dijkstra untuk mencari panjang lintasan terpendek dari titik v1 ke titik v11 dalam graph bobot G tersebut. ---000---



32



GRAPH EULER Persoalan



Jembatan Konisberg pada sungai Pregel.



Teka-teki: Adakah perjalanan yang melalui suatu jembatan hanya satu kali dan kembali ke tempat semula berangkat?



Leonhard Euler dalam “ Solutio problematis ad geometriam situs pertinentis” (1736) mengatakan tidak ada jenis perjalanan tersebut. Dalam bahasa graph, mencari jejak tertutup yang melalui setiap sisi graph G hanya satu kali saja.



Definisi Graph terhubung G = ( V,E ) yang mempunyai jejak tertutup yang memuat setiap sisi graph G disebut graph Euler. Jejaknya disebut jejak Euler. Jika jalurnya tidak tertutup, maka G disebut graph semi Euler.



Graph Euler



Graph Semi Euler



ABCDEF 



CBAED



BGECGFA



CFEBFD



33



Bukan graph Euler



Teorema pada Graph Euler. 1. Graph terhubung G adalah graph Euler jhj derajat setiap titiknya merupakan bilangan genap. 2. Graph terhubung G adalah graph Euler jhj graph G dapat dipecah menjadi sikelsikel yang sisi-sisinya saling lepas. 3. Graph terhubung G adalah semi Euler jhj G mempunyai 2 titik yang berderajat ganjil.



Soal latihan 1. Susunlah jejak Eulernya.



2 Perhatikan denah bangunan berikut.



a) Gambarlah graph yang mewakili denah bangunan tersebut. b) Susunlah jejak Eulernya.



34



GRAPH HAMILTON Definisi: Graph terhubung G disebut graph Hamilton kalau ada sikel yang memuat semua titik pada graph G. Jika hanya ada lintasan terbuka yang memuat semua titik pada graph G maka graph G disebut semi hamilton.



Teorema: Jika G merupakan graph sederhana dengan n titik dan d (v) ≥



n 2



untuk setiap titik v



maka G merupakan graph Hamilton. Contoh V(G)= 6, d (V) = 3 Salah satu sirkuit Hamilton u v  z  w x  y u



PEWARNAAN Persoalan. Perhatian gambar benua Australia berikut ini.



I



Western Australia (WA)



II



Northern Territory (NT)



III Queensland (Q) IV



South Australia (SA)



V



Victoria (V)



VI New South Wales (NSW) VII Tasmania (T) VIII Lautan (L)



35



Bagaimana mewarnai dengan warna berbeda di setiap wilayah dan banyaknya warna adalah minimum? atau “Bagaimana menentukan minimum banyaknya warna agar titik-titik yang berhubungan langsung mempuyai warna yang berlainan?” Banyaknya warna yang minimum ini disebut bilangan kromatik graph tersebut.



Contoh 1



Penyelesaian Cara I : Intuitif Bilangan kromatik pada graph G ada 4.



Cara II : Algoritma pertama terbesar 1. Urutkan derajat titik- titik secara menurun. 2. Tandai titik yang berderajat terbesar dengan angka 1. 3. Tanda 1 ini secara berurutan digunakan untuk menandai setiap titik lainnya yang tidak berhubungan langsung dengan titik yang berderajat terbesar. 4. Ulangilah langkah ini dengan warna ke 2, ke 3, dan seterusnya sampai semua titik bertanda. 5. Nomor tanda terakhir menyatakan minimum banyak warna yang harus disediakan.



d(L)



=7



d(SA)



=6



d(NSW) = 4 d(Q)



=4



d(NT)



=4



d(WA) = 3



36



d(V)



=3



d(T)



=1



Warna Titik



Pemberian



Pemberian



Pemberian



Pemberian



Warna Tahap 1 Warna Tahap 2 Warna Tahap 3 Warna Tahap 4 L



1



SA



2



NSW



3



Q



4



NT



3



WA



4



V



4



T



2



Jadi , bilangan kromatik pada graph G ada 4. Soal Latihan 1. Jelaskan berapa bilangan kromatik pada graph berikut.



2. Perhatikan gambar berikut.



a.



Modelkan gambar tersebut dalam graph;



37



b. tentukan bilangan kromatiknya.



3. UNNES merencanakan seminar Pendidikan Matematika bagi guru-guru SMA. Ada pembicara yang masing –masing akan tampil selama satu jam. Jika setiap pembicara tampil dalam kesempatan yang berbeda, kegiatan tersebut akan memakan waktu lama. Akan tetapi, juga tidak diharapakan pembicara-pembicara tertentu tampil pada saat yang bersamaan. Panitia seminar menghendaki agar seminar ini berlangsung tidak lebih dari 4 babak. Bagaimanakah kegiatan dijadwalkan jika pembicara-pembicara yang sebaiknya tidak tampil pada saat yang bersamaaan ditandai dengan * pada tabel berikut. Nama Pembicara A B



A



B



C



*



* *



C



D



E



F



*



*



*



*



D E



*



F



4. Warnailah peta pada gambar berikut berdasarkan algoritma pertama terbesar. a)



38



b)



---000---



39



Istilah-Istilah Lain dalam Graph (diambil dari buku Andi Hakim Nasution – Graph di SMU) 1. Lemma Jabat Tangan = Lemma Persalaman. 2. Matriks berhubungan langsung (Adjacence matrix) = matriks ikatan. 3. Matrik keterkaitan (Incidence matrix) = matriks kehadiran. 4. Graph kosong = graph nol. 5. Graph komplit = graph lengkap. 6. Graph teratur : graph yang setiap titiknya/simpulnya berderajat sama. Graph teratur berderajat r jika setiap titiknya berderajat r. Graph sirkuit : graph teratur berderajat 2.



Graph kubik: graph teratur berderajat 3.  Graph nol : graph teratur berderajat 0.  Graph lengkap (Kn) : graph teratur berderajat n-1.  Komplemen graph teratur juga graph teratur.



7. Graph bipartisi = garph bipartit. 8. Graph berbobot = grap setiap sisinya diberi bobot.



Graph bidang = suatu graph yang setiap pasangan sisinya saling berpotongan hanya pada titik ujungnya.



40



Contoh :



Graph (b) dan (c) adalah graph bidang.  Graph planar adalah suatu graph yang isomorfik dengan suatu graph bidang ( lihat gb. (1)).  Graph planar adalah suatu graph yang dapat digambar pada bidang datar sedemikian hingga sisi-sisinya tidak ada yang saling berpotongan kecuali mungkin pada titik –titik akhir dari sisi tersebut.  Graph bidang pasti graph planar , sebaliknya tidak berlaku. 9. Graph subdivisi Graph H disebut graph subdivisi dari G, jika graph H dibentuk dari G dengan cara menambah beberapa titik (bisa nol) pada beberapa sisi G. 



H1 dan H2 disebut homeomorfik dengan G jika graph H1 dan H2 merupakan graph subdivisi dari G.



10.







H1 dan H2 juga homeomorfik.







Sebuah graph homeomorfik dengan dirinya sendiri.







Graph G planar jhj subdivisi G planar.



Daerah yang dibatasi oleh sisi-sisi suatu graph disebut muka / face (F).



Graph di samping ada 4 muka/face. 41



Rumus : V(G)-E(G)+F(G)= 2 Disebut Teorema/Rumus Euler, berlaku pada graph bidang.



11. Rumus Euler tak berlaku pada graph bidang tak berhubung. Contoh: V(G)= 3,E(G)=1,F(G)=1



V(G)-E(G)+ F(G)= 3 ≠ 2 12. Graph Petersen



Yulius Peterson (1839 – 1910) Matematikawan Denmark



13. Jalan = trayek Lintasan/path = lintasan Jejak = jalur Jejak tertutup = sirkuit ( = jejak/jalur tertutup) Barisan sisi-sisi = sekuens sisi- sisi. Sirkuit dengan panjang 3 disebut segitiga. 14. Graph terhubung lawannya Graph terputus Teorema 1 Graph G = (V,E) adalah terputus jhj himpunan titik V dapat disekat jadi 2 himpunan saling menyisihkan dan tak kosong, X dan Y, sedemikian hingga tidak ada sisi yang satu titik ujung anggota X dan titik ujung yang lain anggota Y.



Teorema 2 Jika suatu graph mempunyai tepat 2 titik berderajat ganjil, maka ada lintasan yang melalui kedua titik tesebut.



42



Penghapusan sisi dan titik Graph. (1) Jika e suatu sisi pada grap G = (V,E), maka G – e adalah graph bagian G yang diperoleh dengan menghapus sisi e dari G. (2) ]ika v suatu titik pada graph G = (V,E), maka G – v adalah graph bagian G yang diperoleh dengan menghapus v dan semua sisi yang mencakup v sebagai suatu titik ujungnya. Himpunan Pemutus dan Himpunan Pemisah Misal G = (V,E) adalah graph terhubung. (1) Himpunan E1 yang merupakan himpunan bagian E, disebut himpunan pemutus graph G jhj graph bagian G1 = (V,E – E1) merupakan graph terputus (tak terhubung). (2) Himpuanan pemutus yang tidak mempunyai himpunan bagian yang merupakan himpuanan pemutus disebut himpunan pemisah Jadi : Himpunan Pemutus : Himpunan sisi- sisi Graph G yang dapat dihapus sehingga G menjadi graph terputus. Contoh : Diketahui graph G terhubung E1 = { e1, e2, e5 } E2 = { e3, e6, e7, e8 ) E3 = { e1, e2 }  E3  E1



(1) E2 himpunan pemutus G. Graph terputus diperoleh dengan cara menghapus semua sisi yang ada pada himpunan E2.



Graph terputus



43



(2) E1 bukan himpunan pemisah , sebab ada himpunan bgaian E1 yaitu E3 yang juga merupakan himpunan pemutus G. (3) Periksalah, ternyata E2 adalah himpunan pemisah G.



Catatan: Jika himpunan pemisah hanya memiliki satu sisi, maka sisi ini disebut jembatan.



Sisi e = {v, w}adalah jembatan.



{e}



Soal 1. Periksalah apakah himpunan berikut merupakan himpunan pemutus ataukah himpunan pemisah.



a) {su, sv, uv} b) {ux, uw, wx, xz} c) {yt, yz} d) {xz, xw, uw} e) {wy, wx, yz} f) {su, uv, wx, yz, vx} 2. Gambar graph Peterson. Tentukan himpunan pemisah yang mempunyai 3 dan 5 sisi. ---000---



44



POHON Definisi Pohon (tree) adalah graph terhubung tanpa sikel. Contoh:



G



Graph tak terhubung yang setiap komponennya merupakan pohon, disebut hutan (forest). Contoh: G adalah forest.



G Sifat-sifat Misalkan T = (V, E) suatu graph dengan n titik. Enam pernyataan berikut ini ekuivalen. 1. T adalah pohon. 2. T mempunyai n – 1 sisi tanpa sikel. 3. T adalah graph terhubung dan mempunyai n – 1 sisi. 4. T adalah graph terhubung dan setiap sisi merupakan jembatan. 5. Ada satu dan hanya satu lintasan yang menghubungkan dua titik pada graph T. 6. T tidak mempunyai sikel dan penambahan satu sisi menghasilkan satu sikel.



Penjelasan: Misal T adalah pohon. Maka T adalah graph terhubung tanpa sikel. Pandang, T adalah pohon dengan satu titik, maka dapat dibangun sembarang pohon dengan cara menambahkan sebuah sisi dan sebuah titik. Pada setiap tahap, jelas bahwa banyaknya titik, satu lebih banyak daripada banyaknya sisi. Jadi, setiap pohon dengan n titik mempunyai tepat (n-1) sisi.



45



Selain itu, pada setiap tahap tidak akan terbentuk suatu sikel, karena setiap sisi baru digunakan untuk menghubungkan sebuah titik lama dengan sebuah titik yang baru. Akibatnya, setiap 2 titik sembarang pada pohon dihubungkan dengan satu dan hanya satu lintasan. Dengan demikian, dua titik sembarang pada pohon dihubungkan oleh satu lintasan, yaitu sebuah sisi dengan kedua titik tadi sebagai titik ujungnya. Jika sisi ini dihapus maka tidak ada lintasan yang menghubungkan kedua titik tadi. Dengan demikian, setiap sisi pohon adalah jembatan. Akibat selanjutnya adalah penambahan sebuah sisi yang menghubungkan 2 titik sembarang pada pohon menghasilkan sebuah sikel karena 2 titik sembarang (misal u dan v) terhubungkan hanya oleh sebuah lintasan dan penambahan sebuah sisi (u, v) menghasilkan sebuah sikel yang terbentuk dari lintasan sebelumnya digabung dengan sisi (u, v).



Sebagai akibat sifat-sifat di atas adalah titik awal dan titik akhir lintasan terpanjang pada sebuah pohon selalu berderajat satu.



Teorema: Setiap pohon dengan lebih dari satu titik mempunyai paling sedikit 2 titik yang berderajat satu (titik terminal).



Pohon Pembangkit Pada suatu graph terhubung G, jika ada, kita pilih sebuah sikel dan menghapus salah satu sisinya sedemikian hingga masih diperoleh graph terhubung. Ulangilah langkah tersebut sampai diperoleh graph terhubung tanpa sikel. Jelas bahwa graph terhubung yang dihasilkan dengan proses ini merupakan pohon yang menghubungkan semua titik di graph G. Pohon ini disebut Pohon Pembangkit graph G. Beberapa pohon pembangkit bagi graph G, diperlihatkan pada gambar di bawah ini. Tampak pula bahwa banyaknya sisi yang dihapus pada graph G dengan n titik dan m sisi ada sebanyak: m – n + 1.



46



G



Pohon pembangkit dari graph G adalah sebagai berikut.



Pada praktiknya, setiap sisi graph pada umumnya memiliki bobot. Dan, kita berusaha mencari pohon pembangkit dengan jumlah bobot minimum dan disingkat dengan Pohon Pembangkit Minimum. Mencari pohon pembangkit minimum: 1. Dengan Algoritma Kruskal (Joseph B. Kruskal, 1956). 2. Dengan Algoritma Prim (Robert C. Prim, 1957).



Algoritma Kruskal Misal, bobot sisi e dilambangkan dengan w(e). Input: G = (V, E) graph terhubung dan berbobot dengan n titik dan m sisi. Sisi-sisi graph G kita nomori sedemikian hingga bobot sisi-sisinya membentuk barisan tidak turun, yaitu w(e1 )  w(e2 )  ...  w(en ) . Output: Pohon pembangkit minimum dengan n titik dan n – 1 sisi. T = (V, E’), E’  E, dan jumlah bobot sisi pada T adalah w(T) =



 w(e) min .



eE '



Langkah-langkah untuk menghasilkan T = (V, E’). A. Pemberian nilai awal: (pada awalnya pohon pembangkit T mempunyai n titik dan tanpa sisi). 1. E’   (pada mulanya himpunan sisi pohon pembangkit minimum berupa  ). 2. k  0 (pada mulanya banyaknya sisi di E’ = 0). 3. w(T)  0 (bobot awal pohon pembangkit = 0). 4. V(T)  V(G) (himpunan titik di T identik dengan himpunan titik di G).



47



B. Pemilihan sisi-sisi untuk E’ sebanyak n – 1. Ulangi 1. Pilih sisi e  E dengan w(e) terkecil. 2 E  E – {e} (sisihkan sisi e dari himpunan E). 3. Jika penambahan e pada graph T tidak menghasilkan sikel, maka: mulai kerjakan E’  E’  {e}; (tambahkan sisi e ke himpunan E’). k  k + 1; (banyaknya sisi di E’ bertambah 1). w(T)  w(T) + w(e); (bobot terakhir pohon T). selesai proses dengan jika sampai k = n – 1.



Contoh: Diketahui graph sebagai berikut.



A 6



2 8 4 6



E



8



4



7



B



5 D



9



C



Graph G.



Tentukan pohon pembangkit minimum graph G di atas. Penyelesaian: Graph G memiliki 5 titik dan 10 sisi. Dibentuk barisan tidak turun sisi-sisi berdasarkan bobotnya, AE, AC, EC, BC, BA, BE, DE, AD, DB, DC. Kita buat tabel sebagai berikut.



48



Iterasi ke



k



Himpunan E



Bobot sisi terpilih



Bobot pohon



Himpunan E’



0



O



Keterangan



0



AE,AC,EC,BC,BA,BE,DE,AD,DB,DC



1



1



AC,EC,BC,BA,BE,DE,AD,DB,DC



w(AE)=2



2



AE



2



2



EC,BC,BA,BE,DE,AD,DB,DC



w(AC)=4



6



AE,AC



3



2



BC,BA,BE,DE,AD,DB,DC



w(EC)=4



6



AE,AC



4



3



BA,BE,DE,AD,DB,DC



w(BC)=5



11



AE,AC,BC



ACEA



5



3



BE,DE,AD,DB,DC



w(BA)=6



11



AE,AC,BC



BA disisihkan, ada



6



3



DE,AD,DB,DC



w(BE)=6



11



AE,AC,BC



ACBA



EC disisihkan, ada sikel



sikel



BE disisihkan, ada sikel AEBC 7



4



AD,DB,DC



w(DE)=7



18



AE,AC,BC,DE



A



Dalam hal ini, pohon pembangkit minimumnya mempunyai himpunan sisi E’ = {AE, AC, BC, DE}, dengan jumlah bobot minimumnya sebesar: w(T) = w(AE) + w(AC) + w(BC) + w(DE) = 2 + 4 + 5 + 7 = 18.



Algoritma Prim Misal, bobot sisi e dilambangkan dengan w(e). Input: G = (V, E) graph terhubung dan berbobot dengan n titik dan m sisi. Output: Pohon pembangkit minimum dengan n titik dan n – 1 sisi. T = (V’, E’), V’ = V, E’  E, dan jumlah bobot sisi pada T adalah w(T) =



 w(e) min .



eE '



Langkah-langkah untuk menghasilkan T = (V’, E’). A. Pemberian nilai awal: (pada awalnya pohon pembangkit T mempunyai 1 titik v dan tanpa sisi). Kemudian kita lakukan: 1. E’   (pada mulanya himpunan sisi pohon pembangkit minimum berupa  ). 2. k  0 (pada mulanya banyaknya sisi di E’ = 0). 3. w(T)  0 (bobot awal pohon pembangkit = 0). 49



4. Ambil v  V dan tempatkan di V’, dicatat sebagai V’  {v} (v merupakan titik awal pada pohon pembangkit). 5. V  V – {v}; (sisihkan v dari himpunan V). B. Pemilihan titik-titik dan sisi-sisi sebanyak n – 1. Ulangi 1. Pilih sisi e  E sedemikian hingga w(e) minimum di antara bobot semua sisi berbentuk {p, q} dengan p  V’ dan q  V; titik ujung e yang terletak di V dicatat sebagai w. 2 E’  E’  {e}; (tambahkan sisi e ke E’). 3. V’  V’  {w}; (tambahkan titik w ke V’). 4. V  V – {w}; (sisihkan titik w dari V). 5. k  k + 1;



(banyaknya sisi di E’ bertambah 1).



6. w(T)  w(T) + w(e);



(bobot akhir pohon pembangkit).



Sampai k = n – 1.



C. Latihan 1. Pada Graph Bidang Terhubung, buktikan berlaku rumus Euler: V(G)-E(G)+F(G)= 2 2. Perhatikan graph berikut.



Tunjukkan contoh: a. Jalan (walk) b. Jejak tertutup c. Jejak d. Lintasan e. Sikel



50



7. Gambarlah graph Peterson. Tentukan himpunan pemisah yang mempunyai 3 dan 5 sisi.



D. Lembar Kegiatan Diketahui graph sebagai berikut.



A 6



2 8 4 6



E



8



4



7



B



5 D



9



C



Graph G.



Tentukan pohon pembangkit minimum graph G di atas dengan menggunakan Lembar Kegiatan berikut. Kerjakan dengan Algoritma Prim. Penyelesaian: Buatlah Lembar Kegiatan berikut dari kertas manila. Paparkan temuan saudara di papan tulis. Jejak algoritma ini dengan memilih titik B sebagai titik awal. Iterasi ke 1 2 3 4



Alat



k



Himpunan E’



Himpunan V



Himpunan V’



0 1 2 3 4



O BC .......... .......... ..........



.......... .......... .......... ..........



.......... .......... .......... .......... ..........







: Gunting, Penggaris, Spedol



Bahan : Kertas Manila.



E. Rangkuman 1. Sebuah Graph G adalah pasangan (V(G), E(G)) di mana: 51



Bobot sisi terpilih w(BC)=5 .......... .......... ..........



Bobot pohon 0 5 .......... .......... ..........



V(G) : Himpunan titik (berhingga, tak kosong) dan E(G) : Himpunan sisi (mungkin kosong) sedemikian sehingga setiap sisi e di dalam E(G) adalah pasangan tak berurutan dari titik-titik di V(G). 2. Pohon (tree) adalah graph terhubung tanpa sikel. 3. Misalkan T = (V, E) suatu graph dengan n titik. Enam pernyataan berikut ini ekuivalen. 1) T adalah pohon. 2) T mempunyai n – 1 sisi tanpa sikel. 3) T adalah graph terhubung dan mempunyai n – 1 sisi. 4) T adalah graph terhubung dan setiap sisi merupakan jembatan. 5) Ada satu dan hanya satu lintasan yang menghubungkan dua titik pada graph T. 6) T tidak mempunyai sikel dan penambahan satu sisi menghasilkan satu sikel.



F. Tes Formatif 1.



Diketahui Graph G:



a. Cari sebuah lintasan dari a ke n b. Cari panjang sikel terpanjang dalam G c. Berapakah panjang lintasan terpanjang? d. Cari sebuah graph bagian bukan rentang dari G. e. Cari sebuah graph bagian rentang dari G



2. Pada Graph Bidang Terhubung, buktikan berlaku rumus Euler: V(G)-E(G)+F(G)= 2



===000===



52



Bacaan Perkuliahan Heri Sutarno, dkk. 2003. Matematika Diskrit. Bandung: Jurusan Pend. Matematika FMIPA UPI – JICA. I Ketut Budayasa. 1997. Matematika Diskrit. Surabaya: University Press IKIP Surabaya John Clark dan Derek Allan Holton. 1991. A First Look at Graph Theory. Singapore: World Scientific Publishing Co. Liu, CL. 1988. Elements of Discrete Mathematics. Singapore: Mc-Graw Hill Book Co. Michael Townsend. 1987. Discrete Mathematics: Applied Combinatorics and Graph Theory. Amsterdam: The Benjamin Publishing Company. Suyitno, Amin. 2003. Hand-out Matematika Diskrit I, Semarang. FMPIA UNNES. Victor Bryant. 1995. Aspects of Combinatories – a wide-ranging introduction. Cambrid-ge: Cambridge University Press.



53



KEMENTERIAN PENDIDIKAN DAN KEBUDAYAAN UNIVERSITAS NEGERI SEMARANG (UNNES) Kantor: Gedung H lt 4 Kampus, Sekaran, Gunungpati, Semarang 50229 Rektor: (024)8508081 Fax (024)8508082, Purek I: (024) 8508001 Website: www.unnes.ac.id - E-mail: [email protected]



FORMULIR



FORMAT BUKU AJAR No. Dokumen FM-02-AKD-07



No. Revisi 00



Hal 1 dari 1



Tanggal Terbit 1 September 2017



BUKU AJAR MATA KULIAH SEMESTER



: MATEMATIKA DISKRIT : GANJIL 2019/2020



JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS NEGERI SEMARANG TAHUN 2019 54