M1 - TT - Terapan Teori Graf [PDF]

Citation preview

PENDAHULUAN TEORI GRAF



Dr. Desti Riminarsih, S.Si, M.Si Dr. Nola Marina, S.Si, M.Si



LINGKUP MATERI Operasi pada Graf



1



6



Keterhubungan Graf



Kelahiran Teori Graf



2



5 4



Derajat pada Graf



3



Graf secara formal



Subgraph



Kelahiran Teori Graf A



Sungai Pregel di Kalilingrad (Uni Soviet)



Misteri Jembatan Konigsberg



C



Bagaimana dapat melalui ketujuh jembatan tepat satu kali, yakni bermula dari satu tempat/daratan (A, B, C atau D) dan kembali ke tempat semula B



Kelahiran Teori Graf Leonhard Euler 1736



Mampu mengungkap misteri Jembatan Konigsberg



R



Representasi graf keadaan jembatan Konigsberg oleh Euler



G



raf



Adalah struktur diskrit yang terdiri atas simpul dan ruas yang menguhubungkan simpul-simpul.



Graf Secara Formal Sebuah Graf G didefinisikan sebagai Koleksi atau pasangan dari dua himpunan V dan E G = ( V,E ) V : Himpunan Vertex / simpul / node / titik E : Himpunan Edge / ruas / sisi



Graf Secara Formal Contoh: b



c



e



V



= {a, b, c, d, e}



E = {(a,b ),(b,c),( c,d),( c,e),( d,e) }



a



G1



d



Graf Secara Formal Contoh: jika ruas memiliki nama b



e2



e1 a



c e4 e3



G1



e e5



d



V



{a,b,c,d,e}



Tipe Ruas Berarah



u



Pasangan terurut dari simpul. Direpresentasikan sebagai (u, v) yang memiliki arah dari simpul u ke v.



v



Tak berarah u



v



Pasangan tak terurut dari simpul . Direpresentasikan sebagai {u, v} dengan mengabaikan arah dan memperlakukan kedua simpul ujung secara bergantian.



Tipe Ruas Loop (Gelung) Ruas yang menghubungkan simpul yang sama yaitu tepi yang menghubungkan simpul dengan dirinya sendiri. Direpresentasikan sebagai {u, u} = {u}



Multiple Edges (Ruas Berganda) Ruas sejajar, yaitu dua atau lebih ruas yang menghubungkan sepasang simpul yang sama.



Tipe Graf : Graf Sederhana Graf sederhana terdiri dari V, suatu himpunan tak kosong dari simpul, dan E, suatu himpunan pasangan tak terurut dari elemen simpul yang berbeda.



Contoh: G(V, E), V = {u, v, w}, E = {{u, v}, {v, w}, {u, w}}



v u w



Graf Sederhana: Graf Lengkap Graf lengkap/Complete graph: Kn Graf dengan n simpul dan setiap pasang simpulnya terhubung oleh satu ruas. Derajat setiap simpul sama.



Contoh: K1, K2, K3, K4



•



0-------0



K1



K2



lo\ 0-------0 K3



K4



Graf Sederhana: Cycle Cycle: Cn Graf dengan n ≥ 3 yang terdiri atas n simpul v1, v2, v3 … vn dan ruas (v1, v2), (v2, v3), (v3, v4) … (vn-1, vn), (vn, v1)



Contoh : C3, C4



C3



C4



Graf Sederhana: Roda/Wheels Roda/ Wheels Wn, diperoleh dengan menambahkan simpul tambahan ke cycle Cn dan menghubungkan semua simpul ke simpul baru ini dengan ruas baru.



Contoh: W3, W4



W3



W4



Graf Sederhana: Bipartisi • Graf sederhana G disebut Bipartisi, jika V dapat dipartisi menjadi dua himpunan disjoint V1 dan V2 sehingga setiap ruas dalam graf menghubungkan simpul di V1 dan simpul V2 • Tidak ada sisi di G yang menghubungkan dua simpul di V1 atau dua simpul di V2)



Contoh : V1 = {v1, v2, v3} vand V2 = {v4, v5, v6}, 1



v2 v3



V1



v4 v5 v6



V2



Graf Sederhana: Bipartisi Lengkap Graf Bipartisi lengkap Km,n



adalah graf bipartisi yang semua simpul



pada V (G1) terhubung dengan setiap simpul pada V(G2) dan sebaliknya



Contoh: K2,3, K3,3



K2,3



K3,3



Tipe Graf : Multigraf Graf yang mengandung ruas sejajar Contoh Representasi: G(V, E) V = {u, v, w}, E = {e1, e2, e3} u



Ruas sejajar



e1



0



0w ~ e v e2



3



Tipe Graf : Pseudograph Graf yang mengandung gelung/loop Contoh: V = {u, v, w}, E = {e1, e2, e3, e4}



0u e1



CD w



e2



Gelung/Loop v



e3



e4



Terminologi Graf Tak Berarah Berdampingan/ neighbour simpul u dan v disebut berdampingan bila terdapat ruas ( u, v )



u



v



0k



w



Order Banyaknya simpul dari suatu graf Size/ ukuran Banyaknya ruas dari suatu graf



