Matematika Diskrit POLITEKNIK TELKOM BANDUNG2009 Penyusun dan Editor Adi Wijaya M.Si Dilarang menerbitkan kembali, menyebarluaskan atau menyimpan baik sebagianmaupunseluruhisibukudalambentukdandengancara apapun tanpa izin tertulis dari Politeknik Telkom. Hak cipta dilindungi undang-undang @ Politeknik Telkom 2009 Nopartofthisdocumentmaybecopied,reproduced,printed, distributed, modified, removed and amended in any form by any means without prior writtenauthorization of Telkom Polytechnic. Politeknik TelkomMatematika Diskrit Matematika Diskritiii PAGE 10 Kata Pengantar Assalamualaikum Wr. Wb SegalapujibagiAllahSWTkarenadengankarunia-Nya courseware ini dapat diselesaikan. Atas nama Politeknik Telkom, kami sangat menghargai dan ingin menyampaikanterimakasihkepadapenulis,penerjemahdan penyuntingyangtelahmemberikantenaga,pikiran,danwaktu sehingga courseware ini dapat tersusun. Takadagadingyangtakretak,diduniainitidakadayang sempurna,olehkarenaitukamiharapkanparapenggunabuku ini dapat memberikan masukan perbaikan demi pengembangan selanjutnya. Semogacoursewareinidapatmemberikanmanfaatdan membantuseluruhSivitasAkademikaPoliteknikTelkomdalam memahamidanmengikutimateriperkuliahandiPoliteknik Telkom. Amin. Wassalamualaikum Wr. Wb. Bandung,Mei 2009 Telkom PolytechnicDiscrete Mathematics ivMatematika Diskrit PAGE 10 Christanto Triwibisono Wakil Direktur I Bidang Akademik & Pengembangan Daftar Isi Kata Pengantar .................................................................................... iii Daftar Isi ............................................................................................... iv 1HIMPUNAN ................................................................................. 6 1.1Definisidan KeanggotaanSuatuHimpunan ................................ 7 1.2Operasi Himpunan ..................................................................................... 13 1.3Prinsip Dualitas ........................................................................................... 20 1.4Multi Set ......................................................................................................... 23 2RELASI DAN FUNGSI ............................................................... 33 2.1DefinisiRelasi dan Cara Penyajian ..................................................... 34 2.2Beberapa Sifat Relasi ................................................................................. 39 2.3Operasi pada Relasi ................................................................................... 44 2.4Relasi Ekivalen dan Relasi Terurut ....................................................... 48 2.5Fungsi .............................................................................................................. 53 3KOMBINATORIK ....................................................................... 69 Prinsip Dasar Menghitung ................................................................................... 70 Permutasi dan Kombinasi .................................................................................... 74 4TEORI GRAF .............................................................................. 88 4.1Definisi Graf .................................................................................................. 89 4.2Terminologi Graf ......................................................................................... 96 4.3Keterhubungan dan Sub Graf .............................................................. 106 4.4MatriksKetetanggaan(adjacencymatrix)danMatriksBersisian (incidency matrix) dari Suatu Graf ..................................................... 108 4.5Eulerian dan Hamiltonian ..................................................................... 111 4.5.2Sirkuit Hamilton ........................................................................................ 113 4.6Graf Isomorfik ............................................................................................ 115 4.7Beberapa Aplikasi Graf ........................................................................... 118 5POHON DAN PEWARNAAN GRAF ...................................... 129 Politeknik TelkomMatematika Diskrit Matematika Diskritv PAGE 10 5.1Pohon Merentang Minimum (Minimun SpanningTree) .......... 131 5.2Pohon Berakar ........................................................................................... 135 5.3Penelusuran Pohon Biner ...................................................................... 140 5.4Pewarnaan Graf ........................................................................................ 142 Pewarnaan Peta (Map Coloring) .................................................................... 145 Daftar Pustaka ........................................................................................ Telkom PolytechnicDiscrete Mathematics 6Relasi dan Fungsi PAGE 10 1HIMPUNAN Overview Dalamkehidupannyata,banyaksekalimasalahyangterkaitdengan data(objek)yangdikumpulkanberdasarkankriteriatertentu. Kumpulandatainimerupakanrepresentasidarisuatukondisi,baik secarastatistikamaupunsecaraekonomi.Kumpulandatainilahyangselanjutnyadidefinisikansebagaihimpunan.Padababawaliniakan dibahastentangdefinisidankeanggotaansuatuhimpunan, operasi himpunan dari beberapajenis himpunan. Tujuan 1.Mahasiswa memahami konsep dasar tentang himpunan. Politeknik TelkomMatematika Diskrit Relasi dan Fungsi7 PAGE 10 2.Mahasiswa memahami berbagai macam operasi dan sifat himpunan. 3.Mahasiswa dapat meyelesaikan berbagai persoalan dan fenomena yang terkait dengan teori himpunan. 1.1Definisidan KeanggotaanSuatuHimpunan Himpunan(set)merupakansekumpulanobjek-objekyang berbedayangdapatdidefinisikandenganjelas.Objekdidalamhimpunandinamakanunsuratauanggotahimpunan.Keanggotaan suatu himpunan dinyatakan oleh notasie. Contoh 1 : A = {x, y, z} x e A : x merupakan anggota himpunan A. w e A : w bukan merupakan anggota himpunan A. Ada beberapa cara dalam menyatakan himpunan, yaitu: a. Mencacahkan anggotanya (enumerasi) Dengancaraini,himpunantersebutdinyatakandenganmenyebutkan semuaanggotahimpunannya di dalam suatu kurung kurawal. Contoh 2 :-Himpunan empat bilangan ganjil pertama: A = {1, 3, 5, 7}. -Himpunan lima bilangan prima pertama: B = {2, 3,5, 7, 11}.-Himpunanbilanganasliyangkurangdari50:C={1, 2, ..., 50}-Himpunan bilangan bulat ditulis sebagai {, -2, -1, 0, 1, 2, }.b. Menggunakan simbol standar (baku) Suatuhimpunandapatdinyatakandalamsuatusimbolstandar (baku) yang telah diketahui secara umum oleh masyarakat (ilmiah). Contoh 3 : Telkom PolytechnicDiscrete Mathematics 8Relasi dan Fungsi PAGE 10 N =himpunan bilangan alami (natural)={ 1, 2, ... } Z =himpunan bilangan bulat={ ..., -2, -1, 0, 1, 2, ... } Q =himpunan bilangan rasional R =himpunan bilangan riil C =himpunan bilangan kompleks Himpunanyanguniversal(semestapembicaraan)dinotasikan dengan U.Contoh 4 : MisalkanU={1,2,3,4,5}danA={1,3,5}merupakan himpunan bagian dari U. 3.Menuliskan kriteria (syarat) keanggotaan himpunan Suatuhimpunandapatdinyatakandengancaramenuliskan kriteria(syarat)keanggotaanhimpunantersebut.Himpunanini dinotasinya sebagai berikut : { x ( syarat yang harus dipenuhi oleh x } Contoh 5 :(i)A adalah himpunan bilangan asliyang kecil dari 10 A = { x | xs 10 danx e N }atauA = { x e N | xs 10 } yang ekivalen dengan : A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} (ii)M={x|xadalahmahasiswayangmengambilkuliah matematika diskrit}atau Politeknik TelkomMatematika Diskrit Relasi dan Fungsi9 PAGE 10 M={xadalahmahasiswa|iamengambilkuliah matematika diskrit} 4.Menggunakan Diagram Venn Suatuhimpunandapatdinyatakandengancaramenuliskan anggotanyadalamsuatugambar(diagram)yangdinamakan diagram venn. Contoh6 : Misalkan U = {1, 2, , 7, 8}, A = {1, 2, 3, 5} dan B = {2, 5, 6, 8}. Diagram Venn: U1253 6847A B Terkaitdenganmasalahkeanggotaan,suatuhimpunandapat dinyatakan sebagai anggota himpunan lain.

Contoh 7 : a.Misalkan,M= { mahasiswa Politeknik Telkom } M1 = { mahasiswa prodi komputer akuntansi} M2 = { mahasiswa prodi Sistem Informasi} Dengan demikian, M = { M1, M2 } b. Bila P1 = {x, y}, P2 = { {x, y} }atau P2={P1}, Sementara itu, P3 = {{{x, y}}}, makax e P1dany e P2, sehinggaP1e P2 , sedangkanP1e P3,tetapiP2e P3 Telkom PolytechnicDiscrete Mathematics 10Relasi dan Fungsi PAGE 10 Jumlahunsurdalamsuatuhimpunandinamakankardinalitasdari himpunan tersebut. Misalkan, untuk menyatakan kardinalitas himpunan A ditulis dengannotasi:n(A)atau A Contoh 8 : (i) B = { x | x merupakan bilangan prima yang lebih kecil dari 10 },atau B = {2, 3, 5, 7 } maka |B| = 4(ii)A = {a, {a}, {{a}} }, maka |A| = 3 Jikasuatuhimpunantidakmempunyaianggota,dengankatalain dengankardinalitashimpunantersebutsamadengannolmakahimpunan tersebut dinamakan himpunan kosong (null set). Notasi dari suatu himpunan kosong adalah : C atau {} Contoh 9 : (i)P={MahasiswaTeknikIndustriSTTTelkomyangpernahke Mars}, maka n(P) = 0 Jadi P = C (ii) A = {x | akar persamaan kuadrat x2 + 1 = 0 danx e R}, makan(A) = 0 JadiA = {} (iii) B = {{ }} dapat juga ditulis sebagai B = {C}. JadiBbukanhimpunankosongkarenaiamemuatsatu unsur yaitu himpunan kosong. Himpunan A dikatakan himpunan bagian (subset) dari himpunan B jika dan hanya jika setiap unsur A merupakan unsur dari B. Dalam hal ini, B dikatakan superset dari A. Notasi himpunan bagian: A_ B atauAc BJikadigambarkandalambentukdiagramVennhimpunanbagian tersebut menjadi : Politeknik TelkomMatematika Diskrit Relasi dan Fungsi11 PAGE 10 UAB Contoh 10 : (i)N _ Z _ R _ C(ii) {2, 3, 5} _ {2, 3, 5} Untuk setiaphimpunan Aberlaku hal-hal sebagai berikut: (a) A adalah himpunan bagian dari A itu sendiri (yaitu, A _ A). (b) Himpunan kosong merupakan himpunan bagian dari A ( C _ A). (c) Jika A _ B dan B _ C, maka A _ C C_AdanA_A,makaCdanAdisebuthimpunanbagiantak sebenarnya(impropersubset)darihimpunanA.PernyataanA_B berbeda dengan AcB : A c B : A adalah himpunan bagian dari B tetapi A = B. Yangdemikian,Amerupakanhimpunanbagiansebenarnya(proper subset) dari B. Contoh 11 :Misalkan A = {1, 2, 3}. {1} dan {2, 3} merupakan proper subset dari A. Himpunankuasa(powerset)darihimpunanAmerupakansuatu himpunanyangunsur-unsurnyamerupakansemuahimpunanbagian dari A, termasuk himpunan kosong dan himpunan A sendiri. Himpunan kuasadinotasikanolehP(A).Jumlahanggota(kardinal)darisuatu Telkom PolytechnicDiscrete Mathematics 12Relasi dan Fungsi PAGE 10 himpunankuasabergantungpadakardinalhimpunanasal.Misalkan, kardinalitas himpunan A adalah m, maka |P(A)| = 2m. Contoh 12 :Jika A = { x, y }, maka P(A) = { C, { x }, { y }, { x, y }}

Contoh 13 : HimpunankuasadarihimpunankosongadalahP(C)={C}, sementaraituhimpunankuasadarihimpunan{C}adalah P({C}) = {C, {C}}.

