Struktur Diskrit DRAF [PDF]

Citation preview

NAMA :SAFRI ZAL ALFARABI NIM



:219280010



KELAS :TEKNIK INFORMATIKA A



Tugas Mandiri Mata Kuliah Struktur Diskrit



Pokok Bahasan : GRAF DEFENISI 







Graf merupakan struktur diskrit yang terdiri himpunan sejumlah berhingga obyek yang disebut simpul (vertices,vertex) dan himpunan sisi (edges) yang menghubungkan simpul-simpul tersebut.Terdiri dari Graf digunakan untuk merepresentasikan objekobjek diskrit dan hubungan antara objek-objek tersebut. Notasi sebuah graph adalah G = (V,E) dimana;  V merupakan himpunan tak kosong dari simpul-simpul (vertices), misalkan V = {v1,v2, …..,vn}  E merupakan himpunan sisi-sisi (edges) yang menghubungkan sepasang simpul,misalkan E = {e1,e2,…,en}.



JENIS-JENIS GRAF Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf maka graf digolongkan menjadi dua jenis: 1. Graf sederhana (simple graph)



Graf yang tidak mengandung gelang maupun sisi ganda dinamakan graf sederhana. 2.Graf tak-sederhana (unsimple graph



Graf tak sederhana



Graf Semu



Graf yang mengandung sisi ganda atau gelang dinamakan graf tak sederhana (unsimple graph). Ada dua macam graf tak sederhana, yaitu graf ganda (multigraph) atau graf semu (pseudograph). Graf ganda adalah graf yang mengandung sisi ganda. Graf semu adalah graf yang mengandung gelang (loop). Jumlah simpul pada graf disebut sebagai kardinalitas graf, dan dinyatakan dengan n = |V|, dan jumlah sisi kita nyatakan dengan m = |E| Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis : 1. Graf tak-berarah (undirected graph)



Graf yang sisinya tidak mempunyai orientasi arah disebut tak-berarah. Pada graf tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi, (u, v) = (v, u) adalah sisi yang sama. 2. Graf berarah (directed graph atau digraph)



Graf berarah



Graf Ganda berarah



Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Pada graf berarah, (u, v) dan (v, u) menyatakan dua buah busur yang berbeda, dengan kata lain (u, v)   (v, u). Untuk busur (u, v) simpul u dinamakan simpul asal (initial vertex) dan simpul v dinamakan simpul terminal (terminal vertex). Definisi graf dapat diperluas sehingga mencakup graf-ganda berarah (directed multigraph). Pada graf-ganda berarah, gelang dan sisi ganda diperbolehkan ada. Terminologi Graf 1 e2 2



e



e1



3 4



2



e4



1 3



·5



3



e5



2



3



4



G1



G2



G3



1. Ketetanggaan (Adjacent) Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung. Tinjau graf G1 : simpul 1 bertetangga dengan simpul 2 dan 3, simpul 1 tidak bertetangga dengan simpul 4 2. Bersisian (Incidency) Untuk sembarang sisi e = (vj, vk) dikatakan e bersisian dengan simpul vj , atau e bersisian dengan simpul vk Tinjau graf G1: sisi (2, 3) bersisian dengan simpul 2 dan simpul 3, sisi (2, 4) bersisian dengan simpul 2 dan simpul 4,tetapi sisi (1, 2) tidak bersisian dengan simpul 4. 3. Simpul Terpencil (Isolated Vertex) Simpul terpencil ialah simpul yang tidak dengannya.



mempunyai



sisi



yang bersisian



Tinjau graf G3: simpul 5 adalah simpul terpencil. 4.Graf Kosong (null graph atau empty graph) Graf yang himpunan sisinya merupakan himpunan kosong (Nn). Graf N5 : ·1 4·



·5



·2



·3 5.Derajat (Degree) Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut. Notasi: d(v) Tinjau graf G1:d(1) = d(4) = 2 d(2) = d(3) = 3



Tinjau graf G3: d(5) = 0



®



simpul terpencil



d(4) = 1



®



simpul anting-anting (pendant vertex)



Tinjau graf G2: d(1) = 3



®



bersisian dengan sisi ganda



d(2) = 4



®



bersisian dengan sisi gelang (loop)



6. Lintasan(path) Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2,... , vn – 1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), ... , en = (vn-1, vn) adalah sisi-sisi dari graf G. Tinjau graf G1: lintasan 1, 2, 4, 3 adalah lintasan dengan barisan sisi (1,2),(2,4),(4,3). Panjang lintasan adalah jumlah sisi dalam lintasan tersebut. Lintasan 1, 2, 4, 3 pada G1 memiliki panjang 3. 7.Siklus (Cycle) atau Sirkuit (Circuit) Lintasan yang berawal disebut sirkuit atau siklus.



dan



berakhir



pada



simpul yang



sama



