modul matematika diskrit.docx

Matematika Diskrit

Isnania Lestari, ST

Matematika Diskrit 2011/2012

STKIP PGRI PontianakProgram Studi Pendidikan Teknologi dan Komputer

2

Matematika Diskrit 2011/2012Kombinatorika

Kombinatorika (combinatoric) adalah cabang matematika yang mempelajari pengaturan objek – objek. Solusi yang ingin kita peroleh dengan kombinatorial adalah jumlah cara pengaturan objek – objek tertentu dalam himpunannya. Contoh ilustrasi berikut dikemukakan untuk memperjelas masalah seperti apa yang akan di pecahkan dengan kombinatorika. 1) Misalkan, nomor plat mobil di negara X terdiri dari 5 angaka diikuti oleh 2 huruf. Angka pertama tidak boleh 0. Berapa banyak nomor plat yang di buat? 2) Misalkan, sandi – lewat (password) sistem kmputer panjangnya enam sampai delapan karakter. Tiap karakter boleh berupa angka atau huruf; huruf besar dan huruf kecil tidak dibedakan. Berapa banyak sandi lewat yang dapat dibuat.Kombinatorika merupakan bagian penting dari matematika diskrit. Dalam bab ini akan di bahas mengenai prinsip dasar perhitungan, permutasi dan kombinasi. Salah satu manfaat teknik perhitungan adalah untuk menentukan kompleksitas dalam algoritma.

1. Prinsip Dasar Perhitungan a. Prinsip PenjumlahanBila percobaan 1 mempunyai p hasil percobaan yang mungkin terjadi, percobaan 2 mempunyai q hasil percobaan yang mungkin terjadi, maka bila hanya satu percobaan saja yang dilakukan (percobaan 1 atau 3

Matematika Diskrit 2011/2012percobaan 2), terdapat p + q kemungkinan hasil percobaan. Dengan kata lain : Percobaan 1 = p hasilPercobaan 2 = q hasilMaka, Percobaan 1 atau percobaan 2 = p + q hasilContoh soal Prinsip Penjumlahan : Misalkan dua buah dadu yang berbeda warnanya (Dadu merah dan Dadu putih) dilontarkan. Ada berapa macam cara untuk mendapatkan jumlah angka 4 atau 8?Penyelesaian : a. Cara untuk mendapatkan dadu dengan jumlah angka 4 adalah sebagai berikut :

Jadi, ada 3 cara untuk mendapatkan dadu dengan jumlah angka 4.b. Cara untuk mendapatkan dadu dengan jumlah angka 8 adalah sebagai berikut :

4

Dadu Merah Dadu Putih

2

3

4

5

6

6

5

4

3

2

Dadu Merah Dadu Putih

1

2

3

3

2

1


Jadi, ada 5 cara untuk mendapatkan dadu dengan jumlah angka 8.Jadi banyaknya cara untuk mendapatkan jumlah angka 4 atau 8 adalah 3 + 5 = 8 carab. Prinsip PerkalianBila percobaan 1 mempunyai p hasil percobaan yang mungkin terjadi, percobaan 2 mempunyai q hasil percobaan yang mungkin terjadi , maka bila percobaan 1 dan percobaan 2 dilakukan, maka terdapat pxq hasil percobaan. Dengan kata lain : Percobaan 1 = p hasilPercobaan 2 = q hasilMaka, Percobaan 1 dan percobaan 2 = p x q hasilContoh prinsip perkalian :Sekelompok mahasiswa terdiri atas 24 orang pria dan 13 orang wanita. Berapa jumlah cara untuk memilih satu orang wakil pria dan satu orang wakil wanita? Penyelesaian: Ada 24 kemungkinan untuk memilih satu wakil pria, dan 13 kemungkinan memilih salah satu wakil wanita. Jika 2 orang wakil yang harus dipilih, maka jumlah kemungkinannya adalah 24 x 13 = 312.

5

Perbedaan antara prinsip penjumlahan dan prinsip perkalian adalah kata ATAU dan kata DAN.o ATAU untuk prinsip perkalian .o DAN untuk prinsip penjumlahan.


2. Permutasi a. Faktorial Misalkan n adalah bilangan bulat positif. Besaran n faktorial (n!) didefinisikan sebagai hasil kali semua bilangan bulat antara n hingga 1. Untuk n = 0 atau dengan kata lain 0! didefinisikan =1.n! = n.(n-1)(n-2)... 10! = 1. Contoh soal :Tuliskan 10 faktorial pertama : Penyelesaian : 0! = 11! = 12! = 2 . 1 = 2 3! = 3.2.1 = 64! = 4.3.2.1 = 245! = 5.4.3.2.1 = 120Dst... b. Permutasi Permutasi adalah penyusunan kembali suatu kumpulan objek dalam urutan yang berbeda dari urutan yang semula.

Urutan diperhatikan Perulangan tidak diperbolehkan

6

Matematika Diskrit 2011/2012Misalkan Masalah penyusunan kepanitiaan yang terdiri dari Ketua, Sekretaris dan Bendahara dimana urutan dipertimbangkan merupakan salah satu contoh permutasi. Jika terdapat 3 orang (misalnya Amir, Budi dan Cindy) yang akan dipilih untuk menduduki posisi tersebut, maka dengan menggunakan Prinsip Perkalian kita dapat menentukan banyaknya susunan panitia yang mungkin, yaitu:

Pertama menentukan Ketua, yang dapat dilakukan dalam 3 cara. Begitu Ketua ditentukan, Sekretaris dapat ditentukan dalam 2 cara. Setelah Ketua dan Sekretaris ditentukan, Bendahara dapat ditentukan dalam 1 cara. Sehingga banyaknya susunan panitia yang mungkin adalah 3.2.1 = 6.Contoh Soal Permutasi :1. Gunakan Teorema 3.1 untuk mencari berapa banyak permutasi dari huruf ABC ? Penyelesaian Terdapat 3 unsur dari huruf ABC, jadi banyaknya permutasinya adalah 3!, atau Terdapat 3.2.1 = 6 permutasi dari huruf ABC.2. Berapa banyak permutasi dari huruf ABCDEF jika huruf ABC harus selalu muncul bersama? PenyelesaianKarena huruf ABC harus selalu muncul bersama, maka huruf ABC bisa dinyatakan sebagai satu unsur. Dengan demikian terdapat 4 unsur yang dipermutasikan, sehingga banyaknya permutasi adalah

