BAB II LANDASAN TEORI Bab ini terdiri dari tiga subbab. Subbab pertama adalah tinjauan pustaka yang memuat hasil penelitian yang dilakukan oleh peneliti sebelumnya dalam bidang dimensi metrik. Subbab kedua berisi landasan teori yang memuat pengertian dasar graf, operasi pada graf, kelas-kelas graf dan dimensi metrik. Sedangkan subbab terakhir adalah kerangka pemikiran yang menjelaskan alur pemikiran penulis dalam melakukan penelitian.
2.1
Tinjauan Pustaka
Dimensi metrik adalah himpunan pembeda yang mempunyai kardinalitas terkecil. Himpunan pembeda tersebut diperoleh dengan cara mencari jarak setiap vertex terlebih dahulu. Khuller et al. [11] telah menunjukkan bahwa permasalahan dimensi metrik pada suatu graf sembarang termasuk dalam masalah NP-Complete. Masalah NP-Complete tidak bisa diselesaikan menggunakan algoritma yang efisien karena merupakan persoalan NP yang paling sulit. NP Problems adalah persoalan keputusan yang dapat diselesaikan oleh algoritma non-deterministik dalam waktu polinom. Oleh karena itu, penelitian mengenai dimensi metrik ini dibahas untuk suatu kelas graf tertentu. Pada tahun 2000, Chartrand et al. [6] mengkarakterisasi dimensi metrik pada graf lintasan Pn dan graf complete Kn yang memiliki n vertex dengan hasil yaitu 1. dim(G) = 1 jika dan hanya jika G = Pn (n ≥ 2), dan 2. dim(G) = n − 1 jika dan hanya jika G = Kn (n ≥ 2). Pada tahun 2005, Caceres et al. [3] meneliti dimensi metrik pada graf fan Fn dengan hasil 4
1, 2, dim(Fn ) = 3, ⌊ 2n+2 ⌋, 5
n = 1; n = 2, 3; n = 6; n lainnya.
Pada tahun 2006, Caceres et al. [4] berhasil meneliti dimensi metrik pada graf cycle yaitu dim(Cn ) = 2 untuk n ≥ 3. Pada tahun 2015, Fikri et al. [7] menunjukkan dimensi metrik pada graf flower Fn adalah 3 untuk n = 3 dan n − 1 untuk n lainnya. Penelitian ini bertujuan untuk memperoleh rumus umum dimensi metrik pada graf web, graf friendship, graf generalized flower, dan graf Cn ∗2 Km . Oleh karena itu, diperlukan beberapa definisi yang mendasari penelitian ini seperti pengertian dasar, operasi pada graf, kelas-kelas graf, dan dimensi metrik pada graf.
2.2
Landasan Teori
Berikut diberikan beberapa definisi yang mendasari penelitian ini yaitu pengertian dasar graf, operasi pada graf, kelas-kelas graf, dan dimensi metrik pada graf.
2.2.1
Pengertian Dasar Graf
Chartrand [5] mendefinisikan tentang pengertian graf, u − v walk, u − v trail, u − v path, cycle, distance (jarak), sifat adjacent, incident, dan degree pada suatu graf. Definisi 2.2.1. Suatu graf G adalah himpunan tak kosong berhingga V disertai dengan relasi R yang irreflexive, symmetric pada V . Dalam graf G, V (G) disebut himpunan vertex dan E(G) adalah himpunan edge dalam graf G. Setiap graf harus memuat minimal satu vertex dan dimungkinkan tidak memiliki edge. Graf yang himpunan edge-nya adalah himpunan kosong dinamakan
5
graf kosong atau null graph. Banyaknya vertex pada suatu graf disebut dengan order, sedangkan banyaknya edge pada suatu graf disebut dengan size. Definisi 2.2.2. Jika u dan v adalah sembarang vertex dari graf G yang dihubungkan oleh edge e dan dinotasikan e = uv maka dikatakan u dan v adalah vertex yang saling adjacent. Selanjutnya vertex u dan v dikatakan incident dengan edge e dan e disebut join vertex dari u dan v.
Gambar 2.1. Graf A Gambar 2.1 merupakan graf A dengan order 6 dan size 9 yang memperlihatkan bahwa vertex v1 dan v2 saling adjacent sedangkan vertex v1 dan v2 incident terhadap edge v1 v2 . Definisi 2.2.3. Misalkan v vertex dari graf G. Degree vertex v dari graf G dinotasikan deg(v) adalah banyaknya edge yang incident dengan v. Gambar 2.1 menunjukkan bahwa deg(v1 ) = 2, deg(v2 ) = 3, dan deg(v3 ) = 4. Vertex dengan degree 0 disebut isolated vertex dan vertex dengan degree 1 disebut sebagai pendant vertex. Definisi 2.2.4. Suatu u − v walk dari graf G adalah barisan bergantian antara vertex dan edge yang dimulai dari vertex u dan berakhir di vertex v, sehingga ei = ui−1 ui untuk i = 1, 2, . . . , n. Suatu u − v path adalah u − v walk yang tidak mengulang sembarang vertex. Suatu u − v trail adalah u − v walk yang tidak mengulang sembarang edge. Contoh v1 −v2 walk pada Gambar 2.1 yaitu v1 , v1 v2 , v2 , v2 v3 , v3 , v3 v5 , v5 , v5 v6 , v6 , v6 v2 , v2 . Contoh v1 − v6 path adalah v1 , v1 v2 , v2 , v2 v3 , v3 , v3 v5 , v5 , v5 v6 , v6 . Contoh v1 − v4 trail adalah v1 , v1 v6 , v6 , v6 v3 , v3 , v3 v5 , v5 , v5 v4 , v4 , v4 v3 , v3 , v3 v2 , v2 . 6
Definisi 2.2.5. Suatu u − v trail dengan u = v dan paling sedikit terdiri dari 3 vertex disebut circuit. Circuit yang tidak mengulang sembarang vertex disebut cycle. Graf A pada Gambar 2.1 mempunyai circuit yaitu v1 , v1 v2 , v2 , v2 v6 , v6 , v6 v5 , v5 , v5 v3 , v3 , v3 v6 , v6 , v6 v1 , v1 dan cycle yaitu v1 , v1 v2 , v2 , v2 v6 , v6 , v6 v1 , v1 . Definisi 2.2.6. Distance (jarak) dari vertex u ke v di G adalah panjang lintasan terpendek dari vertex u ke v yang dinotasikan dengan d(u, v). Jika tidak terdapat lintasan yang menghubungkan vertex u dan v maka d(u, v) = ∞.
2.2.2
Operasi pada Graf
Suatu graf dapat dibentuk dengan cara menggunakan operasi-operasi tertentu dalam graf. Operasi tersebut antara lain komplemen dari suatu graf, union, join, dan cartesian product dari dua graf yang didefinisikan oleh Chartrand et al. [6]. Sedangkan operasi amalgamasi didefinisikan oleh Gross et al. [9]. Terdapat operasi amalgamasi vertex dan operasi amalgamasi edge. Definisi 2.2.7. Komplemen dari graf G, dinotasikan G, adalah graf dengan himpunan vertex V (G) = V (G) sedemikian hingga uv adalah edge dari G jika dan hanya jika uv bukan edge dalam G. Definisi 2.2.8. Union dari G1 dan G2 , dinotasikan G1 ∪ G2 , adalah graf dengan V (G1 ∪ G2 ) = V (G1 ) ∪ V (G2 ) dan E(G1 ∪ G2 ) = E(G1 ) ∪ E(G2 ). Contoh dari operasi komplemen suatu graf dapat dilihat pada Gambar 2.2 dan operasi union suatu graf dapat dilihat pada Gambar 2.3. Definisi 2.2.9. Join dari G1 dan G2 , dinotasikan G1 + G2 , adalah graf yang terdiri dari union G1 ∪ G2 bersama-sama dengan semua edge vi vj , dimana vi ∈ V (G1 ) dan vj ∈ V (G2 ) dengan i, j = 1, 2, 3, . . . .
7
Gambar 2.2. Graf G (kiri) dan komplemen dari graf G (kanan)
Gambar 2.3. Graf G1 ,G2 dan G1 ∪ G2 Definisi 2.2.10. Cartesian product dari G1 dan G2 , dinotasikan G1 ×G2 , merupakan graf yang memiliki himpunan vertex V (G1 ) × V (G2 ) dan dua vertex (u1 , u2 ) dan (v1 , v2 ) adjacent dalam G1 ×G2 jika dan hanya jika u1 = v1 dan u2 v2 ∈ E(G2 ), atau u2 = v2 dan u1 v1 ∈ E(G1 ). Contoh dari operasi join dan cartesian product dari graf G1 dan G2 dapat dilihat pada Gambar 2.4. Definisi 2.2.11. Operasi amalgamasi vertex dari pasangan graf (G, u) dan (H, v) adalah graf yang diperoleh dengan menggabungkan vertex u dari graf G dan v dari graf H menjadi satu vertex. Operasi amalgamasi edge dari pasangan edge graf (G, a) bersama (H, b) adalah graf yang diperoleh dengan menggabungkan edge a dan b menjadi satu edge. Notasi yang digunakan untuk menyatakan operasi amalgamasi vertex adalah ”∗” sedangkan notasi untuk operasi amalgamasi edge adalah ”∗2 ”. Contoh operasi amalgamasi dari dua graf dapat dilihat pada Gambar 2.5.
8
Gambar 2.4. G1 + G2 dan G1 × G2
Gambar 2.5. Operasi amalgamasi vertex G ∗ H dan operasi amalgamasi edge G ∗2 H
2.2.3
Kelas-Kelas Graf
Graf dapat dibagi ke dalam kelas-kelas graf, antara lain graf lintasan, graf web, graf cycle, graf book, graf complete, graf flower, graf generalized flower, graf prisma, dan graf friendship. Berikut akan diuraikan definisi dari kelas graf complete menurut Chartrand [5], graf web menurut Koh et al [12], graf friendship menurut Gallian [8], graf generalized flower menurut Miller et al [13], dan graf C n ∗ 2 Km . Definisi 2.2.12. Suatu graf dikatakan graf lengkap dengan order m yang dinotasikan Km apabila setiap dua vertex yang berbeda saling adjacent. 9
Ilustrasi graf complete Km disajikan pada Gambar 2.6.
Gambar 2.6. Graf complete Km
Definisi 2.2.13. Graf web yaitu graf yang diperoleh dari graf generalized prism Yn+1,3 dengan menghapus edge pada cycle terluar. Ilustrasi graf web Wn dengan n ≥ 3 disajikan pada Gambar 2.7.
Gambar 2.7. Graf web Wn
10
Definisi 2.2.14. Graf friendship fn dengan n ≥ 2 yaitu suatu graf yang dibentuk dari n-kali graf C3 yang dipusatkan pada satu vertex. Ilustrasi dari graf friendship fn disajikan pada Gambar 2.8.
Gambar 2.8. Graf friendship fn
Definisi 2.2.15. Graf generalized flower dengan p kelopak F L(G, m, n, p) adalah graf yang dibangun dari graf generalized web W B(G, m, n) yang menghubungkan setiap vertex ke pusat vertex u dengan sebuah edge. Pada penelitian ini akan diteliti graf generalized flower yaitu F L(G, m, n) dengan G∼ = Cm . Definisi 2.2.16. Graf Cn ∗2 Km dengan n ≥ 3 dan m ≥ 2 yaitu suatu graf hasil dari operasi amalgamasi edge atau menggabungkan salah satu edge pada Cn dan satu edge pada Km sehingga menjadi satu edge yang incident dengan vertex x dan y. Vertex x dan y juga merupakan vertex yang dimiliki oleh Cn dan Km . Ilustrasi F L(G, m, n) dengan G ∼ = Cm dapat dilihat pada Gambar 2.9 dan graf Cn ∗2 Km disajikan pada Gambar 2.10.
11
Gambar 2.9. Graf F L(G, m, n)
Gambar 2.10. Graf Cn ∗2 Km
2.2.4
Dimensi metrik
Menurut Chartrand et al. [6], misalkan G adalah suatu graf terhubung dengan himpunan vertex V (G) dan himpunan edge E(G). Misalkan W = {w1 , w2 , ..., wk } sebagai subhimpunan dari V (G). Untuk setiap v ∈ V (G), representasi vertex v terhadap W didefinisikan sebagai k-pasang terurut r(v | W ) = (d(v, w1 ), d(v, w2 ), ..., d(v, wk )). Himpunan W dikatakan sebagai himpunan pembeda dari G apabila untuk setiap dua vertex berbeda x, y ∈ V (G) berlaku r(x | W ) ̸= r(y | W ). Himpunan 12
pembeda dengan kardinalitas terkecil disebut basis dari G. Dimensi metrik dari G yang dinotasikan dim(G), didefinisikan sebagai banyaknya elemen dari suatu basis di G. Jika dim(G) = k maka G dikatakan berdimensi metrik k.
Gambar 2.11. Graf H
Sebagai contoh, perhatikan graf H pada Gambar 2.11. Selanjutnya, untuk mendapatkan himpunan pembeda dibuat tabel jarak antar vertex. Misal diambil himpunan vertex W1 = {v1 , v2 }, diperoleh representasi untuk semua vertex pada H terhadap W1 adalah r(v1 |W1 ) = (0, 1),
r(v2 |W1 ) = (1, 0),
r(v3 |W1 ) = (2, 1),
r(v4 |W1 ) = (2, 1),
r(v5 |W1 ) = (1, 2),
r(v6 |W1 ) = (2, 1).
Himpunan vertex W1 bukan merupakan himpunan pembeda, karena terdapat vertex pada H yang mempunyai representasi sama yaitu r(v3 |W1 ) = r(v4 |W1 ) = r(v6 |W1 ) = (2, 1). Bisa dilihat pada tabel jarak bahwa tidak dapat diperoleh himpunan pembeda dengan kardinalitas 2 karena memiliki representasi yang sama. Selanjutnya misal dipilih himpunan vertex W2 = {v1 , v3 , v6 }, diperoleh representasi untuk semua vertex pada H terhadap W2 adalah r(v1 |W2 ) = (0, 2, 2),
r(v2 |W2 ) = (1, 1, 1),
r(v3 |W2 ) = (2, 0, 2),
r(v4 |W2 ) = (2, 2, 2),
r(v5 |W2 ) = (1, 1, 1),
r(v6 |W2 ) = (2, 2, 0).
Himpunan vertex W2 bukan himpunan pembeda karena terdapat vertex yang memiliki representasi sama yaitu r(v2 |W2 ) = r(v5 |W2 ) = (1, 1, 1). Dapat 13
dibuat 20 himpunan vertex dengan kardinalitas 3 tetapi tidak ada yang bisa menjadi himpunan pembeda karena himpunan vertex dengan kardinalitas 3 akan menimbulkan representasi yang sama. Misalkan dipilih himpunan vertex W3 = {v1 , v2 , v3 , v4 }, diperoleh representasi untuk semua vertex pada H terhadap W3 adalah r(v1 |W3 ) = (0, 1, 2, 2),
r(v2 |W3 ) = (1, 0, 1, 1),
r(v3 |W3 ) = (2, 1, 0, 2),
r(v4 |W3 ) = (2, 1, 2, 0),
r(v5 |W3 ) = (1, 2, 1, 1),
r(v6 |W3 ) = (2, 1, 2, 2).
Setiap vertex dari H memiliki representasi yang berbeda terhadap W3 , sehingga W3 merupakan himpunan pembeda dari graf H. Dapat dibuat 15 himpunan vertex dengan kardinalitas 4 dan yang bisa menjadi himpunan pembeda hanya 6 himpunan, yaitu W3 = {v1 , v2 , v3 , v4 },
W4 = {v2 , v3 , v4 , v6 },
W5 = {v1 , v2 , v4 , v6 },
W6 = {v1 , v3 , v4 , v5 },
W7 = {v3 , v4 , v5 , v6 },
W8 = {v1 , v4 , v5 , v6 }.
Dengan demikian diperoleh dim(H) = 4 dan W3 , W4 , W5 , W6 , W7 , W8 merupakan basis dari H. Pada graf H tidak diperoleh himpunan pembeda dengan kardinalitas 1 karena graf H memiliki cycle jadi tidak dimungkinkan memiliki himpunan pembeda dengan kardinalitas 1.
2.3
Kerangka Pemikiran
Berdasarkan landasan teori yang telah diberikan, dapat disusun suatu kerangka pemikiran untuk menyelesaikan permasalahan dalam penelitian ini. Penentuan dimensi metrik pada penelitian ini mengacu pada Chartrand et al. [6], yaitu dengan terlebih dahulu menghitung jarak setiap vertex terhadap vertex lainnya pada graf tersebut. Agar mempermudah perhitungan jarak bisa dibuat tabel jarak menggunakan microsoft excel. Selanjutnya dipilih himpunan W yang merupakan subhimpunan vertex dari graf tersebut. Himpunan W dikatakan himpunan pembeda apabila representasi jarak untuk semua vertex terhadap W berbeda. Himpunan pembeda yang memiliki kardinalitas minimum akan dipilih sebagai basis dari graf tersebut dan jumlah elemen dari basis disebut dimensi metrik pada graf tersebut. Penelitian oleh para peneliti terdahulu dapat memban14
tu untuk mencari dimensi metrik pada graf web, graf friendship, graf generalized flower, dan graf Cn ∗2 Km . Kardinalitas himpunan pembeda dari graf web, graf friendship, graf generalized flower, dan graf Cn ∗2 Km akan diperoleh lebih dari satu karena graf tersebut memiliki cycle. Menurut Chartrand et al. [6] yang sudah meneliti graf lintasan, hanya graf G = Pn yang memiliki dim(G) = 1. Untuk pembuktian rumus umum dimensi metrik pada graf web digunakan teknik pembuktian yang mengacu pada Saba et al. [15], yaitu dengan mencari pola umum yang dapat dicari dari jarak antar vertex sehingga tidak membangun lema. Sedangkan pembuktian rumus umum dimensi metrik pada graf friendship, graf generalized flower, dan graf Cn ∗2 Km mengacu pada Baˇ ca et al. [1], yaitu dengan menggunakan kontradiksi untuk membuktikan kardinalitas dari himpunan pembeda.
15