Contoh: simpul u dan v berdampingan Simpul v dan w tidak berdampingan Order dari graf adalah 4 Size dari graf adalah 2



SubGraf Sebuah subgraf dari suatu graf G = (V, E) adalah suatu graf H =(V’, E’) dimana V’ subhimpunan dari V dan E’ subhimpunan dari E



Contoh : Graf G dengan V = {u, v, w}, E = {(u, v), (v, w), (w, u)} H1 , H2 adalah subgraph dari graf u



v



u



w G



-



v



u



w H1



v



w H2



Operasi pada Graf 1. Gabungan G1  G2 2. Irisan G1  G2 3. Selisih G1 - G2 4. Penjumlahan Ring G1  G2



Operasi pada Graf Bila diketahui 2 buah graf : G1(V1,E1) dan G2(V2,E2), maka :



~



G~ A



e,1



A



B



e,1i



e4



B e2



e2



1. Gabungan G1  G2 graf dengan himpunan V nya = V1  V2 dan himpunan E nya = E1  E2



D D



e,3



C



F



GmvGz



2.



Irisan G1  G2 graf dengan himpunan V nya = V1  V2 dan himpunan E nya = E1  E2



C



A



B



Gmir"'Gi A



e4 □



•



C



e,1



e,2



e4



a



B



e3



C



Operasi pada Graf Bila diketahui 2 buah graf : G1(V1,E1) dan G2(V2,E2), maka : 3. Selisih G1 - G2 graf dengan himpunan V nya = V1 dan himpunan E nya = E1 - E2 Selisih G2 – G1 graf dengan himpunan V nya = V2 dan himpunan E nya = E2 – E1 4. Penjumlahan Ring G1  G2 graf yang dihasilkan dari (G1  G2) – (G1  G2) atau (G1 -  (G2 - G1)



Operasi pada Graf B



A



D



~



Gill A



.



e1



,e 4



B



A



e2



e4



D ,e1I



C



B e,2



G1·EBGz



D



,e 3



C



D



C



IF D



Graf Null/Hampa Suatu graf d ikatakan graf nu ll/hampa bila graf tersebut tidak mengandung ruas.



b Conteh : G1 . V



* 0.



Dan E= 0



a



G1



c



Penghapusan/Deletion Penghapusan dapat dilakukan pada simpul ataupun ruas. 1) Penghapusan Simpul . Notasinya : G – {V} Contoh :



• •



v,



V4



Penghapusan S~mpul V2



Pemendekan/Shorting Pemendekan/Shorting adalah menghapus simpul yang dihubungkan oleh 2 ruas (simpul berderajat 2), lalu menghubungkan titik-titik ujung yang lain dari kedua ruas tersebut. Contoh : 11



n



n 12~m_ engekan,terhadap simpu·~Adan C



Derajat Graf Derajat simpul adalah banyaknya ruas yang terhubung ke simpul tersebut. Derajat graf adalah jumlah dari derajat simpul-simpulnya. Derajat dari sebuah loop adalah dua Contoh Graf G :



a



b



c



d



f



e



g



Derajat graf G adalah 2+4+4+1+3+4+0= 18



deg deg deg deg deg deg deg



(a) (b) (c) (d) (e) (f) (g)



= = = = = = =



2 4 4 1 3 4 0



Jenis Simpul Simpul Ganjil bila derajat simpulnya merupakan bilangan ganjil Simpul Genap bila derajat simpulnya merupakan bilangan genap



Simpul Bergantung / Akhir bila derajat simpulnya adalah 1



Simpul Terpencil bila derajat simpulnya adalah 0



Keterhubungan pada Graf Walk



barisan simpul dan ruas



Trail



Walk dengan ruas yang berbeda



Path / Jalur



Walk dengan simpul yang berbeda



Cycle / Sirkuit



Trail tertutup dengan derajat setiap simpul = 2



Contoh



B



D



E



a



-A



C



F



1) A, B, C, D, E, F, C, A, B, D, C  Walk



7) A, B, D, E, F, C, A  Cycle



2) A, B, C, D, E, F, C, A  Trail



8) C, E, F  Path



3) A, B, C, A  Cycle



9) B, D, C, B  Cycle



4) A, B, D, C, B, D, E  Walk



10) C, A, B, C, D, E, C, F, E  Trail



5) A, B, C, D, E, C, F  Trail



11) A, B, C, E, F, C, A  Trail



6) 6) A, B, D, C, E, D  Trail



Graf Terhubung • Suatu graf G disebut terhubung jika untuk setiap 2 simpul dari graf terdapat jalur yang menghubungkan kedua simpul tersebut. • Setiap Subgraf terhubung dari suatu graf disebut komponen dari G bila subgraf tersebut tidak terkandung dalam subgraf terhubung lain yang lebih besar. • Jarak antara 2 simpul dalam graf G adalah panjang jalur terpendek antara ke-2 simpul tersebut. • Diameter suatu graf terhubung G adalah maksimum jarak antara simpul-simpul G



Cutset Subgraf S dari graf terhubung G disebut Cut-Set jika subgraf S dipindahkan dari G, akan menyebabkan G tidak terhubung .



Graf Regular graf dengan derajat setiap simpulnya sama.