PernyataanA_BdigunakanuntukmenyatakanbahwaAadalahhimpunan bagian (subset) dari B yang memungkinkan A = B. Dua buah himpunan dikatakan sama jika memenuhi kondisi berikut : A=BjikadanhanyajikasetiapunsurAmerupakanunsurBdan sebaliknya setiap unsur B merupakan unsur A.UntukmenyatakanA=B,yangperludibuktikanadalahAadalah himpunanbagiandariBdanBmerupakanhimpunanbagiandariA. Jika tidak demikian, maka A = B. atau A = B A _ BdanB _ A Contoh 14 : (i) Jika A = { 0, 1 } dan B = { x | x (x 1) = 0 },maka A = B (ii)Jika A = { 3, 5, 8, 5 } dan B = {5, 3, 8 },maka A = B (iii) Jika A = { 3, 5, 8, 5 } dan B = {3, 8}, maka A = B Untuk tiga buah himpunan, A, B, dan Cberlaku aksioma berikut: (a)A = A, B = B, dan C = C(b) Jika A = B, maka B = A (c) Jika A = B dan B = C, maka A = C Politeknik TelkomMatematika Diskrit Relasi dan Fungsi13 PAGE 10 Duabuahhimpunandikatakanekivalenjikamasing-masing mempunyaikardinalitasyangsama.Misalkan,himpunanAadalahekivalendenganhimpunan B berarti kardinal darihimpunanAdanhimpunanBadalahsama,notasiyangdigunakan adalah : A~B Contoh 15 : Misalkan A = { 2, 3, 5, 7 } dan B = { a, b, c, d },maka A ~ B sebab |A| = |B| = 4 DuahimpunanAdanBdikatakansalinglepas(disjoint)jikakeduanya tidak memiliki unsur yang sama. Notasi yang digunakan adalahA // B .Jika dinyatakan dalam bentuk diagram Venn adalah sebagai berikut : UAB Contoh 16 : Jika A = { x | x e N, x < 10 } dan B = { 11, 12, 13, 14, 15 },maka A // B. 1.2Operasi Himpunan Adabeberapaoperasihimpunanyangperludiketahui,yaitu: irisan, gabungan, komplemen, selisih dan beda setangkup. a. Irisan (intersection) Irisan antara dua buah himpunan dinotasikan oleh tanda . Misalkan A dan B adalah himpunan yang tidak saling lepas, makaTelkom PolytechnicDiscrete Mathematics 14Relasi dan Fungsi PAGE 10 A B = { x , x e A dan x e B } Jika dinyatakan dalam bentuk diagram Venn adalah : Contoh 17 : 1.MisalkanA = {2, 3, 5, 7, 11} danB = {3, 6, 9, 12},maka A B = {3} 2.MisalkanA adalah himpunan mahasiswi TI STT Telkom danB merupakan himpunan wanita lanjut usia (50 tahun ke atas)maka A B = C. Hal ini berarti A dan B adalah saling lepas atauA // B. b.Gabungan (union) Gabungan antara dua buah himpunan dinotasikan oleh tanda . Misalkan A dan B adalah himpunan, makaAB = { x , x e A atau x e B } Jika dinyatakan dalam bentuk diagram Venn adalah :Politeknik TelkomMatematika Diskrit Relasi dan Fungsi15 PAGE 10 Contoh 18 :(i)Jika A = { 2, 3, 5, 7} dan B = { 1, 2, 3, 4, 5 }, maka A B = {1,2,3, 4, 5, 7} (ii) AC = A c.Komplemen (complement) Komplemendarisuatuhimpunanmerupakanunsur-unsuryangadapadahimpunanuniversal(semestapembicaraan)kecualianggotahimpunantersebut.MisalkanAmerupakan himpunanyangberadapadasemestapembicaraanU,maka komplemen dari himpunan A dinotasikan oleh: A= Ac = { x , x e Udanx e A } Jika dinyatakan dalam bentuk diagram Venn adalah : Contoh 19 : Misalkan U = { 1, 2, 3, ..., 9 }, jika A = {1, 3, 7, 9}, maka A = {2, 4, 5, 6, 8} jika A = { x e U | x habis dibagi dua }, maka A= { 1, 3, 5, 7, 9 } Contoh 20 : A = himpunan mahasiswa PoliteknikTelkom B = himpunan mahasiswa yang tinggal di Asrama C = himpunan mahasiswa Sistem Informasi D =himpunanmahasiswayangmengambilmatematika diskrit Telkom PolytechnicDiscrete Mathematics 16Relasi dan Fungsi PAGE 10 E = himpunan mahasiswa yang membawa motor untuk pergi ke kampusa. PernyataanSemuamahasiswaPoliteknikTelkomJurusanSistem Informasiyangmembawamotoruntukpergike kampusdapatdinyatakandalamnotasioperasihimpunansebagai berikut: (A C) E b. PernyataanSemuamahasiswaPoliteknikTelkomyangtinggaldi asrama dan tidak mengambil matematika diskritdapatdinyatakandalamnotasioperasihimpunansebagai berikut: D B A c. PernyataansemuamahasiswaJurusanSisteminformasiyang tidaktinggaldiasramaatautidakmembawamotor untuk pergike kampusdapatdinyatakandalamnotasioperasihimpunansebagai berikut: E B C d. Selisih (difference) Selisihantara dua buah himpunan dinotasikan oleh tanda . MisalkanAdanBadalahhimpunan,makaselisihAdanB dinotasikan olehPoliteknik TelkomMatematika Diskrit Relasi dan Fungsi17 PAGE 10 A B = { x , x e A dan x e B } = B A Contoh 21 : Jika A = { 1, 2, 3, ..., 10 } dan B = { 2, 3, 5, 7}, maka A B = { 1, 4, 6, 8, 9 } danB A = C e.Beda Setangkup (Symmetric Difference) Bedasetangkup antara dua buah himpunan dinotasikan oleh tanda . Misalkan A dan B adalah himpunan, maka beda setangkup antara A dan B dinotasikan oleh: A B = (AB) (A B)= (A B)(B A) Jika dinyatakan dalam bentuk diagram Venn adalah : Contoh 22 : Jika A = { 2, 3, 5, 7} danB = { 1, 2, 3, 4,5 },makaA B = { 1, 4, 7 } Beda setangkup memenuhi sifat-sifat berikut: Telkom PolytechnicDiscrete Mathematics 18Relasi dan Fungsi PAGE 10 (a) A B = B A (hukum komutatif) (b) (A B ) C = A (B C )(hukum asosiatif) f.Perkalian Kartesian (cartesian product) Perkaliankartesianantaraduabuahhimpunandinotasikanoleh tanda . Misalkan A dan B adalah himpunan, maka perkalian kartesian antara A dan B dinotasikanoleh: A B = {(a, b) | a e A dan b e B } Contoh 23 : (i)Misalkan C = {1, 2, 3}, dan D = { a, b }, maka C D = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) } (ii) Misalkan A = B = himpunan semua bilangan riil, maka A B = himpunan semua titik di bidang datar Misalkanadaduahimpunandengankardinalitasberhingga,maka kardinalitashimpunanhasildarisuatuperkalian kartesian antara duahimpunantersebutadalahperkalianantarakardinalitasmasing-masinghimpunan.Dengandemikian,jikaAdanB merupakan himpunan berhingga, maka: |A B| = |A| . |B|. Pasangan terurut(a, b) berbeda dengan (b, a), dengan kata lain (a, b)=(b,a).Denganargumeniniberartiperkaliankartesiantidak komutatif, yaituA B = B A dimana A atau Bbukan himpunan kosong. Jika A = C atau B = C,makaA B = B A =C Politeknik TelkomMatematika Diskrit Relasi dan Fungsi19 PAGE 10 Hukum-hukumyangberlakuuntukoperasihimpunanadalahsebagai berikut : 1.Hukum identitas: AC = A A U = A 2. Hukum null/dominasi: A C = C AU = U 3.Hukum komplemen: AA = U A A = C 4.Hukum idempoten: AA = A A A = A 5.Hukum involusi: ) ( A = A 6.Hukum penyerapan (absorpsi): A(A B) = A A (AB) = A 7.Hukum komutatif: AB = BA A B = B A 8.Hukum asosiatif: A(BC) = (AB)C A (B C) = (A B) C 9. Hukum distributif: A(B C) = (AB) (AC) A (BC) = (A B)(A C) 10.Hukum De Morgan: B A = B A B A = B A Telkom PolytechnicDiscrete Mathematics 20Relasi dan Fungsi PAGE 10 11. Hukum komplemen U = C U = C Misalkan A dan B adalah himpunan berhingga, maka n(AB) = n(A) + n(B) n(AB) Inimerupakanprinsipinklusi-eksklusiyangbergunadalam penyelesaian himpunan maupun kombinatorial. Iniberlakujugauntuktigahimpunanberhinggadanseterusnya. MisalkanA,B,danCmerupakanhimpunanberhinggamaka berdasarkanprinsipinklusi-eksklusi,hubunganantarkardinalitasdari partisi himpunan tersebut dapat ditulis dalam bentuk : |ABC| = |A| + |B| + |C| |AB| |BC| |AC| +|ABC| Prinsip inklusi-eksklusi akan dibahas lagi pada bab kombinatorik. 1.3Prinsip Dualitas Prinsipdualitasmengemukakanbahwaduakonsepyangberbeda dapat dipertukarkan namun tetap memberikan jawaban yang benar. Contoh 24 : AS kemudi mobil di kiri depan Indonesia kemudi mobil di kanan depanPeraturan: (a) di Amerika Serikat, mobil harus berjalan di bagian kanan jalan, pada jalan yang berlajur banyak, lajur kiri untuk mendahului, bila lampu merah menyala, mobil belok kanan boleh langsung (b) di Indonesia, mobil harus berjalan di bagian kiri jalan, pada jalur yang berlajur banyak, lajur kanan untuk mendahului, bila lampu merah menyala, mobil belok kiri boleh langsung Prinsip dualitas pada kasus diatas adalah: Politeknik TelkomMatematika Diskrit Relasi dan Fungsi21 PAGE 10 Konsepkiridankanandapatdipertukarkanpadakeduanegara tersebutsehinggaperaturanyangberlakudiAmerikaSerikatmenjadi berlaku pula di Inggris. (PrinsipDualitaspadaHimpunan).MisalkanSadalahsuatukesamaan (identity) yang melibatkan himpunan dan operasi-operasi seperti , , dan komplemen. Jika S* merupakan kesamaan yang berupa dual dari S maka dengan mengganti , ,C U, U C, sedangkan komplemendibiarkansepertisemula,makaoperasi-operasitersebut pada kesamaan S* juga benar. Tabel 1.1Dualitas dari Hukum Aljabar Himpunan 1. Hukum identitas: AC = A Dualnya: A U= A 2. Hukum null/dominasi: A C = C Dualnya: AU = U 3. Hukum komplemen : AA = U Dualnya: A A= C 4. Hukum idempoten : AA = A Dualnya: A A = A 5.Hukum penyerapan : A(A B) = A Dualnya: A (AB) = A 6.Hukum komutatif : AB = BA Dualnya: A B = B A 7.Hukum asosiatif : A(BC) = (AB)C Dualnya: A (B C) = (A B) C Telkom PolytechnicDiscrete Mathematics 22Relasi dan Fungsi PAGE 10 8.Hukum distributif : A(B C)=(AB) (AC) Dualnya: A (BC) = (A B)(A C) 9.Hukum De Morgan: B A B A = Dualnya: B A B A= 10.Hukum 0/1U = C Dualnya: U = C Contoh 25 : Misalkan A e U dimana A =( ) ( ) B A B A maka pada dualnya, misalkanU*, berlaku : A= ( ) ( ) B A B A Dalammembuktikankebenaransuatupernyataanatau merepresentasikansuatupernyataandengancaralaindenganmenggunakanbantuan himpunan ada beberapa cara, antara lain : a. Pembuktian dengan menggunakan diagram Venn Contoh 26 : Misalkan A, B, dan C adalah himpunan.Tunjukan bahwa A (BC) = (A B)(A C)dengan diagram Venn. Jawab : Carainidilakukanbukandalampembuktianformal, denganmenggambarkansejumlahhimpunanyangdiketahuidan mengarsirsetiapoperasiyangdiinginkansecarabertahap, sehingga diperoleh himpunan hasil operasi secara keseluruhan. Politeknik TelkomMatematika Diskrit Relasi dan Fungsi23 PAGE 10 A (BC)(A B)(A C) Kedua digaram Venn memberikan area arsiran yang sama.Terbukti bahwa A (BC) = (A B)(A C).b.Beberapacontohdalammembuktikanpernyataandengan menggunakan aljabarhimpunan. Contoh 27 : Misalkan A dan B himpunan.Tunjukan bahwa : A(B A) = AB Jawab : A(B A)= A(B A)(Definisioperasi selisih) = (AB) (A A )(Hukum distributif) = (AB) U(Hukum komplemen) = AB (Hukumidentitas)