7

Matematika Diskrit 2011/20124.3.2.1 = 24.Permutasi-r dari n objek adalah jumlah kemungkinan urutan r buah objek yang dipilih dari n buah objek, dengan r ≤ n, yang dalam hal ini, pada setiap kemungkinan urutan tidak ada objek yang sama. Dan dapat di notasikan dengan P(n,r).Banyaknya permutasi-r dari n unsur yang berbeda adalah

Atau dengan kata lain, secara umum permutasi r objek dari n buah objek dapat di hitung dengan persamaan berikut :

Jika r = n, maka persamaan menjadi

Contoh Soal permutasi-r :Tentukan permutasi-3 dari 5 huruf yang berbeda, misalnya ABCDE. PenyelesianKarena r = 3 dan n = 5 maka permutasi-3 dari 5 huruf ABCDE adalah

8


Jadi banyaknya permutasi-3 dari 5 huruf ABCDE adalah 60. 3. KombinasiKombinasi adalah menyusun (memilih) objek sejumlah r dari n buah objek yang ada. Kombinasi r elemen dari n elemen, atau C(n, r), adalah jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen. Aturan kombinasi adalah:

Urutan tidak diperhatikan Tidak boleh ada pengulangan

Misalnya pemilihan 3 orang untuk mewakili kelompak 5 orang (misalnya Dedi, Eka, Feri, Gani dan Hari) dalam mengikuti suatu kegiatan. Dalam masalah ini, urutan tidak dipertimbangkan karena tidak ada bedanya antara Dedi, Eka dan Feri dengan Eka, Dedi dan Feri. Dengan mendata semua kemungkinan 3 orang yang akan dipilih dari 5 orang yang ada, diperoleh: {Dedi,Eka,Feri}{Dedi,Eka,Gani}{Dedi,Eka,Hari}{Dedi,Feri,Gani}{Dedi,Feri,Hari}{Dedi,Gani,Hari}{Eka,Feri,Gani}{Eka,Feri,Hadi}9

Matematika Diskrit 2011/2012{Eka,Gani,Hari}{Feri,Gani,Hari}Sehingga terdapat 10 cara untuk memilih 3 orang dari 5 orang yang ada. Selanjutnya kita dapat mendenisikan kombinasi secara formal seperti dibawah ini: Kombinasi-r dari n unsur yang berbeda x1, x2,.., xn adalah seleksi tak terurut r anggota dari himpunan {x1, x2,..., xn} (sub-himpunan dengan r unsur).Banyaknya kombinasi-r dari n unsur yang berbeda dinotasikan dengan C(n,r) atau

C ( nr ).

Contoh Soal Kombinasi : Tentukan kombinasi-3 dari 5 huruf yang berbeda, misalnya ABCDE? Penyelesaian Kombinasi-3 dari huruf ABCDE adalahABC ABD ABE ACD ACEADE BCD BCE BDE CDESehingga banyaknya kombinasi-3 dari 5 huruf ABCDE adalah 10. Banyaknya kombinasi-r dari n unsur yang berbeda adalah

Contoh soal kombinasi-r:

10

Matematika Diskrit 2011/20121. Gunakan rumus kombinasi-r untuk menentukan kombinasi-3 dari 5 huruf yang berbeda, misalnya ABCDE.Penyelesaian Karena r = 3 dan n = 5 maka kombinasi-3 dari 5 huruf ABCDE adalah

Jadi banyaknya kombinasi-3 dari 5 huruf ABCDE adalah 10.2. Berapa banyak cara memilih sebuah panitia yang terdiri dari 4 orang, dengan kandidat sebanyak 6 orang ?? Penyelesaian Karena panitia yang terdiri dari 4 orang merupakan susunan yang tidak terurut, maka masalah ini merupakan kombinasi-4 dari 6 unsur yang tersedia. Sehingga dengan mengunakan rumus kombinasi-r dimana n = 6 dan r = 4 diperoleh:

Jadi terdapat 15 cara untuk membentuk sebuah panitia yang terdiri dari 4 orang bisa dipilih dari 6 orang. 4. Permutasi dan Kombinasi Multi HimpunanPermutasi dan kombinasi multi himpunan di terapkan untuk menghitung pengaturan (atau pengurutan) n buah objek dari himpunan ganda S (himpunan S terdiri dari n buah objek yang tidak perlu semuanya berbeda). Dengan persamaannya adalah sebagai berikut :

11

Matematika Diskrit 2011/2012Persamaan permutasi disebut permutasi bentuk umum (Generalized Permutation).

Persamaan kombinasi disebut kombinasi bentuk umum (Generalized Combination).

Contoh Soal Permutasi dan Kombinasi Multi Himpunan:Berapa banyak cara untuk menyusun kembali huruf – huruf dari kata KAKIKUKAKU ?Penyelesaian S = {K,A,K,I,K,U,K,A,K,U}Huruf K = 5 buah (n1)Huruf A = 2 buah (n2)Huruf U = 2 buah (n3)Huruf I = 1 buah (n4)n = 5+2+2+1 = 10 buah. Penyelesaian Cara-1 :

Penyelesaian Cara-2 :

5. Koefisien BinomialKoefisien binomial merupakan bilangan-bilangan yang muncul dari hasil penjabaran penjumlahan dua peubah yang dipangkatkan, misalkan (x + y)n . Yang dalam hal ini, n adalah bilangan bulat.12


Segitiga Pascal :(x + y)0 = 1(x + y)1 = x + y(x + y)2 = x2+2xy+y2 (x + y)3 = x3+3 x2y+3xy2+y3(x + y)4 = x4+4x3y+6x2y2+4xy3+y4(x + y)5 = x5+5x4y+10x3y2+10x2y3+5xy4+y5

Aturan untuk menjabarkan bentuk perpangkatan (x + y)n adalah : 1. Suku pertama adalah xn, sedangkan suku terakhir yn 2. Pada setiap suku berikutnya, pangkat x berkurang satu sedangkan pangkat y bertambah satu.untuk setiap suku, jumlah pangkat x dan y adalah n.3. Koefisien untuk xn-kyk , yaitu suku ke-(k+1), adalah C(n,k). Bilangan C(n,k) disebut koefisien binomialDari Aturan diatas dapat disimpulkan bahwa :(x+y)n= C(n,0)xn + C(n,1)xn-1y1+...+ C(n,k)xn- kyk+...+C(n,n)yn