Tinjau graf G1: 1, 2, 3, 1 adalah sebuah sirkuit. Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut. Sirkuit 1, 2, 3, 1 pada G1 memiliki panjang 3 8.Terhubung (Connected) Dua buah simpul v1 dan simpul v2 disebut terhubung jika terdapat lintasan dari v1 ke v2. G disebut graf terhubung (connected graph) jika untuk setiap pasang simpul vi dan vj dalam himpunan V terdapat lintasan dari vi ke vj. Jika tidak, maka G disebut graf tak-terhubung (disconnected graph). 9. Upagraf Rentang (Spanning Subgraph) Upagraf G1 = (V1, E1) dari G = (V, E) dikatakan upagraf rentang jika V1 =V (yaitu G1 mengandung semua simpul dari G). 1



1



2



3



2



3



4



5



4



5



a).graf G



b). upagraf rentang dari G



1



2



3 c). bukan upagraf rentang dari G



10. Upagraf(Subgraph) dan Komplemen Upagraf Misalkan G = (V, E) adalah sebuah



graf. G1 = (V1, E1) adalah



upagraf (subgraph) dari G jika V1 Í V dan E1 Í E. Komplemen dari upagraf G1 terhadap graf G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = E - E1 dan V2 adalah himpunan simpul yang anggota-anggota E2 bersisian dengannya. 11.Cut-set Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen. Pada graf di bawah, {(1,2), (1,5), (3,5), (3,4)} adalah cut-set.Terdapat banyak cut-set pada sebuah graf terhubung. Himpunan {(1,2), (2,5)} juga adalah cut-set, {(1,3), (1,5), (1,2)} adalah cut-set, {(2,6)} juga cut-set, tetapi {(1,2), (2,5), (4,5)} bukan cut-set sebab himpunan bagiannya, {(1,2), (2,5)} adalah cut-set. 1



2



1



5



3



6



2



5



4



3



6 4



12. Graf Berbobot (Weighted Graph) Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot). a 10



12



e



8



b



15



11



9



d



14



c



GRAF KHUSUS a.Graf Lengkap (Complete Graph) Graf lengkap adalah graf sederhana yang setiap dua simpulnya bertetangga. Graf lengkap dengan n buah simpul dilambangkan dengan Kn. Setiap simpul pada Kn berderajat n – 1. Banyaknya rusuk pada graf lengkap yang terdiri dari n buah simpul adalah n(n – 1)/2. b.Graf Lingkaran



Graf lingkaran adalah graf sederhana yang setiap simpulnya berderajat dua. Graf lingkaran dengan n simpul dilambangkan dengan Cn.



Gambar 2.9 Graf Lingkaran C3 dan C4 C.Graf Teratur (Regular Graph) ` Graf teratur adalah graf yang setiap simpulnya mempunyai derajat yang sama. Apabila derajat setiap simpul adalah r, maka graf tersebut disebut sebagai graf teratur derajat r.



Gambar 2.10 Graf Teratur Derajat 3 d.Graf Bipartit (Bipartite Graph) Graf G yang himpunan simpulnya dapat dikelompokkan menjadi dua himpunan bagian V1 dan V2, sedemikian sehingga setiap rusuk di dalam G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2 disebut graf bipartit dan dinyatakan sebagai G (V1, V2).



Contoh/Kasus Graf 1. Dalam sebuah pesta, lima orang saling berjabat tangan. Tiap orang hanya berjabat tangan satu kali dengan orang lainnya. Hitung jumlah jabat tangan yang terjadi dan modelkan dalam graf. penyelesaian Graf berikut merepresentasikan jabat tangan yang terjadi. Titik mewakili orang, sedangkan sisi mewakili jabat tangan. Jumlah jabat tangan diwakili oleh jumlah sisi pada graf tersebut, yaitu 4+3+2+1=104+3+2+1=10. 2. Periksalah apakah barisan (4 4 3 3 2) merupakan grafik atau bukan. Penyelesaian: Perhatikan bahwa banyaknya bilangan pada S=4 4 3 3 2 adalah 5. Jelas bahwa n=5≥1. Tampak pula bahwa S tidak memuat bilangan yang lebih dari 4 dan tidak semua bilangannya 0, serta tidak ada bilangan negatif. S sudah terurut berupa bilangan monoton turun, sehingga langkah selanjutnya adalah sebagai berikut. S=4 4 3 3 2 (Eksekusi 4 dan kurangi 4 bilangan disampingnya dengan 1) S1=3 2 2 1 (Eksekusi 3 dan kurangi 3 bilangan disampingnya dengan 1) S2=1 1 0 (Eksekusi 1 dan kurangi 1 bilangan disampingnya dengan 1) S3=0 0 Tampak bahwa S3 hanya memuat bilangan 0, sehingga S3 grafik. Jadi, S juga grafik. 3. Periksalah apakah barisan (5 4 3 2 1 0)merupakan grafik atau bukan Penyelesaian: Perhatikan bahwa banyaknya bilangan pada S=5 4 3 2 1 0 adalah 6. Jelas bahwa n=6≥1. Tampak pula bahwa S tidak memuat bilangan yang lebih dari 5 dan tidak semua bilangannya 0, serta tidak ada bilangan negatif. S sudah terurut berupa bilangan monoton turun, sehingga langkah selanjutnya adalah sebagai berikut. S=5 4 3 2 1 0 (Eksekusi 5 dan kurangi 5 bilangan disampingnya dengan 1) S1=3 2 1 0 −1



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