Contoh 28 : Tunjukan bahwa untuk sembarang himpunan A dan B, berlaku (i) ( ) B A A = ABdan (ii)A ( AB) = A B Jawab : (i)( ) B A A =( ) ( ) B A A A(H. distributif) =U (AB)(H. komplemen) =AB(H. identitas) (ii) adalah dual dari (i)( ) B A A =( ) ( ) B A A A (H. distributif) = C(A B)(H. komplemen) =A B(H. identitas) 1.4Multi SetHimpunanyangunsurnyabolehberulang(tidakharusberbeda) disebut multi set (himpunan ganda).Telkom PolytechnicDiscrete Mathematics 24Relasi dan Fungsi PAGE 10 Contoh 29 : A ={1, 1, 1, 2, 2, 3},B ={2, 2, 2},C ={2, 3, 4},D ={ }.Multiplisitassuatuunsurpadamultisetadalahjumlah kemunculan unsur tersebut pada multi set. Contoh 30 :M = { 1, 1, 1, 2, 2, 2, 3, 3, 1 },multiplisitas1adalah4danmultiplisitas2adalah3,sementaraitumultiplisitas3 adalah 2. Himpunan (set)merupakan contoh khusus dari suatumultiset, yangdalamhalinimultiplisitasdarisetiapunsurnyaadalah0atau1. Himpunanyangmultiplisitasdariunsurnya0adalahhimpunan kosong. Politeknik TelkomMatematika Diskrit Relasi dan Fungsi25 PAGE 10 MisalkanPdanQadalahmultiset,operasiyangberlakupadadua buah multi set tersebut adalah sebagai berikut : a.PQmerupakansuatumultisetyangmultiplisitasunsurnyasama dengan multiplisitasmaksimum unsur tersebut pada himpunan P dan Q. Contoh 31 :P = { a, a, a, c, d, d } dan Q ={ a, a, b, c, c }, makaPQ = { a, a, a, b,c, c, d, d } b.PQadalahsuatumultisetyangmultiplisitasunsurnyasama denganmultiplisitasminimumunsurtersebutpadahimpunanP dan Q. Contoh 32 :P = { a, a, a, c, d, d } dan Q = { a, a, b, c, c } maka P Q = { a, a, c } c. P Qadalahsuatu multisetyangmultiplisitasunsurnya sama denganmultiplisitasunsurtersebutpadaPdikurangi multiplisitasnyapadaQ,iniberlakujikajikaselisihmultiplisitas tersebutadalahpositif.Jikaselisihnyanolataunegatifmaka multiplisitas unsur tersebut adalah nol. Contoh 33 :P = { a, a, a, b, b, c, d, d, e } danQ = { a, a, b, b, b, c, c, d, d, f } makaP Q= { a, e } d.P + Q, yang didefinisikan sebagai jumlah (sum) dua buah himpunan ganda,adalahsuatumultisetyangmultiplisitasunsurnyasama denganpenjumlahandarimultiplisitasunsurtersebutpadaPdan Q. Contoh 34 :P = { a, a, b, c, c } dan Q = { a, b, b, d }, maka P + Q = { a, a, a, b, b, b, c, c, d } Telkom PolytechnicDiscrete Mathematics 26Relasi dan Fungsi PAGE 10 Rangkuman 1.Himpunan(set)merupakansekumpulanobjek-objekyang berbeda yang dapat didefinisikandenganjelas. 2.Himpunandapatdinyatakandenganmencacahanggotanya, menggunakansimbol,syaratkeanggotaan,ataumenggunakan diagram venn.3.JumlahunsurdalamsuatuhimpunanAdinamakankardinalitas himpunan A,notasi: n(A)atau A4.Jikasuatuhimpunantidakmempunyaianggota,dengankatalain dengankardinalitashimpunantersebutsamadengannolmakahimpunan tersebut dinamakan himpunan kosong (null set), Notasi : C atau { }. 5.Beberapaoperasipadahimpunanyangperludiketahuia.l:irisan, gabungan, komplemen, selisih, dan beda setangkup.6.MisalkanAdanBadalahhimpunanberhingga,makaPrinsip Inklusi-Eksklusi untuk dua himpunan ditulis :n(AB) = n(A) + n(B) n(AB) 7.Himpunanyangunsurnyabolehberulang(tidakharusberbeda) disebut multi set (himpunan ganda).Politeknik TelkomMatematika Diskrit Relasi dan Fungsi27 PAGE 10 8.Multiplisitassuatuunsurpadamultisetadalahjumlah kemunculan unsur tersebut pada multi set tersebut. Kuis Benar Salah (Untuk soal no 1 5) DiketahuiA = {2, 3, 5, 7},B = {2, 4, 6, 8, 10},dan C = {1, 3, 5, 7} 1.C A B A = 2. B A_ 3.B B merupakan himpunan bilangan asli 4. C B A A _ 5.C B A C B A =6.Himpunan kosong adalah himpunan yang hanya terdiri dari satu anggota yaitu nol.7.Jika (A B) = {1, 2, 3}dan (B A) = {4, 5}maka AB = {1, 2, 3, 4, 5} Telkom PolytechnicDiscrete Mathematics 28Relasi dan Fungsi PAGE 10 8.Jika PQ = R maka(R Q) = P 9.Komplemen dari himpunan bilangan asli adalah bilangan negatif. 10.Jika a e Adan b e B makaA B = C Pilihan Ganda 1.Himpunan yang unsurnya boleh berulang dinamakanA.Himpunan berganda D.Fuzzy set B.Multi setE.Data set C.Frekuensi set 2.Jika C = { x , x e A atau x e B }makaC = ..... A.A BD.A B B.A BE.A (BA) Politeknik TelkomMatematika Diskrit Relasi dan Fungsi29 PAGE 10 C.AB 3.Operasi himpunan A B, setara dengan .... A.A BD.(A B) (AB) B.(A B) BE.(A B)(B A) C.(A B) (B A) 4.Hukum DMorgan pada himpunan dinyatakan oleh : A.AB = BAD.AU = U B.A(BC) = (AB)CE.C(A B) C. B A B A = 5.Frekuensi kemunculan suatu unsur pada multi set disebut . A.KardinalitasD.Mutiplisitas B.MultiplikasiE.Aditivitas C.Frekuensi 6P ={ x , x e A dan x e B }makaP = ..... A.A BD.A B B.A BE.A (BA) C.AB 7Operasi himpunan (A B)(A B)(B A) menghasilkanAHimpunan ADHimpunan B ABHimpunan BEHimpunan AB CHimpunan A B 8Jika U adalah universal set dari A dan B, maka(AU) = .... A(B A)cD(A B)c B(A B)cEBc C(AB)c 9Ada10mahasiswayangambilmatdis,15mahasiswaambil manajemen dan 6 mahasiswa ambil kedua mata kuliah itu. Jika total Telkom PolytechnicDiscrete Mathematics 30Relasi dan Fungsi PAGE 10 mahasiswaadalah30orang,makajumlahmahasiswayangtidak ambil kedua mata kuliah itu ada...A9 mahasiswaD12 mahasiswa B10 mahasiswaE13 mahasiswa C11 mahasiswa 10Misalkan P = {1, 2, 3, 4, 5} dan Q = {a, b, c}maka n (A X B) = .... A5D15 B3E8 C2 Latihan (Untuk soal no. 1 5) Diketahui A = {1,2, 3, 4, 5, 6, 7},B = {1, 2, 3, 5, 6, 12}, danC = {2, 4, 8, 12, 20} Tentukan hasil dari opreasi himpunan berikut : 1.(A B) CPoliteknik TelkomMatematika Diskrit Relasi dan Fungsi31 PAGE 10 2.(A B)(B C)3.(A B) (B C)4.(AC) (BC) 5.(AB) C (AC) B6.TentukanJumlah(banyaknya)bilanganpadahimpunanAyang tidak habis dibagi 3 atau 5 ! 7.TentukanJumlah(banyaknya)bilanganpadahimpunanAyang habis dibagi 3, tetapi tidak habis dibagi 5 ! 8.TentukanJumlah(banyaknya)bilanganpadahimpunanAyang habis dibagi 3, tetapi tidak habis dibagi 5 maupun 7 ! 9.Misalkan, jumlah mahasiswa pada suatukelasadalah60 orang. 20 orangmahasiswamenyukaikalkulus,30menyukaimatematika diskrit,dan10orangmenyukaialjabarlinear.7orangmenyukai kalkulusdanmatematikadiskrit,5orangmenyukaimatematika diskritdan aljabar linear, dan 10 orang tidak menyukai ketiga mata kuliah itu. a.Tentukan jumlah mahasiswa yang menyukai ketiga mata kuliah tersebut ! b.Tentukanjumlahmahasiswayanghanyamenyukaisatumata kuliah ! (Untuk soal no 10 15) Darihasilsurveypada60orangmahasiswa,diperolehdatasebagai berikut : 25 mahasiswa suka membaca kompas 26 mahasiswa suka membaca Republika 27 mahasiswa suka membaca Pikiran Rakyat 9 mahasiswa suka membaca kompas dan Republika 11 mahasiswa suka membaca kompas danPikiran Rakyat 8 mahasiswa suka membaca Republika dan Pikiran Rakyat 3 mahasiwa suka membaca ketiga koran tersebut 10.Gambarkan diagram ven untuk masalah tersebut ! 11.Tentukanjumlahmahasiswayangtidakpernahbacasatupun ketiga koran tersebut ! Telkom PolytechnicDiscrete Mathematics 32Relasi dan Fungsi PAGE 10 12.Tentukan jumlah mahasiswa yang hanya baca Pikiran Rayat saja ! 13.Tentukanjumlahorangyangtepathanyamembacasatujenis koran saja ! Politeknik TelkomMatematika Diskrit Relasi dan Fungsi33 PAGE 10 2RELASI DAN FUNGSI Overview Hubunganantarelemen/unsurdalamhimpunanterjadidalam berbagaimasalah.Hubunganinidirepresentasikanmenggunakan strukturyangdinamakanrelasi.Relasidapatdigunakanuntuk menyelesaikan berbagai masalah seperti optimasijaringan komunikasi, penjadwalan, permasalahan dalam database. Tujuan Telkom PolytechnicDiscrete Mathematics 34Relasi dan Fungsi PAGE 10 1.Mahasiswa memahami konsep relasi dan fungsi. 2.Mahasiswa memahami berbagai macam operasi dan sifat relasi. 3.Mahasiswa dapat meyelesaikan berbagai persoalan dan fenomena yang terkait denganrelasi dan fungsi. 2.1DefinisiRelasi dan Cara Penyajian Pada bab sebelumnya, telah dibahas tentang Cartesian product, yaituberupapasanganterurutyangmenyatakanhubungandaridua himpunan.Semuapasanganterurutmerupakananggotadari himpunanbagiandarihasilCartesianproductduabuahhimpunan. Sebagiandarianggotahimpunanbagiantersebutmempunyai hubungan yang khusus (tertentu) antar dua unsur pada pasangan urut tersebut,menurutaturantertentu.Aturanyangmenghubungkan antara dua himpunan dinamakan relasi biner.Relasiantara himpunan A dan himpunan B merupakan himpunan yang berisi pasangan terurut yang mengikuti aturan tertentu.Jadi, relasi biner R antara himpunan A dan B merupakan himpunan bagian dari cartesian product A BatauR _ (A B). NotasidarisuaturelasibineradalahaRbatau(a,b)eR.Ini berartibahwaadihubungankandenganbolehR.Suatuunsurdalam cartesianproductyangbukanmerupakanunsurrelasidapata dinyatakandenganaRbatau(a,b)eR,yangartinyaatidak dihubungkanolehbolehrelasi R. Himpunan A disebut daerahasal (domain) dari R, dan himpunan B disebut daerah hasil (range) dari R. Contoh 2.1 : Misalkan A = {2, 3, 4} danB = {2, 4, 8, 9, 15}.Jika kita definisikan relasi R dari A ke B dengan aturan : (a, b) e Rjika a faktor prima dari b Tentukan unsur-unsur R! Jawab : Politeknik TelkomMatematika Diskrit Relasi dan Fungsi35 PAGE 10 Sepertiyangtelahdipelajarisebelumnya,cartesianproductAB adalah : A B = {(2, 2), (2, 4), (2, 8), (2, 9), (2, 15), (3, 2), (3, 4), (3, 8), (3, 9), (3, 15), (4, 2), (4, 4), (4, 8), (4, 9), (4, 15)} Denganmenggunakandefinisirelasidiatas,relasiRdariAkeB yangmengikuti aturan tersebut adalah : R= {(2, 2), (2, 4), (2, 8), (3, 9), (3, 15) }

Relasidapatpulaterjadihanyapadasebuahhimpunan,yaiturelasi padaA.RelasipadahimpunanAmerupakanhimpunanbagiandari cartesian product A A. Telkom PolytechnicDiscrete Mathematics 36Relasi dan Fungsi PAGE 10 Contoh 2.2 : MisalkanRadalahrelasipadaA={2,3,4,8,9}yang didefinisikan oleh (x, y)e Rjika danhanya jika x habis dibagi olehy.Jawab : Relasi R padaAyang mengikuti aturan tersebut adalah : R={(2,2),(4,4),(4,2),(8,8),(8,2),(8,4),(3,3),(9,9),(9,3)}

Caramenyatakansuaturelasibisabermacam-macam,antaralain: dengandiagrampanah,tabel,matriks,bahkandengangraph berarah.Berikutini,akandibahassatu-persatucaramenyajikankan suatu relasi dengan cara-cara tersebut. Cara menyajikan suatu relasi : a.Penyajian Relasi dengan Diagram Panah Misalkan A = {2, 3, 4} danB = {2, 4, 8, 9, 15}.Jika kita definisikan relasi R dari A ke B dengan aturan : (a, b) e Rjika a faktor prima dari b makarelasitersebutdapatdigambarkandengandiagrampanah berikut ini : b.Penyajian Relasi berupa PasanganTerurut 2 - 3 - 4 - - 2 - 4 - 8 - 9 - 15 Politeknik TelkomMatematika Diskrit Relasi dan Fungsi37 PAGE 10 Contohrelasipada(a)dapatdinyatakandalambentukpasangan terurut, yaitu : R = {(2, 2), (2, 4), (2, 8), (3, 9), (3, 15)} c.Penyajian Relasi dengan Tabel Kolompertamatabelmenyatakandaerahasal,sedangkankolom keduamenyatakandaerahhasil.Relasiyangtelahdijelaskanpada bagian (a) dapat direpresentasikan sebagai berikut: Tabel 2.1 Relasi Faktor Prima Dari AB 22 24 28 39 315 d.Penyajian Relasi dengan Matriks Misalkan Rmerupakan relasi yangmenghubungkanhimpunan A = {a1,a2,,am}danhimpunanB={b1,b2,,bn}.Relasitersebut dapat disajikan dalam bentuk matriks yaitu : b1 b2 .bn