=

Contoh soal Koefisien Binomial Jabarkan (x+y)4 ?Penyelesaian (x + y)4 = C(4,0)x4-0y0 + C(4,1)x4-1y1 + C(4,2)x4-2y2 + C(4,03)x4-3y3 + C(4,4)x4-4y4

= x4 + 4x3y + 6x2y2 + 4xy3 + y4

13

Matematika Diskrit 2011/2012Perhatikan sifat-sfat yang timbul dari penjabaran tersebut:1. Banyaknya suku adalah (n+1) = 6+1 = 7.2. Jumlah dari eksponen a dan b dalam setiap suku adalah n.

6. Koefisien Multinomial Multinomial merupakan perluasan dari Binomial. Multinomial adalah jumlahan t buah suku berbeda, yaitu x1 + x2 + ..... + xt. Binomial merupakan kasus khusus dari multinomial, yakni untuk t = 2.Teorema multinomial adalah rumus penjabaran (x1 + x2 + ..... + xt)n. Secara formal, teorema multinomial adalah sebagai berikut : Misalkan x1, x2, ..... , xt adalah bilangan – bilangan riil dan n adalah bilangan bulat positif. Dengan demikian, ¿Penjumlahan dilakukan terhadap semua q1, q2, ... , qt dengan q1 + q2 + ... + qt = n.

Banyaknya suku pada ¿ adalah C ( n+t−1n ).Contoh soal Koefisien MultinomialHitunglah koefisien dari : a. x12 x3❑x 43 x54 dalam ekspresi ¿b. x3 y3 z2 dalam ekspresi ¿Ada berapa banyak suku dalam ekspresi – ekspresi tersebut?Penyelesaian

a. Koefisien x12 x3❑x 43 x54 adalah 10!2!0 !1 !3 !4 !

=¿ 1260014


Banyak suku C (10+5−110 )=1001b. Misal x1 = 2x; x2 = -3y; dan x3= 5z, Maka (2x – 3y + 5z)8 = (x1 + x2 + x3)8

Koefisien x13 x23 x32 adalah 8 !3!3 !2 !

=560 sehingga koefisien x3y3z2 adalah (2)3(-3)3(5)2.560 = -3.024.000Banyak suku = C ( 8+3−18 )=45

Teori GrafMakalah pertama tentang teori graf ditulis pada tahun 1736 oleh seorang matematikawan Swiss yang bernama Leonard Euler. Ia menggunakan teori graf untuk menyelesaikan masalah jembatan Königsberg (sekarang, bernama Kaliningrad). Berikut adalah ilustrasi masalah tersebut :

Gambar 1. Masalah Jembatan Königsberg (Rossen, 2003)Masalah yang dikemukakan Euler : Dapatkah melewati setiap jembatan tepat sekali dan kembali lagi ke tempat semula? Berikut adalah sketsa yang merepresentasikan ilustrasi jembatan Königsberg yang pada gambar diatas. Himpunan titik yaitu {A, B, C, D} merepresentasikan sebagai daratan, dan garis 15

Matematika Diskrit 2011/2012yang menghubungkan titik-titik tersebut adalah sebagai jembatan

Gambar 2. Representasi graf masalah jembatan KönigsbergJawaban pertanyaan Euler adalah tidak mungkin. Agar bisa melalui setiap jembatan tepat sekali dan kembali lagi ke tempat semula maka jumlah jembatan yang menghubungkan setiap daratan harus genap. 1. Pengertian Graf Graf adalah suatu diagram yang memuat informasi tertentu jika diinterprestasikan secara tepat. Tujuannya adalah sebagai visualisasi objek – objek agar lebih mudah dimengerti. Tiap – tiap diagram memuat sekumpulan objek (kotak, titik, dan lain – lain) beserta garis – garis yang menghubungkan objek – objek tersebut. Representasi visual dari graf adalah menyatakan objek dinyatakan sebagai noktah, bulatan, atau titik, sedangkan hubungan antara objek dinyatakan dengan garis.2. Dasar – Dasar GrafDefinisi 1

16

Matematika Diskrit 2011/2012Suatu graf terdiri dari 2 himpunan yang berhingga, yaitu himpunan titik – titik tidak kosong (simbol V(G)) dan himpunan garis – garis (simbol E(G)).Graf G didefinisikan sebagai pasangan himpunan (V, E), di tulis dengan notasi G = (V, E), yang dalam hal ini V adalah himpunan tidak-kosong dari simpul – simpul (vertice and node) dan E adalah himpunan sisi (edges and arcs) yang menghubungkan sepasang simpul. Definisi di atas menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada, minimal satu. Graf yang hanya mempunyai satu buah simpul tanpa sebuah sisi dinamakan Graf Trivial.Graf dinyatakan dengan gambar. Gambar suatu Graf G terdiri dari himpunan titik – titik atau simpul V(G), himpunan garis – garis atau sisi yang dinyatakan dengan E(G) yang menghubungkan titik tersebut (beserta arah garis pada graf berarah), dan label pada garisnya (jika ada). Simpul pada graf dapat dinomori dengan huruf, seperti a, b, c, …., v, w, … dengan bilangan asli 1, 2, 3, … , atau gabungan dari keduanya. Sedangkan sisi yang menghubungkan simpul u dengan simpul v dinyatakan dengan pasangan (u,v) atau dinyatakan dengan lambang e1, e2, … Dengan kata lain, jika e adalah sisi yang menghubungkan simpul u dan v, maka e dapat di tulis sebagai e = (u,v)

17

Matematika Diskrit 2011/2012Secara geometri graf di gambarkan sebagai sekumpulan noktah (simpul) yang di hubungkan dengan sejumlah garis. Dan berikut adalah beberapa contoh Graf.

Setiap garis berhubungan dengan satu atau dua titik. Titik – titik tersebut dinamakan Titik Ujung. Garis yang hanya berhubungan dengan satu titik ujung disebut Loop. Dua garis berbeda yang menghubungkan titik yang sama disebut Garis Paralel. Dua titik dikatakan Berhubungan (adjacent) jika ada garis yang menghubungkan keduanya. Titik yang tidak memiliki garis yang berhubungan dengannya disebut Titik Terasing (Isolating Point) Graf yang tidak memiliki titik (sehingga tidak memiliki garis) disebut Graf Kosong.Perhatikan gambar berikut ini:

18


Gambar tesebut memperlihatkan tiga buah graf, G1, G2, dan G3.

19

G1 adalah graf dengan himpunan simpul V dan Himpunan sisi E adalah :V (G) = {1, 2, 3, 4}E (G) = {(1,2), (1,3), (2,3), (2,4), G2 adalah graf dengan himpunan simpul V dan Himpunan sisi E adalah :V (G) = {1, 2, 3, 4}E (G) = {(1,2), (2,3), (1,3), (1,3), (2,4), (3,4), (3,4)} Himp. Ganda.= {e1, e2, e3, e4, e5, e6, e7}

G3 adalah graf dengan himpunan simpul V dan Himpunan sisi E adalah :V (G) = {1, 2, 3, 4}E (G) = {(1,2), (2,3), (1,3), (1,3), (2,4), (3,4), (3,4), (3, 3)} Himp. Ganda = {e1, e2, e3, e4, e5, e6, e7, e8}


Pada G2, sisi e3 = (1,3) dan sisi e4 = (1,3) dinamakan Sisi Ganda (Multiple edges atau paralel adges) karena kedua simpul menghubungkan dua buah simpul yang sama, yaitu simpul 1 dengan simpul 3.Pada G3, sisi e8 = (3,3) dinamakan Gelang atau Kalang atau disebut juga sebagai Loop, karena dia berawal dan berakhir di simpul yang sama. Contoh soal Teori GrafAda 7 kota (A,..,G) yang beberapa diantaranya dapat dihubungkan secara langsung dengan jalan darat. Hubungan – hubungan langsung yang dapat dilakukan adalah sebagai berikut : A dengan B A dengan D B dengan DC dengan BE dengan FBuatlah graf yang menunjukan keadaan transportasi di 7 kota tesebut: PenyelesaianMisalkan kota – kota dianggap sebagai titik – titik. Dua titik / atau lebih dihubungkan dengan garis bila dan hanya bila ada jalan yang menghubungkan langsung kedua kota tersebut. Untuk itu keadaan transportasi dalam kota tersebut adalah sebagai berikut : 20


Dalam graf tersebut, e1 berhubungan dengan titik A dan B (keduanya disebut titik ujung e1). Titik A dan Bdikatakan berhubungan, sedangkan titik A dan C tidak berhubungan karena tidak ada garis yang menghubungkannya secara langsung.Titik G adalah titik terasing karena tidak ada garis yang berhubungan dengan G. 3. Jenis – Jenis GrafSisi pada graf dapat mempunyai orientasi arah, berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis : 1. Graf Tak Berarah , adalah graf yang sisinya tidak mempunyai orientasi arah disebut graf tak berarah. Pada graf tak – berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak di perhatikan. Jadi (u,v) = (v,u) adalah sisi yang sama.2. Graf Berarah , adalah graf yang setiap sisinya diberikan orientasi arah. Sisi berarah disebut sebagai arch (busur). Pada graf berarah, (u,v) dan (v,u) menyatakan dua buah busur yang berbeda. Untuk simpul (u,v), simpul u dinamakan simpul asal dan simpul v disebut sebagai Simpul Terminal.

21


4. Graf Tak Berarah (Undirected Graph)a. Graf Sederhana (Simple graf) adalah graf yang tidak mengandung Loop maupun Garis Paralel. Graf d bawah ini adalah contoh graf sederhana.

Pada graf sederhana, sisi adalah pasangan tak-terurut (Unordered Pairs). Jadi menuliskan sisi (u,v) sama saja dengan (v,u). Kita juga dapat mendeskripsikan graf sederhana G=(V,E) terdiri dari himpunan tidak kosong simpul-simpul dan E adalah himpunan pasangan tak-terurut yang berbeda yang disebut sisi. b. Graf tak sederhana (Unsimple-graph), adalah graf yang mengandung garis paralel atau Loop. Ada dua macam Graf tak sederhana, yaitu : 1. Graf Ganda (MultiGraph), adalah graf yang mengandung sisi ganda (garis paralel). Sisi ganda yang menghubungkan sepasang simpul bisa lebih dari dua buah.

22


2. Graf Semu (Pseudograph), adalah graf yang mengandung Loop. Contoh geaf di bawah ini disebut graf semu walaupun memiliki sisi ganda sekalipun.

Contoh SoalGambarlah sebuah graf sederhana yang dapat di bentuk dari 4 titik {a, b, c, d} dan 2 garis.PenyelesaianSebuah garis dalam graf sederhana selalu berhubungan dengan 2 titik. Oleh karena ada 4 titik, maka ada C(4,2) = 6 garis yang mungkin di buat. Yaitu garis – garis dengan titik ujung {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}.Dari keenam garis yang mungkin tersebut, selanjutnya dipilih 2 garis diantaranya. Jadi ada C(6,2) = 15 buah graf yang mungkin di bentuk dari 4 buah titik dan 2 buah garis.

23

Matematika Diskrit 2011/2012Jadi, 15 buah graf tersebut di gambarkan seperti gambar di bawah ini.

c. Graf Lengkap (Complete Graph) dengan n titik (simbol Kn) adalah graf sederhana dengan n titik, di mana setiap 2 titik berbeda dihubungkan dengan suatu garis.

Teorema 1Banyaknya garis dalam suatu graf lengkap dengan n titik adalah . Contoh soal Gambarlah K2, K3, K4, K5, K6 !Penyelesaian - K2

n = 2 2(2−1)2

=1

24

Matematika Diskrit 2011/2012Jadi banyak garisnya adalah 1, dan gambarnya adalah :

- K3

- K4

- K5

- K6

d. Komplemen GrafKomplemen suatu graf G (Simbol G ) dengan n titik adalah suatu graf sederhana dengan : 25

Matematika Diskrit 2011/20121. Titik – titik sama dengan titik – titik G. Jadi, V (G) = V(G).2. Garis – garis G adalah komplemen garis – garis G terhadap graf lengkapnya (Kn).

E (G )=E (K n )−E (G )Titik – titik yang dihubungkan dengan garis dalam G tidak terhubung dalam G. Sebaliknya, titik – titik yang terhubung dalam G menjadi tidak terhubung dalam G.Contoh soal Komplemen GrafGambarlah Komplemen graf G yang di definisikan dalam Gambar di bawah ini !

Penyelesaian : Titik – titik dalam G sama dengan titik – titik dalam G, sedangkan garis – garis dalam G adalah garis – garis yang tidak berada dalam G. Pada gambar (a), titik – titik yang tidak dihubungkan dengan garis dalam G adalah garis dengan titik – titik ujung {a,d}, {a,e}, {b,c}, dan {b,e}.Jadi graf G dapat digambarkan sebagai berikut :

Silakan gambarG graf untuk gambar (b) dan (c) ! e. Sub-Graf26

Matematika Diskrit 2011/2012Misalkan G adalah suatu graf. Graf H dikatakan sub-graf G bila dan hanya bila : a. V(H)⊆ V (G)b. E(H) ⊆ E (G)c. Setiap garis dalam H memiliki titik ujung yang sama dengan garis tersebut dalam G.Dari definisi di atas, ada beberapa hal yang dapat diturunkan : 1. Sebuah titik dalam G merupakan Sub-Graf G.2. Sebuah garis dalam G bersama- sama dengan titik – titik ujungnya merupakan sub-graf G. 3. Setiap graf merupakan subgraf dari dirinya.4. Dalam subgraf berlaku sifat transitif : Jika H adalah Subgraf G dan G adalah Subgraf K, maka K adalah subgraf K.Contoh Soal Sub-Graf: Perhatikan gambar di bawah ini, apakah H merupakan subgraf G ??

Apakah H merupakan Sub-Graf dari G? Penyelesaian: 27

Matematika Diskrit 2011/2012V (H) = {v2, v3} dan V (G) = {v1 , v2, v3} sehingga V(H) ⊆ V (G). E(H) = {e4} dan E(G)= {e1,e2, e3, e4} sehingga E(H)⊆ E (G). Garis e4 di H merupakan Loop pada v2 dan Garis e4 juga merupakan loop pada v2 di G. Dengan demikian, H merupakan subgraf G.

f. Derajat (Degree)Definisi Misalkan V adalah suatu titik dalam graf G. Derajat titik V (Simbol d(v)) adalah jumlah garis yang berhubungan dengan titik v dan garis suatu loop dihitung 2 kali. Derajat total G adalah jumlah derajat semua titik dalam G. Contoh Soal derajat: Tentukan derajat tiap – tiap titik dalam graf pada gambar di bawah ini !

Penyelesaian : 28

Matematika Diskrit 2011/2012d(v1) = 4 karena garis yang berhubungan dengan v1 adalah e2,e3 dan loop e1 yang dihitung dua kali.d(v2) = 2 karena garis yang berhubungan dengan v2 adalah e2 dan e3.d(v3) = d(v5) = 1 karena garis yang berhubungan dengan v3 dan v5 adalah e4. d(v4) = 2 karena garis yang berhubungan dengan v4 adalah loop e5 yang dihitung 2 kali.d(v6) = 0 karena tidak ada garis yang berhubungan dengan v6.Dan derajat total dari graf tersebut adalah :

∑i=1

6

d (v i )=4+2+1+2+1+0=10

Jadi, total derajatnya adalah 10.g. Path dan Sirkuit Misalkan G adalah suatu Graf, Misalkan pula v dan W adalah 2 titik dalam G.

Suatu walk dari v ke w adalah barisan titik – titik berhubungan dan garis secara selang – seling, diawali dari titik v dan di akhiri pada titik w. Walk dengan panjang n dari v ke w dituliskan sebagai berikut : v0 e1 v1 e2 v2 … vn-1 en vn dengn v0 = v; vn = w; vi-

1; dan vi adalah titik – titik ujung garis ei Path dengan panjang n dari v ke w adalah walk dari v ke w yang semua garisnya berbeda. Path dari v ke w dituliskan sebagai v = v0 e1 v1 e2 v2 …. Vn-1 en vn = w dengan ei ≠ ej.

29

Matematika Diskrit 2011/2012 Path sederhana dengan panjang n dari v ke w adalah path dari v ke w yang semua titiknya berbeda. Path sederhana dari v ke w berbentuk v = v0 e1 v1 e2 v2 …. vn-1 en vn = w dengan ei ≠ ej untuk i ≠ j dan vk ≠ vm untuk k ≠ m. Sirkuit dengan panjang n adalah path yang dimulai dan di kahiri pada titik yang sama. Sirkuit adalah path yang berbentuk v = v0 e1 v1 e2 v2 …. vn-1 en vn dengan v0 = vn Sirkuit sederhana dengan panjang n adalah sirkuit yang semua titiknya berbeda. Sirkuit sederhana berbentuk v0 e1 v1 e2 v2 …. vn-1 en vn dengan ei ≠ ej untuk i ≠ j dan vk ≠ vm untuk k ≠ m, kecuali v0 = vm

Definisi – definisi diatas dapat di gambarkan dengen menggunakan gambar berikut ini :

30

Walk v → wv = v0 e1 v1 e2 v2 …. vn-1 en vn = wvi-1 dan vi adalah titik – titik garis ujung garis e1

Path Sederhana Sirkuit

PathSemua garis berbeda

Titik awal dan titik akhir sama (V0 = Vn)Semua titik berbeda

Titik awal dan titik akhir sama (V0 = Vn) Semua titik berbedakecuali (V0 = Vn)


Contoh Soal Path dan Sirkuit: Tentukan mana di antara barisan titik dan garis pada gambar di bawah ini yang merupakan walk, path, path sederhana, sirkuit dan sirkuit sederhana.

a. v1 e1 v2 e3 v3 e4 v3 e5 v4b. v1 e1 v2 e3 v3 e5 v4 e5 v3 e6 v5c. v2 e3 v3 e5 v4 e10 v5 e6 v3 e7 v6 e8 v2d. v2 e3 v3 e5 v4 e10 v5 e9 v6 e8 v2e. v1 Penyelesaian:a. Garis yang muncul adalah (e1, e3, e4, dan e5) dan semua garis yang muncul berbeda. Lalu titik yang muncul adalah (v1, v2, v3, v3 dan v4) dan titik v3 muncul 2 kali. Titik awal dan titik akhir tidak sama. Disimpulkan bahwa barisan tersebut adalah Path dari v1 ke v4 dengan panjang 4.

31

Sirkuit Sederhana

Matematika Diskrit 2011/2012b. Ada garis yang muncul lebih dari sekali, yaitu e5 (muncul 2 kali) berarti barisan tersebut merupakan Walk dari v1 ke v5 dengan panjang 5.c. Semua garis berbeda. Ada titik berulang (v3 muncul 2 kali). Titik awal dan titik akhirnya sma, yaitu v2. Barisan tersebut merupakan Sirkuit dengan panjang 6.d. Semua garis dan titiknya berbeda. Barisan diawali dan diakhiri pada titik yang sama yaitu v2. Disimpulkan barisan tersebut adalah Sirkuit Sederhana dengan panjang 5. e. Oleh karena barisan hanya memuat satu titik saja, berarti tidak ada garis yang sama. Barisan di awali dan di akhiri pada titik yang sama serta tidak memiliki titik yang sama diantaranya. Dengan demikian disimpulkan bahwa barisan tersebut merupakan sirkuit sederhana (sering kali disebut sirkuit Trivial).

h. Graf terhubung dan tidak terhubungMisalkan G adalah suatu graf.• Dua titik v dan w dalam G dikatakan tehubung bila dan hanya bila ada walk dari v ke w.• Graf G dikatakan terhubung bila dan hanya bila setiap dua titik dalam G terhubung. • Graf G dikatakan tidak terhubung bila dan hanya bila ada 2 titik dalam G yang tidak terhubung. Contoh soal : Manakah di antara graf pada gambar di bawah ini yang merupakan graf terhubung ?

32


Penyelesaian: a. Graf (a) merupakan graf terhubung karena ada walk yang bisa menghubungkan keseluruhan titik dan garis yang ada di dalam graf tersebut. b. Graf (b) merupakan graf tak terhubung karena tidak ada walk dari v5 ke v4.c. Graf (c) merupakan graf tak terhubung karena tidak ada walk dari titik v2 ke v3.d. Graf (d) merupakan graf terhubung. 5. Graf Berarah (Direction Graph = Digraph)Suatu graf berarah G terdiri dari :

Himpunan titik – titik V(G): {v1, v2, … }, himpunan garis – garis E(G): {e1, e2, … }, dan suatu fungsi g yang mengawankan setiap garis dalam E(G) ke suatu pasangan berurutan titik (vi,vj). 33

Matematika Diskrit 2011/2012 Jika ek = (vi,vj) adalah suatu garis dalam G, maka vi disebut titik awal ek dan vj disebut titik akhir vk. arah garis adalah dari vi ke vj. Jumlah garis yang keluar dari titik vi disebut derajat keluar (out degree), titik vi (simbol d+(vi)), sedangkan jumlah garis yang menuju ke titik vi disebut derajat masuk (in degree) titik vi (simbol d- (vi)). Titik terasing adalah titik dalam G di mana derajat keluar dan derajat masuknya adalah 0. Titik pendan adalah titik di mana jumlah derajat masuk dan jumlah derajat keluarnya adalah 1. Dua garis berarah dikatakan paralel jika keduanya memiliki titik awal dan titik akhir yang sama, Contoh Soal:

Tentukan:a. Himpunan titik – titik, himpunan garis – garis dan fungsi perkawanan g;b. Derajat masuk dan derajat keluar tiap – tiap titik;c. Titik terasing dan titik pendan;d. Garis paralel. Penyelesaian: a. Himpunan titik – titik V(G) = {v1, v2, v3, v4, v5, v6}34

Matematika Diskrit 2011/2012Himpunan garis – garis E(G) = {e1, e2, e3, e4, e5, e6, e7, e8, e9}Fungsi perkawanan g : e1 dengan (v1, v2) e6 dengan (v3, v4)e2 dengan (v4, v1) e7 dengan (v3, v5)e3 dengan (v1, v4) e8 dengan (v5, v4)e4 dengan (v1, v3) e9 dengan (v5,v4)e5 dengan (v3,v3)b. d+(v1) = 3 ; d-(v1) = 1d+(v2) = 0 ; d-(v2) = 1d+(v3) = 3 ; d-(v3) = 2d+(v4) = 1 ; d-(v1) = 4d+(v5) = 2 ; d-(v1) = 1d+(v6) = 0 ; d-(v6) = 0c. Titik terasing adalah titik v6. titik pendan adalah v2d. Garis paralel adalah e8 dan e9

a. Path Berarah dan Sirkuit BerarahPengertian walk, path dan sirkuit dalam graf berarah sama dengan pengertian dalam graf tak berarah. Hanya saja dalam graf berarah suatu perjalanan harus mengikuti arah garis. Untuk membedakan dengan graf berarah dan graf tak berarah, maka walk, path, dan sirkuit dalam graf berarah disebut walk berarah, path berarah, dan sirkuit berarah. Suatu graf berarah yang tidak memuat sirkuit berarah disebut Asiklik. b. Graf Berarah Terhubung

35

Matematika Diskrit 2011/2012Suatu graf tak berarah dikatakan terhubung jika ada walk yang menghubungkan tiap 2 titiknya. Pengertian itupun berlaku untuk graf berarah. Berdasarkan arah garisnya, dalam graf berarah dikenal 2 jenis keterhubungan, yaitu terhubung kuat dan terhubung lemah. Misalkan G adalah suatu Graf berarah dan v,w adalah sembarang 2 titik dalam G. G disebut terhubung kuat jika ada path berarah dari v ke w. G disebut terhubung lemah, jika G tidak terhubung kuat, tetapi graf tak berarah yang bersesuaian dengan G terhubung.

Contoh Soal :

Manakah di antara graf – graf tersebut yang terhubung kuat dan terhubung lemah? Penyelesaian:36

Matematika Diskrit 2011/2012Dalam G1, setiap 2 titik dapat dihubungkan dengan path berarah sehingga graf berarah G1 adalah graf terhubung kuat.Sebaliknya dalam G2, tidak ada path berarah yang menghubungkan v4 ke v3. Akan tetatpi, jika semua garis dihilangkan (sehingga G2 menjadi Graf tidak berarah), maka G2 merupakan graf yang terhubung. Jadi, G2 merupakan graf terhubung lemah.

6. Representasi Graf dalam Matriks1. Matriks Hubung (Adjacency Matrix)Misalkan G adalah graf tak berarah dengan titik – titik v1 v2 .. vn (n berhingga). Matriks hubung yang sesuai dengan graf G adalah matriks A = (aij) dengan aij = jumlah garis yang menghubungkan titik vi dengan titik vj; i,j = 1,2, ... , n.Oleh karena dalam graf tak berarah jumlah garis yang menghubungkan titik vi dan titik vj selalu sama dengan jumlah garis yang menghubungkan vj dengan vi, maka jelaslah bahwa matriks hubungnya selalu merupakan matriks yang simetris (aij = aji ∀ i,j)

Contoh Soal:

37

Matematika Diskrit 2011/2012Nyatakan graf di bawah ini kedalam matriks hubung !

Penyelesaian: Graf A memiliki 4 buah titik, jadi matriksnya adalah sebagai berikut : V1 V2 V3 V4 V1 0 0 1 1 V2 0 0 2 0 V3 1 2 0 0 V4 1 0 0 1

Matriks hubung dapat dipakai untuk menghitung banyaknya kemungkinan walk dengan panjang tertentu antara 2 titik. Dalam hal ini yang dapat dihitung adalah banyaknya kemungkinan walk, dan bukan walknya sendiri. Misalkan A = (aij) adalah matriks hubung graf G. Misalkan pula An adalah hasil kali matriks A dengan dirinya sendiri sebanyak n kali.Banyaknya kemungkinan walk dengan panjang n dari titik vi ke titik vj adalah elemen aij pada matriks An (=aijn)38

Matematika Diskrit 2011/2012Contoh Soal : Hitunglah walk dengan panjang 2 dari titk v1 ke titik v1.

Penyelesaian : Matriks hubung yang sesuai dengan graf tersebut adalah: V1

V2 V3

V1 1 1 2 V2 1 0 1 V3 2 1 0

Untuk menghitung jumlah walk dengan panjang 2 yang mungkin dilakukan, terlebih dahulu dihitung A2 1 1 2 1 1 2 6 3 3 A2 = 1 0 1 x 1 0 1 = 3 2 2 2 1 0 2 1 0 3 2 5

Jumlah walk dari v1 ke v1 dengan panjang 2 yang dapat dilakukan adalah elemen A211, yaitu 6 buah.

39

1Jika titik vi berhubungan dengan garis ej 0Jika titik vi tidak berhubungan dengan garis ej aij =


2. Matriks Biner (Incidence Matrix)Misalkan G adalah graf tanpa loop dengan n titik v1, v2, .. , vn dan k garis e1, e2, .. ek.Matriks biner yang sesuai dengan graf G adalah matriks A berukuran n x k yang elemennya adalah :

Sesuai namanya, matriks biner hanya berisi bilangan 0 atau 1 saja.Contoh soal : Nyatakan Graf di bawah ini kedalam sebuah matriks biner!

Penyelesaian: Ada 6 titik dan 8 garis dalam graf tersebut, maka matriksnya terdiri dari 6 baris dan 8 kolom. Matriksnya adalah sebagai berikut:e1 e2 e3 e4 e5 e6 e7 e8 V1 1 0 0 0 0 1 0 0 V2 1 1 1 1 0 0 0 0

40

1Jika sirkuit ke-i memuat garis ke-j 0Jika sirkuit ke-i tidak memuat garis ke-j aij =

Matematika Diskrit 2011/2012V3 0 1 0 0 0 0 0 0 V4 0 0 1 0 1 0 1 1 V5 0 0 0 1 1 1 0 0 V6 0 0 0 0 0 0 1 1

3. Matriks SirkuitMisalkan G adalah graf yang memuat q buah sirkuit sederhana dan e buah garis. Matriks sirkuit A = (aij) yang bersesuaian dengan G adalah matriks yang terdiri dari q baris dan e kolom dengan elemen :

Contoh soal : Nyatakan Graf di bawah ini kedalam sebuah matriks sirkuit!

Penyelesaian : Graf tersebut terdapat 8 garis dan terdapat 4 buah sirkuit sederhana, yaitu : S1 = e7 e8 S2 = e3 e4 e6S3 = e1 e4 e6

41

1Jika ada garis dari titik vi ke titik vj 0Jika tidak ada garis dari titik vi ke titik vj aij =

Matematika Diskrit 2011/2012S4 = e1 e3 e5 e6 Dengan demikian, matriks sirkuit yang sesuai terdiri dari 4 baris dan 8 kolom.

e1 e2 e3 e4 e5 e6 e7 e8 s1 0 0 0 0 0 0 1 1 s2 0 0 1 1 1 0 0 0 s3 1 0 0 1 0 1 0 0 s4 1 0 1 0 1 1 0 0

7. Representasi Graf berarah dalam Matriks 1. Matriks Hubung Misalkan G adalah graf berarah yang terdiri dari n titik tanpa garis paralel. Matriks hubung yang sesuai dengan Graf G adalah matriks bujur sangkar n x n A=(aij) dengan

Contoh soal: Nyatakan graf dibawah ini kedalam matriks hubung.

42


Penyelesaian: Graf tersebut terdiri dari 6 titik (v1 ... v6) sehingga matriks hubungnya adalah matriks bujur sangkar 6 x 6. jadi bentuk matriksnya adalah : V1 V2 V3 V4 V5 V6

V1 0 1 0 0 0 0 V2 0 0 0 1 1 0 V3 0 1 0 0 0 0 V4 0 0 0 0 0 1 V5 1 0 0 1 0 0 V6 0 0 0 1 0 0

2. Matriks SirkuitMisalkan G adalah graf berarah dengan e buah garis dan q buah sirkuit atau sirkuit berarah. Sembarang arah orientasi (searah / berlawanan dengan arah jarum jam) diberikan ke tiap – tiap sirkuit. Matriks sirkuit yang bersesuaian dengan graf G adalah matriks A =(aij) dengan

43

1 Jika sirkuit ke-i memuat garis ke – j dan arah garis ke – j sama dengan arah orientasi -1 Jika sirkuit ke-i memuat garis ke – j dan arah garis ke – j berlawanan dengan arah orientasi

aij =

0 Jika sirkuit ke-i tidak memuat garis ke – j

Matematika Diskrit 2011/2012Perbedaan matrik sirkuit untuk menyatakan graf berarah dan tidak berarah terletak pada tanda negatif pada elemen matriks, yang menyatakan bahwa garis yang bersesuaian memiliki arah yang berlawanan dengan arah yang orientasi yang didefinisikan. Orientasi yang diberlakukan pada setiap sirkuit dapat dibuat sembarang sehingga suatu graf berarah dapat dinyatakan dengan beberapa matriks sirkuit berbeda.

Contoh Soal : Nyatakan Graf Berarah di bawah ini dengan matriks Sirkuit !

Penyelesaian: Ada 4 sirkuit pada graf tersebut, masing – masing sirkuit itu adalah S1 = v4 v6 v4S2 = v2 v4 v5 v2S3 = v1 v2 v5 v1S4 = v1 v2 v4 v5 v1Misalkan orientasi yang dipilih pada s2 dan s3 sesuai dengan arah jarum jam, sedangkan pada s1 dan s4

44

Matematika Diskrit 2011/2012berlawanan dengan arah jarum jam. Dengan demikian, matriks sirkuitnya adalah :

e1 e2 e3 e4 e5 e6 e7 e8s1 0 0 0 0 0 0 1 1s2 0 0 1 -1 0 -1 0 0s3 1 0 0 1 1 0 0 0s4 -1 0 -1 0 -1 1 0 08. Pohon 1. Pohon dan Hutan Misalkan G adalah suatu Graf Sederhana (tidak memiliki Loop dan Garis Paralel). G disebut Pohon bila dan hanya bila G tidak memuat sirkuit dan terhubung.Pohon semu (Trivial Tree) adalah pohon yang hanya terdiri dari sebuah titik. Pohon kosong (Empty Tree) adalah pohon yang tidak meiliki titik. G disebut hutan (Forest) bila dan hanya bila G tidak memuat sirkuit.Contoh soal : Tentukan mana diantara graf – graf dibawah ini yang merupakan pohon atau hutan!

45


Penyelesaian : a. Gambar (a) merupakan Pohon, karena gambar tersebut tidak memiliki sirkuit dan merupakan graf yang terhubung;b. Gambar (b) merupakan pohon;c. Gambar (c) bukan merupakan pohon maupun hutan, karena terdapat sirkuit yakni dari titik v3 v4 v5 v3, dan juga merupakan graf terhubung.d. Gambar (d) merupakan Hutan, karena bukan merupakan Graf terhubung.Misalkan T adalah suatu Pohon. Daun (Leaf / Terminal vertex) adalah titik dalam T yang berserajat 1. Titik dalam T yang berderajat > 1 disebut titik cabang (Branch / Interval Vertex).

Contoh Soal: Tentukan daun dan titik cabang pohon pada gambar di bawah ini.

46


Penyelesaian : - Titik v4, v5, v6, v7, v8 derajatnya = 1, jadi titik – titik tersebut merupakan Daun.- Titik v1, v2, v3 derajatnya masing – masing >1, maka titik – titik tersebut merupakan titik cabang.2. Pohon Berakar Pohon berakar (Rooted Tree) adalah suatu pohon dimana ada satu titik yang dikhususkan dari yang lain. Titik ini disebut akar (root).Tingkat (level) suatu titik adalah banyaknya garis antara titik tersebut dengan akar. Tinggi (height) pohon adalah tingkat maksimum yang dimiliki oleh titik – titik pohon.Anak (children) dari titik v adalah semua titik yang berhubungan langsung dengan v, tetapi memiliki tingkat yang lebih tinggi dari v. Jika w adalah anak dari v, maka v disebut orang tua (parent) dari w. Dua titik yang memiliki orang tua yang sama disebut saudara (sibling). Contoh soal : Perhatikan gambar di bawah ini!

47


a. Tentukan tingkat tiap – tiap titik jika akarnya adalah V2!b. Berapa tinggi pohon jika akarnya adalah V2?c. Tentukan anak, orang tua, dan saudara titik V1 jika akarnya adalah V2.d. Apakah pertanyaan a – c memiliki jawaban yang berbeda jika akarnya adalah v1? Penyelesaian: Gambar Pohon dengan akar v2 adalah sebagai berikut :

a. Tingkat titik v1 = v4 = v5 = v6 = 1Tingkat titik v3 = 2Tingkat titik v7 = v8 = 3b. Tinggi pohon = 3c. Anak v1 = v3 ; orang tua v1 = v2; saudara v1 = v4 v5 v6d. Gambar pohon dengan akar v1

48


Tingkat titik v2 = v3 = 1Tingkat titik v4=v5=v6=v7=v8=2Tinggi pohon = 2Anak v1 = v2 v3; orang tua dan saudara v1 tidak ada karena v1 merupakan akar.3. Pohon Biner Pohon biner (Binary Tree) adalah pohon berakar yang setiap titiknya memiliki paling banyak 2 anak, yang disebut Anak Kiri (Left Child) dan Anak Kanan (Right Child);Pohon Biner Penuh (Full Binary Tree) adalah pohon biner yang setiap titiknya memiliki tepat 2 anak. Pohon biner banyak digunakan dalam ilmu komputer untuk menyatakan ekspresi aljabar maupun untuk pencarian dan pengurutan data (searching and shorting). Untuk menyatakan ekspresi aljabar dalam pohon biner, dilakukan cara berikut : Setiap operand / operator dalam ekspresi aljabar besesuaian dengan satu titik dalam pohon biner. Kedua operand dalam ekspresi biner merupakan anak dari operatornya. Contoh :

49

Matematika Diskrit 2011/2012Nyatakan ekspresi aljabar x / y kedalam bentuk pohon biner !

4. Pohon RentangPohon Rentang (Spaning Tree) suatu graf terhubung G adalah Subgraf G yang merupakan pohon yang memuat semua titik dalam G. Contoh : Carilah semua pohon rentang yang mungkin dibuat dari graf G yang tampak pada gambar dibawah ini.

Penyelesaian : Di dalam graf tersebut terdapat satu buah sirkuit, yakni sirkuit dari titik v1 v2 v5 v4 v1, karena pohon merupakan graf yang tidak memiliki sirkuit dan pohon rentang adalah subgraf yang harus melibatkan semua titik dalam G, jadi pohon rentang dari Graf tersebut di atas adalah sebagai berikut:

50


51

modul matematika diskrit.docx

Documents