M = (((((

mn m mnnmm m mm m mm m maaa 2 12 22 211 12 1121 Unsur-unsur mijpada matriks itu bernilai satu atau nol, tergantung apakahunsuraipadahimpunanAmempunyairelasidenganunsurbjpadahimpunanB.Pernyataantersebutdapatdituliskan dalam bentuk : ee=R b aR b amj ij iij) , ( , 0) , ( , 1

Telkom PolytechnicDiscrete Mathematics 38Relasi dan Fungsi PAGE 10 Contoh 2.3 : Misalkan A = {2, 3, 4} danB = {2, 4, 8, 9, 15}.Jika kita definisikan relasi R dari A ke B dengan aturan : (a, b) e Rjika a faktor prima dari b makarelasitersebutdapatdisajikandalambentukmatriks yaitu : ((((

=0100 0 0 01 0 0 00 1 1 1M e.Penyajian Relasi dengan Graf Berarah Relasipadasebuahhimpunandapatdisajikankansecaragrafis dengangrafberarah(directedgraphataudigraph).Grafberarah didefinisikanhanyauntukmerepresentasikanrelasipadasuatu himpunan(bukanantaraduahimpunan).Tiapunsurhimpunan dinyatakandengansebuahtitik(disebutjugasimpulatauvertex), dantiappasanganterurutdinyatakandenganbusur(arc).Jika(a, b) e R, maka sebuah busur dibuat dari simpul a ke simpul b. Simpul adisebutsimpulasal(initialvertex)dansimpulbdisebutsimpul tujuan (terminal vertex).Pasangan terurut (a, a) dinyatakan dengan busur dari simpul a ke simpul a sendiri. Busur semacam itu disebut loop. Contoh 2.4 :Misalkan R = {(a, b), (b, c), (b, d), (c, c) (c, a), (c, d), (d, b)} adalahrelasi pada himpunan {a, b, c, d}.Relasi R dapat di sajikan dalam bentuk graf berarah yaitu : a b cd Politeknik TelkomMatematika Diskrit Relasi dan Fungsi39 PAGE 10 2.2Beberapa Sifat Relasi Relasiyangdidefinisikanpadasebuahhimpunanmempunyai beberapa sifat.Sifat-sifat tersebut antara lain : 1.Refleksif (reflexive) SuaturelasiRpadahimpunanAdinamakanbersifatrefleksifjika (a, a) e R untuk setiap a e A.Dengan kata lain, suatu relasi R pada himpunanAdikatakantidakrefleksifjikaadaaeAsedemikiansehingga (a, a) e R. Contoh 2.5 :MisalkanA={1,2,3,4},danrelasiRadalahrelasisyang didefinisikan pada himpunan A, maka R = {(1, 1), (1, 2), (1, 3),(1, 4), (2, 2), (2, 3), (2,4), (3, 3), (3, 4), (4, 4)}Terlihatbahwa(1,1),(2,2),(3,3),(4,4)merupakanunsurdari R. Dengan demikian R dinamakan bersifat refleksif. Contoh 2.6 :MisalkanA = {2, 3, 4, 8, 9, 15}.Jika kita definisikan relasi R pada himpunan Adengan aturan : (a, b) e Rjika a faktor prima dari b Perhatikan bahwa(4, 4) e R .Jadi, jelas bahwa R tidak bersifat refleksif. Sifatrefleksifmemberibeberapacirikhasdalampenyajiansuatu relasi, yaitu : Telkom PolytechnicDiscrete Mathematics 40Relasi dan Fungsi PAGE 10 Relasiyangbersifatrefleksifmempunyaimatriksyangunsur diagonal utamanya semua bernilai 1, atau mii = 1, untuk i = 1, 2, , n,

(((((((

1111 Relasiyangbersifatrefleksifjikadisajikandalambentukgraf berarahmakapadagraftersebutsenantiasaditemukanloop setiap simpulnya. 2.Transitif (transitive) SuaturelasiRpadahimpunanAdinamakanbersifattransitifjika (a, b)eRdan(b, c) e R, maka (a, c) e R, untuk a, b, c e A. Contoh 2.7 : MisalkanA={2,3,4,5,6,7,8,9},danrelasiRdidefinisikan oleh : a R b jika dan hanya jika a membagi b,dimanaa, b e A, Jawab :DenganmemperhatikandefinisirelasiRpadahimpunanA, maka : R = {(2, 2), (2, 4), (2, 6), (2, 8), (3, 3), (3, 6), (3, 9), (4, 4), (4, 8)} Ketika (2, 4)e Rdan(4, 8) e R terlihat bahwa(2, 8) e R.Dengan demikian R bersifat transitif. Politeknik TelkomMatematika Diskrit Relasi dan Fungsi41 PAGE 10 Contoh 2.8 : RmerupakanrelasipadahimpunanbilanganasliNyang didefinisikan oleh: R:a + b = 5,a, b e A, Periksa, apakah relasi R bersifat transitif! Jawab :DenganmemperhatikandefinisirelasiRpadahimpunanA, maka : R = {(1, 4), (4, 1), (2, 3), (3, 2) } Perhatika bawa (1, 4)e Rdan(4, 1) e R , tetapi (1, 1) e R.Dengan demikian Rtidakbersifat transitif. Sifattransitifmemberikanbeberapacirikhasdalampenyajian suatu relasi, yaitu :-sifattransitifpadagrafberarahditunjukkanolehkondisi:jika adabusurdariakebdanbusurdaribkec,makajugaterdapatbusur berarahdari a ke c.-Padasaatmenyajikansuaturelasitransitifdalambentuk matriks,relasitransitiftidakmempunyaicirikhususpada matriks representasinya 3.Simetri(symmetric) dan Anti Simetri (antisymmetric) SuaturelasiRpadahimpunanAdinamakanbersifatsimetri jika (a, b)eR,untuk setiap a, b e A,maka (b, a) e R. Suatu relasi RpadahimpunanAdikatakantidaksimetrijika(a,b)eR, sementaraitu(b,a)eR.SuaturelasiRpadahimpunanA dikatakan anti simetrijikauntuksetiap a, b e A, (a, b) e Rdan (b,a)eRberlakuhanyajikaa=b.Perhatikanlahbahwaistilah simetridanantisimetritidaklahberlawanan,karenasuaturelasi dapatmemilikikeduasifatitusekaligus.Namun,relasitidak dapatmemilikikeduasifat tersebut sekaligus jika ia mengandungbeberapa pasangan terurut berbentuk (a, b) dimana a = b. Contoh 2.9 : Telkom PolytechnicDiscrete Mathematics 42Relasi dan Fungsi PAGE 10 Misalkan R merupakan relasi pada sebuahhimpunan Riil, yang dinyatakan oleh : a R bjika dan hanya jika a b e Z. Periksa apakah relasi R bersifat simetri ! Jawab : Misalkan a R b maka (a b) e Z, Sementara itu jelas bahwa (b a) e Z. Dengan demikian R bersifat simetri. Contoh 2.10 : TunjukanbahwarelasispadahimpunanZbersifatanti simetri Jawab : Jelas bahwa jikaa s bdan b s aberartia = b. Jadi relasi s bersifat anti simetri. Contoh 2.11 : RelasihabismembagipadahimpunanbilanganasliN merupakan contoh relasi yang tidak simetri karena jika a habis membagib,btidakhabismembagia,kecualijikaa=b. Sementaraitu,relasihabismembagimerupakanrelasiyang antisimetrikarenajikaahabismembagibdanbhabis membagi a maka a = b. Contoh 2.12 : MisalkanrelasiR={(1,1),(2,2),(3,3)}makarelasiR merupakanrelasiyangsimetrisekaligusrelasiyanganti simetri. Sifatsimetridanantisimetrimemberikanbeberapaciri khas dalampenyajian berbentuk matriks maupun graf, yaitu : Relasiyangbersifatsimetrimempunyaimatriksyangunsur-unsurdibawahdiagonalutamamerupakanpencerminandari unsur-unsur di atas diagonal utama, atau mij = mji = 1, untuk i = 1, 2, , n danj = 1, 2, , n adalah : Politeknik TelkomMatematika Diskrit Relasi dan Fungsi43 PAGE 10 (((((((

0101 Relasiyangbersifatsimetri,jikadisajikandalambentukgraf berarahmempunyaiciribahwajikaadabusurdariakeb, maka juga ada busur dari b ke a. Relasiyangbersifatantisimetrimempunyaimatriksdimana unsurnya mempunyai sifat: jika mij = 1 dengan i = j, maka mji = 0.Dengankatalain,matriksdarirelasiantisimetrimemenuhi kondisi: jika salah satu dari mij = 0 atau mji = 0 bila i = j : (((((((

010 001 Sedangkangrafberarahdarirelasiyangbersifatantisimetri mempunyaiciribahwatidakakanpernahadaduabusur dalam arah berlawanan antara dua simpul berbeda. Misalkan,RmerupakanrelasidarihimpunanAkehimpunanB.Invers darirelasiR,yangdilambangkandenganR1,adalahrelasidari himpunan B ke himpunan A yang didefinisikan oleh : R1 = {(b, a) | (a, b) e R } Contoh 2.13 : Misalkan P = {2, 3, 4} dan Q = {2, 4, 8, 9, 15}.Jika didefinisikan relasi R dari P ke Q yaitu : (p, q) e Rjika dan hanya jikap habis membagi q maka kita peroleh : R= {(2, 2), (2, 4), (4, 4), (2, 8), (4, 8), (3, 9), (3, 15)Telkom PolytechnicDiscrete Mathematics 44Relasi dan Fungsi PAGE 10 R1 merupakaninvers dari relasi R, yaitu relasi dari Q ke Pyang berbentuk : (q, p) e R1jika q adalah kelipatan dari p sehinggadiperoleh : R1= {(2, 2), (4, 2), (4, 4), (8, 2), (8, 4), (9, 3), (15, 3) } Jika M adalah matriks yang menyajikan suaturelasi R, M = ((((

0 0 1 1 01 1 0 0 00 0 1 1 1 maka matriks yang merepresentasikan relasi R1, misalkan N, diperoleh dengan melakukan transpose terhadap matriks M, N = MT =(((((((

0 1 00 1 01 0 11 0 10 0 1 2.3Operasi pada RelasiRelasimerupakanhimpunanpasanganterurutmakabeberapa operasialjabaryangberlakupadahimpunan,jugaberakupadarelasi.Operasihimpunansepertiirisan,gabungan,selisih,danbeda setangkup juga berlaku atara dua relasi. Jika R1 dan R2 masing-masing merupakan relasi dari himpunan A ke himpunan B, maka R1 R2, R1

R2, R1 R2, dan R1 R2 juga merupakan relasi dari A ke B. Contoh 2.14 : Misalkan A = {a, b, c} dan B = {a, b, c, d}.Relasi R1 = {(a, a), (b, b), (c, c)} Relasi R2 = {(a, a), (a, b), (a, c), (a, d)} Maka : R1 R2 = {(a, a)} Politeknik TelkomMatematika Diskrit Relasi dan Fungsi45 PAGE 10 R1R2 = {(a, a), (b, b), (c, c), (a, b), (a, c), (a, d)}R1 R2 = {(b, b), (c, c)}R2 R1 = {(a, b), (a, c), (a, d)}R1 R2 = {(b, b), (c, c), (a, b), (a, c), (a, d)}

Misalkan,relasiR1danR2masing-masingdisajikandalambentukmatriksMR1danMR2,makamatriksyangmenyatakangabungandan irisan dari kedua relasi tersebut adalah MR1R2 = MR1 v MR2dan MR1 R2 = MR1 . MR2 Contoh 2.15 : Misalkan bahwa relasi R1 dan R2 pada himpunan A dinyatakan oleh matriks R1 = ((((

0 1 11 0 10 0 0danR2 = ((((

0 0 11 1 00 1 0 makaMR1R2 = MR1 v MR2 = ((((

0 1 11 1 10 1 0

MR1 R2 = MR1 . MR2 = ((((

0 0 11 0 00 0 0 Misalkan R adalah relasi dari himpunan A ke himpunan B, dan TadalahrelasidarihimpunanBkehimpunanC.KomposisiRdanS, dinotasikandenganToR,adalahrelasidariAkeCyangdidefinisikan olehTelkom PolytechnicDiscrete Mathematics 46Relasi dan Fungsi PAGE 10 T o R = {(a, c) | a e A, c e C,untuk suatu b e Bsehingga(a, b) e Rdan (b, c) e S} Contoh 2.16 : Misalkan, A = {a, b, c},B = {2, 4, 6, 8} dan C = {s, t, u} Sementara itu, relasi dari A ke B didefinisikan oleh : R = {(a, 2), (a, 6), (b, 4), (c, 4), (c, 6), (c, 8)}SedangkanrelasidarihimpunanBkehimpunanCdidefisikan oleh :T = {(2, u), (4, s), (4, t), (6, t), (8, u)}Maka komposisi relasi R dan T adalah T o R = {(a, u), (a, t), (b, s), (b, t), (c, s), (c, t), (c, u) } Politeknik TelkomMatematika Diskrit Relasi dan Fungsi47 PAGE 10 Jikadisajikandengandiagrampanah,komposisirelasiRdanTadalah : 1232468stu JikarelasiR1danR2masing-masingdinyatakandenganmatriks MR1danMR2,makamatriksyangmenyatakankomposisidarikedua relasi tersebut adalah : MR2 o R1 = MR1 MR2 dimana MR1 MR2 merupakan perkalian antara dua buah matriks, tetapi denganmenggantitandakalidenganlogika.(dan),sedangakantanda tambah diganti denganlogika v (atau). Contoh 2.17 : MisalkanrelasiR1danR2padahimpunanAdisajikandalam bentuk matriks berikut : MR1 = ((((

1 0 00 1 11 0 1danMR2 = ((((

1 0 11 0 00 1 0 maka matriks yang menyatakan R2 o R1 adalah MR2 o R1 = MR1 . MR2

= ((((

. v . v . . v . v . . v . v .. v . v . . v . v . . v . v .. v . v . . v . v . . v . v .) 1 1 ( ) 1 0 ( ) 0 0 ( ) 0 1 ( ) 0 0 ( ) 1 0 ( ) 1 1 ( ) 0 0 ( ) 0 0 () 1 0 ( ) 1 1 ( ) 0 1 ( ) 0 0 ( ) 0 1 ( ) 1 1 ( ) 1 0 ( ) 0 1 ( ) 0 1 () 1 1 ( ) 1 0 ( ) 0 1 ( ) 0 1 ( ) 0 0 ( ) 1 1 ( ) 1 1 ( ) 0 0 ( ) 0 1 ( a b c Telkom PolytechnicDiscrete Mathematics 48Relasi dan Fungsi PAGE 10 = ((((

1 0 11 1 01 1 1 2.4Relasi Ekivalen dan Relasi Terurut SebuahrelasipadahimpunanAdinamakanrelasiekivalenjika relasitersebutrefleksif,simetridantransitif.Duaunsuryangberelasi ekivalen disebut equivalent. Contoh 2.18 :Misalkan R merupakan relasi pada sebuahZ, yang dinyatakan oleh : a R bjika dan hanya jika a = b atau a = b . Periksa, apakah relasi tersebut merupakan relasi ekivalen ! Jawab : Jelas bahwa a = a, dengan kata lain jika a R a untuk setiap a e Z .JadiR merupakan relasi refleksif. Jikaa = b dan b = c, ini mengakibatkan a = c. Dengan kata lain jikaa R b makab R c maka a R c.Dengan demikian R merupakan relasi transitif. Jikaa = b atau a = b makab = aatau b = a, dengankata lain jikaa R b makab R a.Jadi R merupakan relasi simetri. Dengan demikian R merupakan relasi ekivalen. Contoh 2.19 : MisalkanRmerupakanrelasipadasebuahhimpunanRiil,yang dinyatakan oleh : a R bjika dan hanya jika a b e Z. Periksa, apakah relasi tersebut merupakan relasi ekivalen ! Politeknik TelkomMatematika Diskrit Relasi dan Fungsi49 PAGE 10 Jawab : Untuk setiap a e Rill maka a a= 0 e bilangan bulat, oleh karena itu Rbersifat refleksif. MisalkanaRbmaka(ab)eZ,jelasbahwa(ba)eZ. Dengan demikian R bersifat simetri. Jika a R bdan b R c artinya(a b),(b c)e Zmaka (a c) = (a b) + (b c) juga merupakan bilangan bulat.Oleh karena itu a R c. Jadi R bersifat transitif. Dengan demikian R merupakan relasi ekivalen. Telkom PolytechnicDiscrete Mathematics 50Relasi dan Fungsi PAGE 10 Contoh 2.20 :(Modul Kongruen)Misalkan m adalah bilangan bulat yang lebih besar dari 1.Tunjukan bahwa Relasi R = {(a,b) | a b (mod m)} merupakan relasi ekivalenpada himpunan bilangan bulat. Jawab : Ingat bahwa a b(mod m)jika dan hanya jika m membagi a b . Karena a a = 0 dapat dibagi oleh m, yaitu 0 = 0 m.Oleh karena itu, a a (mod m) , sehingga R bersifat refleksif. a b dapat dibagi oleh m sehingga a b = km, untuk suatu k e Z Ini mengakibatkan b a = km.Jadi relasi tersebut simetri Misalkana b (mod m)danb c (mod m), sehingga a bdanb c dapat dibagi oleh m, atau a b = km danb c = lm untuk suatu k, le ZDengan menjumlahkan keduanya : a c = (a b)+ (b c)= (k + l) m,makaa c (mod m), Ini menunjukan bahwa relasi tersebut transitif. Dengan demikian R merupakan relasi ekivalen. MisalkanRadalahrelasiekivalenpadahimpunanA.Semuaunsur himpunanyangrelasidengansuatuunsureadiAdinamakankelas ekivalen dari a.Kelas ekivalen dari a terhadap relasi R dinotasikan oleh [a]R. Jika hanya ada satu relasi pada himpuanan tersebut, notainya adalah [a]. Contoh 2.21 : Tentukankelasekivalen0,1,2,dan3padarelasimodul kongruen 4! Jawab : [0] = { . . . , 12, 8, 4, 0, 4, 8, 12, . . . }[1] = { . . . , 11, 7, 3,1,5,9, . . . } [2] = { . . . , 10, 6, 2,2, 6, 10, . . . } Politeknik TelkomMatematika Diskrit Relasi dan Fungsi51 PAGE 10 [3] = { . . . , 11, 7, 3, 1, 5, 9, . . . } SebuahrelasiRpadahimpunanSdikatakanrelasiterurut parsialjikarelasitersebutbersifatrefleksif,antisimetridantransitif.SebuahhimpunanSyangdilengkapidengansebuahrelasiRyang terurut parsial, himpunan tersebut dinamakan himpunan terurut parsial(partially ordering set poset),Notasi : (S,R). Contoh 2.22 : Tunjukan bahwa relasi s merupakan relasi terurut pada Z. Jawab : Karena a s a untuk setiap a e Z, maka relasi s bersifat refleksi. Jikaasbdanbsaberartia=a.Jadirelasisbersifat antisimetri. Jikaasbdanbscberartiasc.Jadirelasisbersifat transitif. Dengan demikian relasi s merupakan relasi terurut pada Z. Setiapunsurdalamposet(S,)dikatakancomparable(dapat dibandingkan)jikaabataubauntuksetiapa,beS. Selanjutnya, Jika (S, )merupakansebuah posetdan setiap dua unsur dalamSadalahcomparable,makaSdinamakanHimpunanterurut total(TotallyOrderedSet-Toset)atauChain,sedangkandinamakan urutan total. Contoh 2.23 : 1.( N, s ) merupakan toset. 2.( N, | ) bukan toset karena tak comparable. Jika(S,)adalahsebuahtosetdansetiapsubsettakkosong dariSpalingsedikitmemilikisatuunsur,maka(S,)dinamakanWell-ordered Set (himpunan terurut dengan baik).Setiaphimpunanterurutparsialdapatdisajikandalambentuk diagramHasse.Langkah-langkahdalammenggambardigramHasse dari suatu poset adalah : Telkom PolytechnicDiscrete Mathematics 52Relasi dan Fungsi PAGE 10 -Gambarkan relasi urutan dalam bentuk directed graph. -Hapus semua loop (karena refleksif) -Hapus semua lintasan transitif Contoh 2.24 : Gambarkan diagram Hasse dari poset ({1,2,3,4}, = {(a, b) | a < b}} Jawab : 4 3 2 1 4 3 2 1 Politeknik TelkomMatematika Diskrit Relasi dan Fungsi53 PAGE 10 2.5Fungsi MisalkanAdanB merupakan himpunan. Suatu fungsi fdari A keBmerupakansebuahaturanyangmengkaitkansatu(tepatsatu) unsur di B untuk setiap unsurdi A.Kita dapat menuliskanf(a) = b, jika b merupakan unsur di B yang dikaitkan oleh funtuk suatu a di A.Ini berarti bahwa jika f(a) = bdanf(a) = cmakab = c. JikafadalahfungsidarihimpunanAkehimpunanB,kitadapat menuliskan dalam bentuk : f : A Bartinya fmemetakanhimpunan A ke himpunan B.A dinamakan daerah asal (domain)darifdanBdinamakan daerah hasil (codomain) dari f. Nama lain untuk fungsi adalah pemetaan atau transformasi.Misalkanf(a)=b,makabdinamakanbayangan(image)daria danadinamakanpra-bayangan(pre-image)darib.Himpunanyang berisisemuanilaipemetaanfdinamakanjelajah(range)darif. Perhatikanbahwajelajahdarifadalahhimpunanbagian(mungkin proper subset) dari B. abA Bfb= f(a) a Telkom PolytechnicDiscrete Mathematics 54Relasi dan Fungsi PAGE 10 Contoh 2.25 : Misalkan f : R Rdidefinisikan oleh f(x) = x2.Daerahasaldandaerahhasildarifadalahhimpunanbilangan Riil, sedangkan jelajah dari fmerupakan himpunan bilangan Riiltidak-negatif. Contoh 2.26 : Dibawah ini contoh suatu relasi yang bukan merupakan fungsi : Berikutiniadalahbeberapacontohfungsidalamberbagaicara penyajiannya, yaitu :1.Himpunan pasangan terurut.Misalkanfadalahfungsikuadratpada{1,2,3,4,5,6,7,8,9,10} maka fungsi itu dapat dituliskan dalam bentuk : f = {(2, 4), (3, 9)} a1A B23bcc d4Politeknik TelkomMatematika Diskrit Relasi dan Fungsi55 PAGE 10 2.Formula pengisian nilai (assignment). Contoh 2.27 :f(x) = x2 + 10,f(x) = 5x, 3.Kata-kata Contoh 2.28 :fadalahfungsiyangmemetakanjumlahbilanganbulat menjadi kuadratnya. 4.Kode program (source code) Contoh 2.29 :Fungsi menghitung |x|(harga mutlak dari). function abs(x:integer):integer; begin ifx >0then abs := x else abs :=x; end; MisalkangmerupakanfungsidarihimpunanAkehimpunan B,danfmerupakanfungsidarihimpunanBkehimpunanC.Fungsikomposisifdang,dinotasikandenganfog,merupakanfungsi dari AkeC yangdidefinisikan oleh : (f o g)(a) = f(g(a)), untuk suatu adi A. Perhatikan ilustrasi fungsi komposisi dibawah ini : a b c g f A B C Telkom PolytechnicDiscrete Mathematics 56Relasi dan Fungsi PAGE 10 1232468stu Politeknik TelkomMatematika Diskrit Relasi dan Fungsi57 PAGE 10 Contoh 2.30 :Misalkan f : Z Zdang : Z Z ,diberikan fungsi f(x) = x + 1 dan g(x) = x2 . Tentukan f o gdan g o f . Jawab : (i)(f o g)(x) = f(g(x)) = f(x2 ) = x2 + 1 . (ii) (g o f)(x) = g(f(x)) = g(x + 1) = (x + 1)2= x2+ 2x + 1.

SuatufungsifdarihimpunanAkehimpunanBdikatakansatu-ke-satu(one-to-one)atauinjektif(injective)jikatidakadaduaunsur himpunan A yang memiliki bayangan sama pada himpunan B. Contoh 2.31 : Misalkan f : Z Zdang : R R.Tentukanapakahf(x)=x2dang(x)=x+1merupakanfungsisatu-ke-satu? Jawab : a.f(x) = x2bukan fungsi satu-ke-satu, karena f(2) = f(2) = 4 padahal 2 = 2. b. g(x)=x+1 adalah fungsi satu-ke-satu karena untuk a = b,a +1 = b+1. Misalnya untuk x = 1,g(1)=2.Sementara itu, untuk x=2, g(2) = 3. SuatufungsifdarihimpunanAkehimpunanBdikatakanpada(onto) atau surjektif (surjective) jika setiap unsur pada himpunan B merupakan bayangandarisatuataulebihunsurhimpunanA.Dengankatalain seluruh unsur Bmerupakan jelajah dari f. Fungsi f disebut fungsi pada himpunan B. Contoh 2.32: Misalkan f : Z Zdang : R R.Tentukanapakahf(x)=x2dang(x)=x+1merupakanfungsi pada ! Jawab : a. f(x) = x2bukan fungsi pada,Telkom PolytechnicDiscrete Mathematics 58Relasi dan Fungsi PAGE 10 karenatidaksemuanilaibilanganbulatmerupakanjelajah dari f,yaitu bilangan bulat negatif.b.g(x) = x +1 adalah fungsi pada karena untuksetiap bilangan Riily,selalu ada nilai x yang memenuhi, yaitu y = x + 1.

SuatufungsifdarihimpunanAkehimpunanBdikatakan berkorespondensatu-ke-satuataubijeksi(bijection)jikafungsi tersebut satu-ke-satu dan juga pada. Agarmendapatkanpengertianyanglebihbaik,perhatikanilustrasi berikut : Fungsi satu-ke-satu, Fungsi pada, bukan padabukan satu-ke-satu JikafmerupakanfungsidarihimpunanAkehimpunanByang berkorespondensatu-ke-satumakakitasenantiasadapatmenemukan balikan(invers)darifungsif.Balikanfungsidinotasikandenganf1. MisalkanaadalahanggotahimpunanAdanbadalahanggota himpunanB,makaf -1(b)=ajikaf(a)=b.Fungsiyang berkorespondensatu-ke-satudisebutjugafungsiyanginvertible (dapatdibalik),sehinggakitadapatmendefinisikansuatufungsi balikannya.Jikaiabukanfungsiyangberkorespondensatu-ke-satua1AB23bc4a1AB23bcc dPoliteknik TelkomMatematika Diskrit Relasi dan Fungsi59 PAGE 10 makafungsitersebutdikatakantidakinvertible,karenafungsi balikannya tidak ada. Contoh 2.33 : Tentukan balikan fungsi f(x) = x + 1. Jawab : Fungsi f(x) = x + 1 merupakan fungsi yang berkoresponden satu-ke-satu, jadi invers fungsi tersebut ada.Misalkanf(x)=y,sehinggay=x+1,makax=y1.Jadi, balikan fungsi balikannya adalah f-1(y) = y 1.

Contoh 2.34 : Tentukan balikan fungsi f(x) = x2. Jawab : Daricontohsebelumnya,f(x)=x2bukanmerupakanfungsiyang berkoresponden satu-ke-satu,sehinggafungsibalikannyatidakada. Jadi, f(x) = x2 adalah fungsi yang tidak invertible. Fungsi Rekursif Fungsimerupakanbentukkhusudarisuaturelasi.Sebuah fungsidinamakanfungsirekursif,jikafungsitersebutmengacupada fungsi itu sendiri.Komponen penyusun fungsi rekursif, meliputi : 1.Nilai BasisKomponen ini merupakan nilai awal dari fungsi tersebut. 2.Rekurens Komponeninimendefinisikanargumenfungsiterkaitdengan dirinya sendiri. Contohfungsirekursifyangsederhanaadalahfungsifaktorial. Perhatikan kembali rumus faktorial : a.Nilai basis n!= 1,untuk n = 0 b.Rekurens Telkom PolytechnicDiscrete Mathematics 60Relasi dan Fungsi PAGE 10 n! = n x (n-1) !,untuk n > 1. Dengan demikian, saat kita akan mentukan nilai fungsi 4!,maka : 4 ! = 4 . 3 ! = 4 . 3 . 2! = 4 . 3 . 2 . 1! = 4 . 3 . 2. 1 . 0! = 24Dalamsuatualgoritma,biasanyakemunculanfungsirekursif terjadipadasuatulooping.Misalkandiketahuinilaifungsisaatt=0 adalah a, selanjutnya fungsi f(k) = 2 . f(k 1) + 3. Jadi secara sederhana, yangmenjadipeubahpadafungsirekursifadalahfungsipadaiterasi sebelumnya.Inilahyangmenyebabkankitaharusmempunyaisuatu nilai awal fungsi tersebut. Rangkuman Politeknik TelkomMatematika Diskrit Relasi dan Fungsi61 PAGE 10 1.Aturanyangmenghubungkanantaraduahimpunandinamakan relasi biner. 2.relasibinerRantarahimpunanAdanBmerupakanhimpunan bagian dari cartesian product A BatauR _ (A B). 3.Notasi dari suatu relasi biner adalah a R b atau (a, b) e R. 4.Caramenyajikansuaturelasidapatberupadiagrampanah, pasangan terurut, tabel, matriks, dan graf berarah. 5.JikaR1danR2masing-masingmerupakanrelasidarihimpunanA kehimpunanB,makaR1R2,R1R2,R1R2,danR1R2juga merupakan relasi dari A ke B. 6.Suatu relasi R pada himpunan A dinamakan bersifat refleksif jika (a, a) e R untuk setiap a e A. 7.Suatu relasi R pada himpunan A dinamakan bersifat transitif jika (a, b)eRdan(b, c) e R, maka (a, c) e R, untuk a, b, c e A. 8.Suatu relasi R pada himpunan A dinamakan bersifat simetri jika (a, b)eR,untuk setiap a, b e A,maka (b, a) e R. 9.SebuahrelasipadahimpunanAdinamakanrelasiekivalenjika relasi tersebut refleksif, simetri dan transitif. 10.SuatufungsifdariAkeBmerupakansebuahaturanyang mengkaitkan unsurdi A dengan satu (tepat satu) unsur di B. 11.Suatu fungsi f dari himpunan A ke himpunan B dikatakan satu-ke-satu(one-to-one)atauinjektif(injective)jikatidakadaduaunsur himpunan A yang memiliki bayangan sama pada himpunan B. 12.SuatufungsifdarihimpunanAkehimpunanBdikatakanpada (onto) atau surjektif (surjective) jika setiap unsur pada himpunan B merupakan bayangan dari satu atau lebih unsur himpunan A.13.SuatufungsifdarihimpunanAkehimpunanBdikatakan berkorespondensatu-ke-satuataubijeksi(bijection)jikafungsi tersebut satu-ke-satu dan juga pada.

Telkom PolytechnicDiscrete Mathematics 62Relasi dan Fungsi PAGE 10 Kuis Benar Salah (Untuksoalno15)DiketahuiA={2,3,5,7},RelasipadaA didefinisikan dalam himpunan : R = {(2, 2), (3, 3), (3, 5), (5, 3), (7, 3), (7, 7)}11.R bersifat refleksif12.R tidak bersifat simetri 13.R bersifat transitif14.R tidak bersifat antisimetri 15.R c R2

16.Relasi faktor dari pada himpunan A = {1, 2, 4, 8} merupakan relasi transitif. 17.Suatu relasi yang bersifat tidak simetri dinamakan relasi antisimetri.18.Relasi ekivalen adalah relasi yang bersifat simetri dan transitif 19.Jika setiap unsur pada himpunan B merupakan bayangan dari satu atau lebih unsur himpunan A, maka fungsi dari A ke B bersifat injektif. 20.Misalkan R dan S adalah relasi pada A = {a, b, c}, Jika R dan S adalah simetri maka R S adalah simetri. Politeknik TelkomMatematika Diskrit Relasi dan Fungsi63 PAGE 10 Pilihan Ganda 1.Relasi ekivalen harus memenuhi sifat :A.Refleksif dan simetriD.Refleksif, antisimetri, transitif B.Refleksif, simetri, transitifE.Refleksif, simetri , antisimetri C.Simetri dan transitif 2.Fungsi f(x) = x3 merupakanA.Fungsi injektifD.Fungsi Rekursif B.Fungsi SurjektifE.Fungsi antisimetri C.Fungsi bijektif 3.Relasi yang didefinisikan oleh a R bjika dan hanya jika a + b e Z, memenuhi sifat dibawah ini, kecuali : A.RefleksifD.Anti Simetri B.RekursifE.Transitif C.Simetri 4.Jika relasi R = {(1,2)} maka RR-1 bersifat :A.Tidak transitifD.Tidak simetri B.RefleksifE.Rekursif C.Tidak antisimetri 5.Diketahui U1 = 5dan Un = 2Un-1+ 3,maka U4 = .... Telkom PolytechnicDiscrete Mathematics 64Relasi dan Fungsi PAGE 10 A.29D.73 B.58E.0 C.61 6Suatu relasi dikatakan terurut parsial jika memenuhi sifat :A.Refleksif dan simetriD.Refleksif, antisimetri, transitif B.Refleksif, simetri, transitifE.Refleksif, simetri , antisimetri C.Simetri dan transitif 7MisalkanRadalahrelasipadasuatuhimpunanberhingga.Jika matriksdarirelasitersebutberbentukmatriksidentitas,makarelasi tersebut bersifat : ARefleksif, tidak transitiffDSimetri, transitifBRekursif dan transitifERefleksif, terurut totalCReflesif, tidak simetri (untuk soal no 8 10) Misalkan R dan S adlah relasi pada A = {1, 2, 3},R = {(1,1), (1,2), (2,3), (3,1), (3,3)} dan S = {(1,2), (1,3), (2,1), (3,3)} 8Himpunan Relasi Rc = .... A{(1,3), (2,1)}D{(1,3), (2,2), (3,2)} B{(1,3), (2,1), (2,2), (3,2)}E{(1,1), (2,2), (3,3)} C{(1,2), (3,3)} 9Himpunan Relasi komposisiR o S = .... A{(1,3), (2,1), (2,2), (3,2)}D{(1,1), (1,3), (2,2), (3,2)} B{(1,3), (2,2), (3,2)}E{(1,1),(1,2),(1,3) (2,3), (3,2), (3,3)} C{(1,2), (1,3), (2,3), (3,2)} 10Himpunan Relasi S2 = .... A{(1,3), (2,1), (2,2), (3,2)}D{(1,1), (1,3), (2,2), (3,2)} B{(1,3), (2,2), (3,2)}E{(1,1),(1,2),(1,3) (2,3), (3,2), (3,3)} C{(1,2), (1,3), (2,3), (3,2)} Politeknik TelkomMatematika Diskrit Relasi dan Fungsi65 PAGE 10 Latihan (Untuksoalno13)DiketahuiA={a,b,c,d,e}danB={x,y,z}. Misalkan R adalah relasi A ke B yang tertuang dalam himpunan : R = {(a, y), (a, z), (c, y), (d, x), (d, z)} 1.Tentukan matriks untuk relasi R 2.Gambar graf berarah untuk relasi R 3.Tentukan relasi invers dari relasi R 4.Periksaapakahrelasi(dalambentukpasanganterurut)berikut merupakan relasi ekivalen : a.{(0,0), (1,1), (2,2), (3,3) } b.{(0,0), (1,1), (1,3), (2,2), (2,3), (3,1), (3,2), (3,3) } 5.Misalkan matriks dari suatu relasi direpresentasikan dalam bentuk :MR = ((((

1 1 11 1 01 1 1

Periksaapakahrelasitersebutbersifatrefleksif,simetri,antisimetri, dan transitif 6.Periksa apakah relasi yang direpresentasikan dalam bentuk matriks dibawah inimerupakan relasi ekivalen :

Telkom PolytechnicDiscrete Mathematics 66Relasi dan Fungsi PAGE 10 MR = (((((

1 0 0 00 1 1 10 1 1 10 1 1 1 Politeknik TelkomMatematika Diskrit Relasi dan Fungsi67 PAGE 10 7.Jika suatu relasi R disajikan dalam bentuk matriks sebagai berikut : (((((

=1 0 0 00 1 0 01 0 1 00 1 1 1RMPeriksa apakah relasi tersebut merupakan relasi terurut ! 8.MisalkanAmerupakanhimpunanbilanganbulattaknoldanR merupakan relasi pada himpunan A X A, yang didefinisikan oleh : (a, b)R(c, d)jika ad = bcTunjukan bahwa R merupakan relasi ekivalen ! 9.Jika suatu relasi R disajikan dalam bentuk matriks sebagai berikut : (((((

=1 0 0 00 1 0 01 0 1 00 1 1 1RM TentukanduamatriksyangmerepresentasikanrelasiR1(relasi invers) dankomposisiR R1 ! 10.Gambarkan diagram Hasse dari poset {B , } dimanaB ={1, 2, 3, 4, 6, 8, 12}dan = {(a,b) | a membagi b}} Telkom PolytechnicDiscrete Mathematics 68Relasi dan Fungsi PAGE 10 Politeknik TelkomMatematika Diskrit Kombinatorik69 PAGE 10 3KOMBINATORIK Overview Kombinatorikmerupakanbagianpentingdarimatematikadiskrit. Dalambabiniakandibahasteknikpenghitung,permutasidan kombinasi.Salahsatumanfaatteknikpenghitungadalahuntuk menentukankompleksitasdalamalgoritma.Denganpengetahuan dasarkombinatorik,diharapkanakanmemberikanbekaldalam pemahaman lebih lanjut dalam optimasi maupun pengembangan atau penggunaan dalam aplikasi yang terkait dengan komputerisasi. Tujuan 1.Mahasiswa memahami konsep dasar kombinatorik. Telkom PolytechnicDiscrete Mathematics 70Kombinatorik PAGE 10 2.Mahasiswa membedakan permutasi dan kombinasi. 3.Mahasiswa dapat meyelesaikan berbagai persoalan yang terkait dengan kombinatorik. Prinsip Dasar Menghitung Duaprinsipdasaryangdigunakandalammenghitung(counting)yaitu aturan pejumlahan dan aturan perkalian. Prinsip PenjumlahanJika suatu himpunan A terbagi kedalam himpunan bagian A1, A2,,An,makajumlahunsurpadahimpunanAakansama dengan jumlah semua unsur yang ada pada setiap himpunan bagian A1, A2, , An. Secaratidaklangsung,padaprinsippenjumlahan,setiaphimpunan bagianA1,A2,,Antidaksalingtumpangtindih(salinglepas).Untuk himpunanyangsalingtumpangtindihtidakberlakulagiprinsip penjumlahan,daniniharusdiselesaikandenganprinsipinklusi-eksklusi yang akan dibahas kemudian. Contoh 1 : Seorang guru SD di daerah, mengajar murid kelas 4, kelas 5 dan kelas6.Jikajumlahmuridkelas4adalah25orangdanjumlah murid kelas 5 adalah 27 orang serta jumlah murid kelas 6 adalah 20orang,makajumlahmuridyangdiajargurutersebutadalah 25 + 27 + 20 = 72 murid. Contoh 2 : Seorangmahasiswa ingin membeli sebuah motor. Ia dihadapkan untuk memilih pada satu jenisdaritigamerkmotor,Honda 3Politeknik TelkomMatematika Diskrit Kombinatorik71 PAGE 10 pilihan,Suzuki2pilihan,danYamaha2pilihan.Dengan demikian, mahasiswa tersebut mempunyai mempunyai pilihan sebanyak 3 + 2 + 2 = 7 pilihan. PrinsipPerkalianMisalkansebuahprosedurdapatdipecahdalamdua penugasan.Penugasanpertamadapatdilakukandalamn1 cara,dantugaskeduadapatdilakukandalamn2carasetelah tugaspertamadilakukan.Dengandemikian,dalam mengerjakan prosedur tersebut ada (n1 x n2) cara.Secaratidaklangsung,padaprinsipperkalian,himpunanyang dioperasikan tak perlu saling lepas. Contoh1 : Berapabanyakstringdenganpanjangtujuhyangmungkin terbentuk dari dua bit (0 dan 1) Jawab: Setiapsukupadastringtersebutmempunyaidua kemungkinan, yaitu0 atau 1. Dengan demikian, pada pemilihan string dengan panjang tujuh dapat dilakukan dengan : 2 x 2 x 2 x 2 x 2 x 2 x 2 = 27= 128 string.

Contoh 2 :SeorangguruSDdidaerah,mengajarmuridkelas4,kelas5 dankelas6.Misalkan,jumlahmuridkelas4adalah25orang danjumlah murid kelas 5 adalah 27 orang serta jumlah murid kelas6adalah20orang.Jikagurutersebutinginmemilihtiga orangmuriddarianakdidiknya,dimanaseorangmuriddari setiapkelas,makagurutersebutmempunyai25x27x20= 13.500 cara dalam memilih susunan tigamurid tersebut. Telkom PolytechnicDiscrete Mathematics 72Kombinatorik PAGE 10 Contoh 3 : Berapa banyak bilangan ganjil antara 1000 dan 9999 (termasuk 1000 dan 9999 itu sendiri) dimana(a)semua angkanya berbeda (b)boleh ada angka yang berulang.Jawab :(a)posisi satuan: 5 kemungkinan angka (yaitu 1, 3, 5, 7 dan 9); posisiribuan:8kemungkinanangka(1sampai9kecuali angka yang telah dipilih) posisi ratusan:8 kemungkinan angka posisi puluhan: 7 kemungkinan angka makabanyakbilanganganjilseluruhnyaadalah(5)(8)(8)(7)= 2240 buah. (b)posisi satuan: 5 kemungkinan angka (yaitu 1, 3, 5, 7 dan 9); posisi ribuan: 9 kemungkinan angka (1 sampai 9) posisi ratusan:10 kemungkinan angka (0 sampai 9) posisi puluhan: 10 kemungkinan angka (0 sampai 9) makabanyakbilanganganjilseluruhnyaadalah(5)(9)(10)(10) = 4500 Contoh 5 : Password suatu login pada sistemkomputerpanjangnya lima sampai tujuh karakter. Tiap karakter boleh berupa huruf (huruf besardanhurufkeciltidakdibedakan)atauangka.Berapa banyak passwordyang dapat dibuat untuk suatu login ?Jawab : Banyaknyahurufalfabetadalah26(AZ)danbanyak angka adalah 10 (0 9), jadi seluruhnya 36 karakter.Untukpassworddenganpanjang5karakter,jumlah kemungkinan passwordadalah (36)(36)(36)(36)(36) = 365= 60.466.176 Politeknik TelkomMatematika Diskrit Kombinatorik73 PAGE 10 untukpassworddenganpanjang6karakter,jumlah kemungkinan passwordadalah (36)(36)(36)(36)(36)(36)(36) = 366= 2.176.782.336 danuntukpassworddenganpanjang8karakter,jumlahkemungkinan password adalah (36)(36)(36)(36)(36)(36)(36)(36) = 367 = 78.364.164.096 Jumlah seluruh password yang mungkinadalah60.466.176+2.176.782.336+78.364.164.096= 80.601.412.608 buah. Jadi, untuk suatu login akan mempunyai80.601.412.608 buah kemungkinan password. Ketikaduaprosesdikerjakandalamwaktuyangsama,kita tidakbisamenggunakanprinsippenjumlahanuntukmenghitung jumlahcarauntukmemilihsalahsatudariduaprosestersebut.Untuk menghitungprosestersebut,kitaharusmengenalprinsipinklusi-eksklusi.Contoh : Berapabanyakbyteyangdapatdisusunoleh8-bit,yang dimulai dengan 11 atau berakhir dengan 00?Jawab : Misalkan,A adalahhimpunan byte yang dimulai dengan 11,B adalahhimpunan byte yang diakhiri dengan 00, ABadalahhimpunanbyteyangberawaldengan11dan berakhir dengan 00, Telkom PolytechnicDiscrete Mathematics 74Kombinatorik PAGE 10 dan ABadalahhimpunanbyteyangberawaldengan11atau berakhir dengan 00 Makajumlahkemungkinanbyteyangdapatdisusunpada himpunan A adalah (1)(1)(2)(2)(2)(2)(2)(2) =26 Tulis,|A| = 26 = 64Sementaraitu,jumlahkemungkinanbyteyangdapatdisusun pada himpunan B adalah (2)(2)(2)(2)(2)(2)(1)(1) =26 Jadi,|B| = 26 = 64, Dengan cara yang sama,jumlah kemungkinan byte yang dapat disusun pada himpunan A B adalah (1)(1)(2)(2)(2)(2)(1)(1) =24 Sehingga|A B| = 24 = 16. maka |AB| = |A| + |B| |A B| = 64 + 64 16= 112. Dengan demikian,jumlah byte yang dapat disusun oleh 8-bit,yangdimulaidengan11atauberakhirdengan00adalah112 buah. Permutasi dan Kombinasi Permutasi Suatupermutasimerupakansusunanyangmungkindibuat denganmemperhatikanurutan.Dengankatalain,permutasi merupakanbentukkhususaplikasiprinsipperkalian.Misalkan diberikansuatuhimpunanAdenganjumlahanggotaadalahn,maka susunanterurutyangterdiridarirbuahanggotadinamakan Politeknik TelkomMatematika Diskrit Kombinatorik75 PAGE 10 permutasi-rdariA,ditulisP(n,r).Agarlebihjelasdalam perhitungannya, perhatikan penjelasan berikut ini :Jikar>n,jelasbahwaP(n,r)=0,karenatakmungkin menyusunranggotadariAyanghanyaterdiridarinbuah anggota dimana n < r. Jika r s n, Unsurpertamapermutasidapatdipilihdenganncarakarena terdapatnobjekdalamhimpunan.Unsurpermutasokedua dipilih dari n 1 objek, adalah dengan n 1cara, karena satu anggotatelahterpilih.Demikianpulausurketigapermutasi dipilih dari n 2 objek, adalah dengan n 2cara, karena dua anggotatelahterpilih.Halinidilakukanterusmenerus sehinggaurutanterakhirdipilihdarinr+1objekyang tersisa.Menurutkaidahperkalian,pemilihanobjekdalam susunanrbuahobjekdarinbuahobjekdapatdilakukan dengan : n(n 1) (n 2) (n r + 1) caraDengandemikian,permutasirobjekdarinbuahobjekadalahjumlah kemungkinanurutanrbuahobjekyangdipilihdarinbuahobjek, dengan r s n, pada setiap kemungkinan penyusunan r buah objek tidak ada urutan objek yang sama, yaitu : P(n, r) = n(n 1) (n 2) (n r + 1)= )! (!r nn Contoh 1 : MisalkanS={p,q,r}.Berapacarayangmungkindalam penyusunanduahurufpadaSsehinggatidakadaurutanyang sama ? Jawab : Susunan dua huruf yang mungkin adalah : pq, pr, qr, qp, rp, rqJadipenyusunantersebutdapatdilakukandenganenambuah cara. Dalampenyusunanini,dapatmenggunakandefinisipermutasi, yaitu : Telkom PolytechnicDiscrete Mathematics 76Kombinatorik PAGE 10 ( )611 . 2 . 3! 2 3! 3) 2 , 3 (=== P Denganmenggunakandefinisipermutasi,penyusunantersebut dapat dilakukan dengan enam buah cara. Contoh 2 : Misalkankitamempunyailimabuahboladenganwarnayang berbeda satu sama lain dan 3 buah kotak. Kita akan memasukan bola tersebutkedalamkotak. Masing-masing kotak hanya boleh diisi1buahbola.Berapajumlahurutanboladenganwarna berbedayangmungkindibuatdaripenempatanbolakedalam kotak-kotak tersebut? Jawab : kotak 1 dapat diisi oleh salah satu dari 5 bola(ada 5 pilihan);kotak 2 dapat diisi oleh salah satu dari 4 bola(ada 4 pilihan); kotak 3 dapat diisi oleh salah satu dari 3 bola(ada 3 pilihan). Jumlah urutan berbeda dari penempatan bola= (5)(4)(3) = 60 Jika menggunakan definisi permutasi maka : ( )601 . 21 . 2 . 3 . 4 . 5! 3 5! 5) 3 , 5 (=== P Kombinasi Misalkanrmerupakanunsurbilanganbulattaknegatif.Yang dimaksud dengan kombinasi rdari suatu himpunan B yang terdiri dari nanggota(objek)yangberbedaadalahjumlahhimpunanbagiandari Byangmemilikianggotarbuahobjek.Interpretasiyanglaintentang Politeknik TelkomMatematika Diskrit Kombinatorik77 PAGE 10 kombinasiadalahmenyusun(memilih)objeksejumlahrdarinbuah objek yang ada. Contoh 1 : Misalkan A = {p, q, r}, tentukansemua himpunan bagian dari A yang memiliki kardinalitas dua. Telkom PolytechnicDiscrete Mathematics 78Kombinatorik PAGE 10 Jawab : Himpunan bagian tersebut antara lain : {p, q},{p, r}, dan {q, r}.Jadi kita mempunyai kombinasi : pq,pr, danqr Padahimpunan,urutanunsurpadahimpunantidakdiperhatikan. Dengandemikian,kombinasi2darihimpunanA(penyusunandua huruf tanpa memperhatikan urutan) adalah 3, yaitupq,pr, danqr.Ini berbeda,padasaatkitamendefinisikanpermutasi(urutan diperhatikan),penyusunantersebutdapatdilakukandenganenam buah cara, yaitu pq, pr, qr, qp, rp, danrq. Contoh 2 : Misalkanada2buahbolayangberwarnasamadan3buah kotak.Bolaakandimasukankedalamkotaksehinggasetiap kotakhanyabolehberisipalingbanyak1bola.Berapajumlah cara memasukkan bola ke dalam kotak tersebut ? Jawab : Misalkanketigakotaktersebutditaruhmemanjang,makaada3 cara memasukan dua bola tersebut kedalam kotak, yaitu : Cara I :keduabolamasing-masingditaruhpadaduakotak pertama (kotak I dan kotak II). Cara II:keduabolamasing-masingditaruhpadaduakotak yang paling ujung (kotak Idankotak III) . Cara III:keduabolamasing-masingditaruhpadaduakotak terakhir (kotak IIdan Kotak III) . Secaraumum,jumlahcaramemasukkanrbuahbolayangberwarna sama ke dalam n buah kotak adalah :

)! ( !!!)) 1 ( )...( 2 )( 1 (r n rnrr n n n n= Politeknik TelkomMatematika Diskrit Kombinatorik79 PAGE 10 InimerupakanrumusumumkombinasiyangdinotasikanolehC(n,r) atau ||.|

\|rn

Diketahuiadanbuahbolayangtidakseluruhnyaberbeda warna(jadi,adabeberapabolayangwarnanyasama)akandimasukan kedalam n buah kotak. Misalnya komposisi bola tersebut adalah : n1 bola berwarna 1, n2 bola berwarna 2, nk bola berwarna k, jadin1 + n2 + + nk = n.Berapajumlahcarapengaturannbuahbolakedalamkotak-kotak tersebut (tiap kotak maksimum satu buah bola) ? Jika n buah bola itu kita anggap berbeda semuanya, maka jumlah cara pengaturan n buah bola ke dalam n buah kotak adalahP(n, n) = n!. Dari pengaturan n buah bola itu, ada n1! cara memasukkan bola berwarna 1ada n2! cara memasukkan bola berwarna 2 ada nk! cara memasukkan bola berwarna kPermutasinbuahbolayangmanan1diantaranyaberwarna1,n2 bola berwarna 2, , nk bola berwarna k adalah: ! !... !!! !... !) , () ,..., , ; (2 1 2 12 1k kkn n nnn n nn n Pn n n n P = = Cara lain: Ada C(n, n1) cara untuk menempatkan n1 buah bola yang berwarna 1.AdaC(nn1,n2)carauntukmenempatkann2buahbola berwarna 2. Telkom PolytechnicDiscrete Mathematics 80Kombinatorik PAGE 10 AdaC(nn1n3,n3)carauntukmenempatkann3buahbola berwarna 3. Ada C(n n1 n2 nk-1, nk ) cara untuk menempatkan nk buah bola berwarna k. Jumlah cara pengaturan seluruh bola kedalam kotak adalah: C(n; n1, n2, , nk) = C(n, n1) C(n n1, n2) C(n n1 n2 , n3) C(n n1 n2 nk-1, nk) = )! ( !!1 1n n nn )! ( !)! (2 1 21n n n nn n

)! ( !)! (2 1 32 1kn n n n nn n n

)! ... ( !)! ... (1 2 11 2 1k k kkn n n n n nn n n n =! !... ! !!3 2 1 kn n n nn Kesimpulan: ! !... !!) ,..., , ; ( ) ,..., , ; (2 12 1 2 1kk kn n nnn n n n C n n n n P = = Kombinasi Dengan Pengulangan Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.Masing-masing kotak hanya boleh diisi paling banyak satu buah bola.Jumlah cara memasukkan bola C(n, r).Jikamasing-masing kotakboleh lebih darisatu buahbola (tidak adapembatasanjumlahbola),makaJumlahcaramemasukkan bola, yaitu : C(n + r 1, r) = C(n + r 1, n 1). Contoh : 20 buah apel dan 15 buah jeruk dibagikan kepada 5 orang anak, tiap anak boleh mendapat lebih dari 1 buah apel atau jeruk, atau tidaksamasekali.Berapajumlahcarapembagianyangdapat dilakukan? Politeknik TelkomMatematika Diskrit Kombinatorik81 PAGE 10 Jawab :n = 5, r1 = 20 (apel) dan r2 = 15 (jeruk) Membagi 20 apel kepada 5 anak: C(5 + 20 1, 20) cara, Membagi 15 jeruk kepada 5 anak: C(5 + 15 1, 15) cara.Jumlah cara pembagian kedua buah itu adalah C(5 + 20 1, 20) C(5 + 15 1, 15) = C(24, 20) C(19, 15) Koefisien Binomial Misalkannmerupakanbilanganbulatpositif,denganteorema binomial,perpangkatanberbentuk(x+y)ndapatdijabarkandalambentuk segitiga Pascal berikut ini : (x + y)0 = 1 (x + y)1 = x + y (x + y)2 = x2 + 2xy + y2 (x + y)3 = x3 + 3x2y + 3xy2 + y3

(x + y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4 (x + y)5 = x5 + 5x4y + 10x3y2 + 10x2y3 + 5xy4 + y5

Secara umum, diperoleh rumus sebagai berikut : (x + y)n = C(n, 0) xn + C(n, 1) xn-1 y ++ C(n, k) xn-k yk ++C(n, n)yn

= k k nnky x k n C=0) , ( BilanganC(n,k)merupakankoefisienuntukx(nk)ykdinamakankoefisien binomial. Contoh : Jabarkan (2x + y)3. Jawab : Misalkan a = 2x dan b = y,(a + b)3 = C(3, 0) a3 + C(3, 1) a2b1 + C(3, 2) a1b2 + C(3, 3) b3 = 1 (2x)3 + 3 (2x)2 (y) + 3 (2x) (y)2 + 1 (y)3 = 8 x3 + 12x2 y+ 6x y2 y3 Telkom PolytechnicDiscrete Mathematics 82Kombinatorik PAGE 10 Contoh : Jabarkan (2x 3)3. Jawab : Misalkan a = 2x dan b = 3,(a + b)3 = C(3, 0) a3 + C(3, 1) a2b1 + C(3, 2) a1b2 + C(3, 3) b3 = 1 (2x)3 + 3 (2x)2 (3) + 3 (2x) (3)2 + 1 (3)3 = 8x3 36x2 + 54x 27

Contoh : Tentukan suku kelima dari penjabaran perpangkatan (x y)5. Jawab : (x y)5 = (x + (y))5. Suku kelimadari hasil penjabaran adalah:C(5, 4) x5 4 (y)4 = 10 x y4. Rangkuman Politeknik TelkomMatematika Diskrit Kombinatorik83 PAGE 10 1.Duaprinsipdasaryangdigunakandalammenghitung(counting)yaitu aturan pejumlahan dan aturan perkalian. 2.Suatu permutasi merupakan susunan yang mungkin dibuat dengan memperhatikan urutan. 3.Misalkan B terdiri darin anggota (objek) yang berbeda. kombinasi rdarisuatuhimpunanBadalahjumlahhimpunanbagiandariB yang memiliki anggota r buah objek. 4.Rumus permutasi r objek dari n buah objek adalah : P(n, r) = n(n 1) (n 2) (n r + 1)= )! (!r nn 5.Rumuskombinasirdarinanggotahimpunandinotasikanoleh C(n,r) = )! ( !!r n rnrn=||.|

\| 6.Padapolinom(xy)nmakabilanganC(n,k)merupakankoefisien untuk x(nk)yk dan dinamakankoefisien binomial. Telkom PolytechnicDiscrete Mathematics 84Kombinatorik PAGE 10 Kuis Benar Salah 1.Cara menghitung dengan prinsip penjumlahan sama dengan prinsip perkalian2.Nilai dari 5! = 120 3.Suatu permutasi merupakan susunan yang mungkin dibuat dengan tidakmemperhatikan urutan. 4.Memilih kemungkinan formasi 3 tim futsal dari 15 orang adalah menggunakan prinsip kombinasi. 5.Nilai P(5, 3)= 15 6.Nilai C(5, 2) = 10 7.(2x + y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4 8.P (10, 5) = C (10, 2) 9.Cara menghitung permutasi menggunakan prinsip perkalian 10.C(n + r 1, r) = C(n + r 1, n 1) Politeknik TelkomMatematika Diskrit Kombinatorik85 PAGE 10 Pilihan Ganda 1.Jika ada 3 dosen laki-laki dan 2 dosen perempuan, maka mahasiswa dapat memilih salah satu dari dosen tersebut dalam . A.1 caraD.5 cara B.2 caraE.6 cara C.3 cara 2.Dalam berapa cara sebuah himpunan mahasiswa yang terdiri dari 50 orangmemilihseorangketua,sekertarisdanbendahara,dimana tidak ada mahasiswa yang mendapat jabatan lebih dari satu. A.25 !caraD.3 cara B.25 caraE.25 x 24 x23 cara C.25x3 cara 3. ....28=||.|

\| A.2D.56 B.8E.128 C.28 4.Seorangpeternakmembeli3sapi,4kambingdan5ayamdari seorangpenjualyangmemiliki4sapi,5kambingdan7ayam.Dalamberapacarapeternaktersebutdapatmemilihketigahewan itu ? A.420 caraD.7 cara B.140 caraE.1 cara Telkom PolytechnicDiscrete Mathematics 86Kombinatorik PAGE 10 C.35 cara

5.Ada 9 jenis mainanyang akan dibagikan buat 4 orang anak. Setiap anakdiberi2jenismainan,kecualiyangtermudadiberi3jenis mainan. Ada berapa kemungkinan cara pembagian mainan tersebut ? A. ! 9 cara D. ) ! 2 !. 2 . ! 3 ( / ! 9 cara B. ! 2 / ! 9 caraE. ) ! 2 . ! 2 !. 2 . ! 3 ( / ! 9cara C. ) ! 3 . ! 2 ( / ! 9 cara Latihan 1.Tentukan nilai : a.||.|

\|1315 b. ||.|

\|911 2.Tentukan nilai : a.P(6, 3) b. C(5, 1) 3.Tunjukan bahwa : ||.|

\|+||.|

\|=||.|

\|616516617 4.Tentukan n jika :a. P(n,2) = 72b. P(n,4) = 42 P(n,2) 5.20mahasiswaakandibagidalamtigatim.Dalamberapa kemungkinan formasi tim yangdapat dibentuk. 6.Limaorangakandudukmenghadiriseminar.Dalamberapacara mereka dapat menempati tempat duduk, jika a.5 tempat duduk diletakan dalam satu baris b.5tempat duduk dibuat melingkar mengelilingi meja bundar Politeknik TelkomMatematika Diskrit Kombinatorik87 PAGE 10 7.Padatokodunydonutmenyediakanempatjenisdonatdengan rasayangberbeda(stokmasing-masingrasa10buah).Berapa jumlahcarapengambilan,jikaseseorangmembelidonattersebut enam buah. 8.Berapabanyakstringdenganpanjangsepuluhyangmungkin terbentuk dari dua bit (0 dan 1), yang memuat bit satu tepat tujuh buah. 9.Dalamsuatupacuankudadengan12peserta(diasumsikan semuanya dapatmencapaifinish),Berapajumlahkemungkinan susunan pemenang (pertama, kedua, dan ketiga)dalam pacuan tersebut. 10.Dengan menggunakan teorema binomial, tentukan : a.koefisien x5y8 dalam(x + y)13 b.koefisien x7 dalam(1 + x)11 c.koefisien x9 dalam (1 x)19 Telkom PolytechnicDiscrete Mathematics 88Teori Graf PAGE 10 4TEORI GRAF Overview Grafdigunakanuntukmenyelesaikandalamberbagaimasalah,antara lain:penentuanlintasanterpendekbaikuntukmaslaahkomunikasi maupuntransportasi,frekuensiassignmentdalamtelekomunikasi, optimasipenjadwalan,danlainlain.Pembahasangrafpadababini meliputi definisi dan terminologi graf, masalah lintasan terpendek serta beberapa sifat penting yang biasa digunakan dalam aplikasi. Tujuan 1.Mahasiswa memahami konsep dan terminologi graf. Politeknik TelkomMatematika Diskrit Teori Graf89 PAGE 10 2.Mahasiswa memodelkan masalah dalam bentuk graf. 3.Mahasiswa dapat meyelesaikan berbagai persoalan yang terkait dengan teori graf. 4.1Definisi Graf Graf merupakan struktur diskrit yang terdiri himpunan sejumlah berhinggaobyekyangdisebutsimpul(vertices,vertex)danhimpunan sisi(edges)yangmenghubungkansimpul-simpultersebut.terdiridari dariGrafdigunakanuntukmerepresentasikanobjek-objekdiskritdan hubungan antara objek-objek tersebut. Notasi sebuah graf adalah G = (V, E), dimana : Vmerupakanhimpunantakkosongdarisimpul-simpul(vertices), misalkanV = { v1 , v2 , ... , vn }Emerupakanhimpunansisisisi(edges)yang menghubungkan sepasang simpul,misalkanE = {e1 , e2 , ... , en } Contoh:Graf dari masalah jembatan Knigsberg dapat disajikan sebagai berikut : e2 e3 e4 e5 e6 e7 e1 B A C D Telkom PolytechnicDiscrete Mathematics 90Teori Graf PAGE 10 Misalkan graf tersebut adalah G(V, E) denganV = { A, B, C, D } E = { (A, C), (A, C), (A, B), (A, B), (B, D), (A, D), (C, D)} = { e1, e2, e3, e4, e5, e6, e7} Padagraftersebutsisie1=(A,C)dansisie2=(A,C) dinamakansisi-ganda(multipleedgesatauparaleledges)karena keduasisiinimenghubungiduabuahsimpulyangsama,yaitusimpul AdansimpulC.Begitupundengansisie3dansisie4.Sementaraitu, pada graf diatas, tidak terdapat gelang (loop), yaitusisi yangberawal dan berakhir pada simpul yang sama. Daridefinisigraf,himpunansisi(E)memungkinkanberupa himpunankosong.Jikagraftersebutmempunyaihimpunansisiyang merupakanhimpunankosongmakagraftersebutdinamakangraf kosong(null graph atau empty graph).Contoh : Graf kosong dengan 3 simpul (grafN3 ) Denganmemperhatikankondisisisinya,suatugrafdapat dikategorikansebagaigraftidakberarahdangrafberarah.Graftidak berarah,sepertitelahdijelaskanpadacontohgrafuntukjembatan Knigsberg.Sementaraitu,grafberarah(directedgraph,digraph) merupakangrafyangmempunyaisisiyangberarah,artinyasatubuah simpulyangdihubungkanolehsisitersebutmerupakansimpulawal (initialvertex)dansimpulyanglaindikatakansebagaisimpulakhir (terminal vertex). v1 v2 v3 Politeknik TelkomMatematika Diskrit Teori Graf91 PAGE 10 Beberapa jenis graf yang perlu diketahui adalah :1. Graf sederhana (simple graph). Grafsederhanamerupakangraftakberarahyangtidak mengandung gelang maupun sisi-ganda. Contoh : Graf sederhana Selanjutnya, pernyataan suatu graf pada buku ini merepresentasikan bahwagraftersebutadalahgrafsederhana.Kecualiapabilaada penambahanlain,misalkangrafsemuataugrafberarah,danlain-lain. P SQ R Telkom PolytechnicDiscrete Mathematics 92Teori Graf PAGE 10 2. Graf Ganda(multigraph). Grafgandamerupakangraftakberarahyangtidakmengandung gelang (loop). Contoh : Graf ganda

Dengandemikian,grafsederhanapunmerupakangrafganda (multi graph). 3. Graf semu (Pseudo graph) Graf semu merupakan graf yang boleh mengandung gelang (loop).

Contoh :Graf semu : P SQ R P SQ R Politeknik TelkomMatematika Diskrit Teori Graf93 PAGE 10 Telkom PolytechnicDiscrete Mathematics 94Teori Graf PAGE 10 4. Grafberarah(directed graphataudigraph). Grafberarahmerupakangrafyangsetiapsisinyamempunyaiarah dantidakmempunyaiduasisiyangberlawananantaraduabuah simpul (tak mempunyai sisi ganda) Contoh :a. Graf berarah : b. Grafgandaberarah(directed multigraph). Grafgandaberarahmerupakangrafberarahyang membolehkanadanyasisigandapadagraftersebut(boleh mempunyaiduasisiyangberlawananantaraduabuah simpul).

P SQ R R P SQ Politeknik TelkomMatematika Diskrit Teori Graf95 PAGE 10 Darijenis-jenisgrafyangtelahdijelaskandiatas,kitadapatmembuat ringkasan (sebagai bahan perbandingan) [3], seperti tertulis pada tabel 4.1. Tabel 4.1 Jenis-jenis grafJenisSisiSisi ganda dibolehkan? Gelang (loop) dibolehkan? Graf sederhana Graf ganda Graf semu Graf berarah Graf ganda berarah Tak-berarah Tak-berarah Tak-berarah Bearah Bearah Tidak Ya Ya Tidak Ya Tidak Tidak Ya Ya Ya Contoh : Graf berikut merupakan graf berarah : e6 P SQ R e1 e4 e3 e2 Telkom PolytechnicDiscrete Mathematics 96Teori Graf PAGE 10 Terlihat bahwae1 = (P, S),e3 = (R, Q),dan e5 = (Q, Q) SimpulPmerupakansimpulawalbagisisie1dansimpulS merupakan simpul akhirbagi sisi e1.

4.2Terminologi Graf Ada beberapa terminologi graf yang perlu diketahui, antara lain : ketetanggaanantaraduasimpul,bersisian,derajatsuatusimpul,dan lain-lain.Berikut ini adalah beberapa terminoogi yang penting, yaitu : 1.Bertetangga(Adjacent) Dua buah simpul dikatakan bertetangga jika kedua simpul tersebutterhubung langsung oleh suatu sisi.Contoh : Perhatikan graf berikut : Pada graf diatas : simpul Pbertetangga dengan simpul Q dan S, tetapi simpul P tidak bertetangga dengan simpul R. 2. Bersisian (Incidency) Suatu sisi e dikatakan bersisian dengan simpul v1 dan simpul v2 jika e menghubungkankedua simpul tersebut, dengankata lain e = (v1, v2).Contoh : Perhatikan graf dari masalah jembatan Knigsbergberikut ini :P SQ R Politeknik TelkomMatematika Diskrit Teori Graf97 PAGE 10

makae1bersisiandengansimpulAdansimpulC,tetapisisi tersebut tidak berisian dengan simpul B. 3. Simpul Terpencil (Isolated Vertex) Jikasuatusimpultidakmempunyaisisiyangbersisiandengannya maka simpul tersebutdinamakan simpul terpencil.

Contoh : Perhatikan graf berikut : Simpul Tdansimpul Umerupakan simpul terpencil. 5. Derajat (Degree) P SQ R T U e2 e3 e4 e5 e6 e7 e1 B A C D Telkom PolytechnicDiscrete Mathematics 98Teori Graf PAGE 10 Derajatsuatusimpulmerupakanjumlahsisiyangbersisiandengan simpul tersebut. Misalkan,suatusimpulvmempunyai3buahsisiyangbersisian dengannya maka dapat dikatakan simpul tersebut berderajat 3, atau dinotasikan oleh d(v) = 3. Contoh 1: Perhatikan graf berikut : Pada graf diatas: d(P) = d(Q)= d (S)= 5,sedangkan d(R) = 3. Derajatsebuahsimpulpadasuatugrafberarahdijelaskan sebagai berikut : din(v) merupakanjumlah busur yang masuk ke simpul v dout(v) merupakan jumlah busur yang keluar dari simpul v Dengan demikian derajat pada simpul tersebut, diperoleh :d(v) = din(v) + dout(v) Contoh 2 : Perhatikan graf berarah berikut ini : P SQ R P SQ R Politeknik TelkomMatematika Diskrit Teori Graf99 PAGE 10 Pada graf diatas: din (P) = 1dan dout (P) = 3makad (P) = 4 din (Q) = 4dan dout (Q) = 1makad (Q) = 5 din (R) = 1dan dout (R) = 1makad (R) = 2 din (S) = 1dan dout (S) = 2makad (S) = 3 Jumlahderajatsemuasimpulpadasuatugrafadalahgenap, yaituduakalijumlahsisipadagraftersebut.JikaG=(V,E) merupakan suatu graf, maka dapat ditulis :E v dV v2 ) ( =e Contoh 3 : Perhatikangrafpadacontoh1.Jumlahsisipadagraftersebut adalah 9, sehingga Jumlah derajat pada graftersebut adalah : 189 . 2. 2 ) (===eE v dV v atau 183 5 5 5) ( ) ( ) ( ) ( ) (=+ + + =+ + + =eS d R d Q d P d v dV v Perhatikan graf pada contoh 2. Jumlah sisi pada graf tersebut adalah 7, sehingga Jumlah derajat pada graftersebut adalah : 14 7 . 2 . 2 ) ( = = =eE v dV v atauTelkom PolytechnicDiscrete Mathematics 100Teori Graf PAGE 10 14 3 2 5 4) ( ) ( ) ( ) ( ) (= + + + =+ + + =eS d R d Q d P d v dV v Dengandemikian,jikakitainginmenggambarsebuahgraf denganderajatmasing-masingsimpuldiketahui,danternyata jumlah derajat seluruh simpul tersebut adalah ganjil maka hal ini tak mungkin terjadi. 6. Lintasan (Path)Jalurdarisuatusimpulawalv0kesimpultujuanvTdidalam suatu graf G merupakan barisan sebuah sisi atau lebih (x0, x1), (x1, x2), (x2, x3), , (xn-1, xn) pada G, dimana x0 = v0 danxn = vT.Padasuatujalurtidakmengalamipengulangansisi.Jalurdapatjuga dinotasikan oleh simpul-simpul yang dilewati, yaitu : x0, x1, x2, x3, , xn Jika jalur yang digunakan tidak melakukan pengulangan simpul maka jalurinidinamakanlintasan(path).Suatulintasandikatakan memilikipanjangn,jikalintasaninimemuatnbuahsisi,yang dilewatidarisuatusimpulawalv0kesimpultujuanvTdidalam suatugrafG.Suatujaluryangberawaldanberakhirpadasimpul yang sama dinamakan Sirkuit (Circuit). Sementara itu, lintasanyang berawaldanberakhirpadasimpulyangsamadinamakansilkus (cycle). Contoh : Perhatikan graf berikut ini : P SQ R T U Politeknik TelkomMatematika Diskrit Teori Graf101 PAGE 10 PadagraftersebutlintasanP,Q,Rmemilikipanjang2. Sementara itu lintasan P, Q, S, R memiliki panjang 3. Lintasan P, Q, R, S, P dinamakan siklus dengan panjang 4.Antara simpul P dan U maupun T tidak dapat ditemukan lintasan. Panjangsuatusiklusterpendekpadagrafsederhanaadalah tiga,artinyasiklustersebutharusmelewatitigasisi.Sedangkan, Panjangsuatusiklusterpendekpadagrafsemuadalahsatu,artinya siklustersebutdapatberupaloop.Diametersuatugrafmerupakan panjang lintasan terpanjang pada graf tersebut. Berikut ini adalah beberapa graf yang sering digunakan :a.Graf Lengkap (Complete Graph) Graflengkapmerupakangrafsederhanayangsetiapsimpulnya terhubung (oleh satu sisi) ke semua simpul lainnya. Dengan kata lain, setiap simpulnya bertetangga. Graf lengkap dengan n buah simpuldilambangkandenganKn.Jumlahsisipadasebuahgraf lengkap yang terdiri dari n buah simpul adalah n(n 1)/2 sisi.Contoh : K1K2 K3K4K5 K6 Gambar 4.3Grap lengkap Kn, 1 s n s 6 b.Graf Lingkaran(Cycle Graph) Graf lingkaran merupakan graf sederhana yang setiap simpulnya berderajatdua.Graflingkarannsimpuldilambangkandengan Cn.Telkom PolytechnicDiscrete Mathematics 102Teori Graf PAGE 10 C3 C4 C5C6 Gambar 4.4Grap LingkaranCn, 3 s n s 6 c. GrafRoda (Wheels Graph) Grafrodamerupakangrafyangdiperolehdengancara menambahkansatusimpulpadagraflingkaranCn,dan menghubungkansimpulbarutersebutdengansemuasimpul pada graf lingkaran tersebut. W3 W4W5 Gambar 4.5Grap Roda Wn, 3 s n s 5 d. Graf Teratur (Regular Graphs) Grafteraturmerupakangrafyangsetiapsimpulnyamempunyai derajatyangsama.Apabiladerajatsetiapsimpulpadagrap teraturadalahr,makagraftersebutdinamakangrafteratur berderajatr.Jumlahsisipadagrafteraturdengannsimpul adalah2nrsisi.Politeknik TelkomMatematika Diskrit Teori Graf103 PAGE 10 Gambar 4.5Graf Reguler Berderajat 3 e. Graf Planar (Planar Graph) dan Graf Bidang (Plane Graph) Grafyangdapatdigambarkanpadabidangdatardengansisi-sisi yang tidak saling berpotongan dinamakan graf planar. Jika tidak, maka graf tersebut dinamakan graf tak-planar. Beberapa contoh dari graf planar adalah - Semua graf lingkaran merupakan graf planar- Graf lengkap K1, K2, K3, K4merupakan graf planar Tetapi graf lengkap Kn untuk n > 5 merupakan graf tak-planar. Ilustrasi untuk graf planar K4. Gambar 4.6K4 adalah graf planar Grafplanaryangdigambarkandengansisi-sisiyangtidak saling berpotongan dinamakan graf bidang (plane graph). Sementaraitu,untukmembedakanantaragrafplanardangraf bidang, perhatikan ilustrasipada graf K4 berikut ini : (a) (b) (c) Telkom PolytechnicDiscrete Mathematics 104Teori Graf PAGE 10 Gambar 4.7 Tiga buah graf planar. Graf (b) dan (c) adalah graf bidang Beberapa hal tentang graf planar G(V, E), antara lain : (FormulaEuler)MisalkanGmerupakangrafplanarterhubung dengan e buahsisi dan v buahsimpul,danrmerupakanjumlahdaerahpadagrafplanartersebutmaka r = e v + 2. JikaGmerupakangrafplanarterhubungdengane buahsisidanvbuahsimpul(v>3)makaes3v6 (ketaksamaan Euler). JikaGmerupakangrafplanarterhubungdenganebuahsisidanvbuahsimpul(v>3)dantidakmemuat sirkuit dengan panjang 3 maka e s 2v 4. f. Graf bipartit(Bipartite Graph) SebuahgrafsederhanaGdikatakangrafbipartitjikahimpunan simpulpadagraftersebutdapatdipisahmenjadiduahimpunan tak kosong yang disjoint, misalkan V1 dan V2,sedemikian sehingga setiapsisipadaGmenghubungkansebuahsimpulpadaV1dansebuahsimpulpadaV2.Dengandemikian,padagrapbipartit tidakadasisiyangmenghubungkanduasimpulpadaV1atauV2. Graf bipartit tersebut dinotasikanolehG(V1, V2). Contoh : GrafG berikut merupakan graf bipartit : a c d e b Politeknik TelkomMatematika Diskrit Teori Graf105 PAGE 10 Graf diatasdapatdirepresentasikanmenjadigrafbipartitG(V1, V2),dimanaV1= {a, b} danV2 = {c, d, e} Representasi graf bipartit, dari graf pada contoh diatas adalah :

Gambar 4.7Graf bipartit g. Graf BerlabelGrafberlabeladalahgrafyangsetiapsisinyadiberisebuahlabel (bobot). V1V2 a c d e b p t s r q 89 10 1312 11 7 Telkom PolytechnicDiscrete Mathematics 106Teori Graf PAGE 10 Gambar 4.8Graf K5 yang sisinya dilabeli Grafdapatjugadiberilabelpadasimpulnya,tergatung representasi label yang diberikan. 4.3Keterhubungan dan Sub Graf Duabuahsimpulv1dansimpulv2padasuatugrafdikatakan terhubungjikaterdapatlintasandariv1kev2.Jikasetiappasang simpul vi dan vj dalam himpunan Vpada suatu graf G terdapat lintasan darividanvjmakagraftersebutdinamakangrafterhubung (connectedgraph).Jikatidak,makaGdinamakangraftak-terhubung (disconnected graph). Contoh 1 :Graf roda merupakan salah satu contoh graf terhubung: Contoh 2 :Perhatikan graf lingkaran berikut ini : p q r a b c d a c p q r c Politeknik TelkomMatematika Diskrit Teori Graf107 PAGE 10 (i)(ii) (iii) Jelasbahwa(i)C3dan(ii)C4merupakangrafterhubung.Sementara itu, graf (iii) merupakan graftak-terhubung, karena takadalintasanyangmenghubungkansimpulsalahsatu