BAB II LANDASAN TEORI Dalam bab ini dipaparkan beberapa hasil penelitian yang dilakukan para peneliti sebelumnya, pengertian dasar graf, operasi-operasi pada graf, kelas-kelas graf dan dimensi partisi pada graf. Pemaparan tersebut dibagi dalam tiga subbab yaitu tinjauan pustaka, landasan teori, dan kerangka pemikiran. Subbab tinjauan pustaka memuat hasil-hasil penelitian yang telah dilakukan. Subbab landasan teori memuat pengertian dasar graf, operasi-operasi pada graf, kelas-kelas graf dan dimensi partisi pada graf. Subbab kerangka pemikiran memuat prinsipprinsip teori yang dapat menggambarkan langkah dari penelitian ini.
2.1
Tinjauan Pustaka
Menurut Javaid dan Shokat [9], dimensi partisi adalah kardinalitas minimum dari k-partisi penyelesaian terhadap V (G). Pada tahun 2000, Chartrand et al. [5] memperoleh beberapa hasil penelitian yaitu 1. pd(G) = 2 jika dan hanya jika G adalah path Pn , 2. pd(G) = n jika dan hanya jika G adalah graf lengkap Kn , dan 3. untuk graf bipartit lengkap Kr,s pd(Kr,s ) = r + 1 jika r = s dan pd(Kr,s ) = max{r, s} jika r ̸= s. Pada tahun 2012, Javaid et al. [10] meneliti dimensi partisi pada graf circulant. Dalam penelitiannya Javaid et al. [10] memperoleh hasil dimensi partisi pada dua families dari graf circulant yaitu Cn (1, 3) dan Cn (1, 4). Jika Cn (1, 3) merupakan families dari graf circulant dengan n ≥ 10 maka pd(Cn (1, 3)) = 4. Kemudian untuk n ≥ 9, jika Cn (1, 4) merupakan families dari graf circulant 4
maka pd(Cn (1, 4)) = 4 ketika n ≡ 1(mod 4) dan pd(Cn (1, 4)) ≤ 5 ketika n ≥ 0, 2, 3(mod 4). Penelitian ini bertujuan untuk memperoleh rumus umum dimensi partisi pada graf antiprisma, graf Mongolian tent dan graf stacked book.
2.2
Landasan Teori
Berikut diberikan beberapa definisi yang mendasari penelitian ini, yaitu pengertian dasar graf, operasi-operasi pada graf, kelas-kelas graf, dan dimensi partisi pada graf.
2.2.1
Pengertian Dasar Graf
Pengertian dasar graf meliputi definisi graf, pengertian order dan size, sifat adjacent dan incident, degree dari suatu vertex, u − v walk, u − v trail, u − v path, graf terhubung, circuit, cycle, graf reguler dan jarak. Berikut ini diberikan beberapa definisi dasar graf menurut Chartrand [2]. Definisi 2.2.1. Suatu graf G adalah suatu himpunan tak kosong berhingga V disertai dengan relasi R yang irreflexive, symmetric pada V . Graf terdiri dari kumpulan titik-titik yang disebut vertex yang dihubungkan oleh garis yang disebut edge. Sebuah graf harus terdapat minimal sebuah vertex dan dimungkinkan tidak mempunyai edge. Graf yang himpunan edge-nya adalah himpunan kosong dinamakan graf kosong atau null graph. Banyaknya vertex dalam graf G disebut order, dinotasikan dengan |V (G)| dan banyaknya edge dalam graf G disebut size, dinotasikan dengan |E(G)|. Definisi 2.2.2. Jika u dan v adalah sembarang dua vertex dari graf G yang dihubungkan oleh edge e, dinotasikan e = uv maka u dan v dikatakan sebagai vertex yang adjacent sedangkan, vertex u dan v dikatakan sebagai dua vertex yang incident dengan edge e. Misalkan v adalah vertex pada G. Banyaknya edge pada G yang incident dengan v disebut degree dari v. Degree dari v dinotasikan dengan deg(v). 5
Definisi 2.2.3. Suatu u − v walk dari graf G adalah barisan bergantian antara vertex dan edge yang dimulai dari vertex u dan berakhir di vertex v. Suatu u − v trail adalah u − v walk yang tidak mengulang sebarang edge. Suatu u − v path adalah u − v walk yang tidak mengulang sembarang vertex. Dua vertex u dan v dalam graf G dikatakan terhubung jika u = v, atau jika u ̸= v dan terdapat u − v path dalam G. Graf G terhubung jika setiap dua vertex pada G terhubung. Definisi 2.2.4. Circuit adalah u−v trail dimana u = v dan memuat paling sedikit tiga edge, dengan kata lain suatu circuit harus dimulai dan diakhiri pada vertex yang sama. Suatu circuit yang tidak mengulang sembarang vertex dinamakan cycle.
Gambar 2.1. Graf G merupakan graf terhubung Gambar 2.1 merupakan contoh dari graf terhubung dengan |V (G)| = 5 dan |E(G)| = 7. Degree setiap vertex pada graf G adalah deg(v1 ) = deg(v2 ) = 3, deg(v3 ) = deg(v5 ) = 2, dan deg(v4 ) = 4. Contoh u−v walk dalam Gambar 2.1 adalah v5 , v5 v1 , v1 , v1 v2 , v2 , v2 v1 , v1 , v1 v4 , v4 , sedangkan contoh dari u − v trail adalah v1 , v1 v2 , v2 , v2 v4 , v4 , v4 v1 , v1 , v1 v5 , v5 dan v1 , v1 v2 , v2 , v2 v4 , v4 adalah contoh dari u − v path. Pada Gambar 2.1 v1 , v5 , v4 , v2 , v3 , v4 , v1 adalah circuit tetapi bukan cycle sedangkan v1 , v2 , v3 , v4 , v5 , v1 adalah cycle dan merupakan circuit. Suatu circuit belum tentu cycle tetapi suatu cycle pasti merupakan circuit. Definisi 2.2.5. graf r-reguler adalah graf yang setiap vertexnya memiliki degree yang sama sebanyak r. 6
Definisi jarak diambil dari Chartrand dan Lesniak [3]. Definisi 2.2.6. Jarak dari vertex u ke v di G adalah panjang path terpendek dari vertex u ke v, dinotasikan dengan d(u, v). Jika tidak terdapat path yang menghubungkan vertex u dan v maka d(u, v) = ∞. Definisi 2.2.7. Misalkan G = (V, E) adalah graf terhubung. Misalkan S ⊆ V dan terdapat suatu vertex v ∈ V (G), maka jarak vertex v terhadap S yang dinotasikan d(v, S) didefinisikan sebagai d(v, S) = min{d(v, x)|x ∈ S}. Berdasarkan Gambar 2.1 dapat ditunjukkan jarak setiap vertex, yaitu d(v1 , v2 ) = 1, d(v1 , v3 ) = 2, d(v1 , v5 ) = 1, d(v2 , v3 ) = 1, d(v2 , v5 ) = 2, dan d(v3 , v5 ) = 2. Misalkan diambil himpunan bagian S = {v1 , v3 }, diperoleh d(v1 , S) = 0, d(v2 , S) = 1, d(v3 , S) = 0, d(v4 , S) = 1, dan d(v5 , S) = 1.
2.2.2
Operasi pada Graf
Suatu graf dapat dibentuk dengan cara menggunakan operasi-operasi dalam graf yaitu, union, join dan hasil kali Cartesian yang didefinisikan oleh Chartrand et al. [6]. Definisi 2.2.8. Union dari G1 dan G2 yang dinotasikan G1 ∪ G2 adalah graf dengan V (G1 ∪ G2 ) = V (G1 ) ∪ V (G2 ) dan E(G1 ∪ G2 ) = E(G1 ) ∪ E(G2 ). Gambar 2.2(a) adalah graf G1 dan G2 . Gambar 2.2(b) menunjukkan operasi union dari G1 dan G2 .
Gambar 2.2. (a) Graf G1 dan G2 dan (b) union G1 dan G2
7
Definisi 2.2.9. Join dari G1 dan G2 yang 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, . . .. Definisi 2.2.10. Hasil kali Cartesian dari G1 dan G2 yang 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 ). Join dari graf G1 dan G2 ditunjukkan pada Gambar 2.3(a), dan Gambar 2.3(b) menunjukkan operasi hasil kali Cartesian dari G1 dan G2 .
Gambar 2.3. (a) join G1 dan G2 dan (b) hasil kali Cartesian G1 dan G2
2.2.3
Kelas-Kelas Graf
Graf dapat dibagi ke dalam kelas-kelas graf, antara lain path, graf lengkap, graf tree, graf star, graf antiprisma, graf Mongolian tent, graf book, graf stacked book, graf prisma, dan lain sebagainya. Berikut diuraikan definisi dari kelas graf antiprisma, graf Mongolian tent, dan graf stacked book. Baˇ ca et al. [1] mendefinisikan pengertian graf antiprisma, Lee [11] mendefinisikan pengertian graf Mongolian tent, sedangkan Gallian [7] mendefinisikan pengertian graf stacked book sebagai berikut. Definisi 2.2.11. Graf antiprisma dinotasikan An dengan n ≥ 3 adalah suatu graf reguler berdegree 4 dengan jumlah vertex 2n dan jumlah edge 4n. Tersusun 8
atas Cn luar dan dalam kemudian antara kedua cycle dihubungkan oleh edge vi ui dan vi u1+i(mod n) untuk i = 1, 2, 3, . . . , n. Gambar 2.4 adalah contoh dari graf antiprisma An dengan n ≥ 3.
Gambar 2.4. Graf antiprisma An
Definisi 2.2.12. Graf Mongolian tent dinotasikan Mm,n adalah suatu graf hasil kali Cartesian Pm × Pn , n bilangan ganjil, dan menambahkan satu vertex di atas grid kemudian menggabungkan setiap vertex ganjil pada baris pertama Pm × Pn dengan vertex tersebut. Gambar 2.5 adalah contoh dari graf Mongolian tent Mm,n dengan m ≥ 2 dan n ≥ 3.
Gambar 2.5. Graf Mongolian tent Mm,n
9
Definisi 2.2.13. Graf stacked book dinotasikan Bm,n adalah suatu graf hasil kali Cartesian Sm × Pn dengan Sm adalah graf bintang dengan m + 1 vertex dan Pn adalah path dengan n vertex. Gambar 2.6 adalah contoh dari graf stacked book Bm,n dengan m ≥ 3 dan n ≥ 2.
Gambar 2.6. Graf stacked book Bm,n
2.2.4
Dimensi Partisi
Berikut ini diberikan definisi dan lema dimensi partisi menurut Chartrand et al. [5]. Definisi 2.2.14. Misalkan G adalah graf terhubung. Untuk suatu subhimpunan Si pada V (G) dan suatu vertex v pada G, jarak antara v dan Si didefinisikan sebagai d(v, Si ) = min{d(v, x)|x ∈ Si }, 1 ≤ i ≤ k. Selanjutnya, untuk suatu k-partisi terurut Π = {S1 , S2 , . . . , Sk } pada V (G) dan suatu vertex v pada G, representasi v terhadap Π didefinisikan sebagai r(v|Π) = (d(v, S1 ), d(v, S2 ), ..., d(v, Sk )). Himpunan Π disebut partisi pembeda jika r(v|Π) berbeda, untuk setiap v ∈ V (G). Kardinalitas minimum dari k-partisi pembeda terhadap V (G) disebut dimensi partisi dari G yang dinotasikan dengan pd(G). Lema 2.2.1. Misalkan G adalah graf terhubung dengan order n ≥ 2, maka pd(G) = 2 jika dan hanya jika G = Pn .
10
Lema 2.2.2. Misalkan Π partisi pembeda dari graf G dengan u, v ∈ V (G). Jika d(u, w) = d(v, w) untuk setiap w ∈ V (G) − {u, v}, maka u dan v termuat pada kelas partisi yang berbeda. Bukti. Misalkan Π = {S1 , S2 , . . . , Sk }, dengan u dan v termuat pada kelas partisi yang sama pada Π, misal Si , maka d(u, Si ) = d(v, Si ) = 0. Karena d(u, w) = d(v, w) untuk setiap w ∈ V (G) − {u, v}, maka d(u, Sj ) = d(v, Sj ) untuk 1 ≤ j ̸= i ≤ k. Sehingga, r(u|Π) = r(v|Π) dan Π bukan merupakan partisi pembeda.
Gambar 2.7. Path P4 Sebagai contoh, akan dicari dimensi partisi dari path P4 pada Gambar 2.7 dengan himpunan vertex V (P4 ) = {v1 , v2 , v3 , v4 }. Misalkan Π = {S1 , S2 }, dengan S1 = {v1 , v2 }, dan S2 = {v3 , v4 }, diperoleh representasi untuk setiap vertex pada graf P4 terhadap Π adalah sebagai berikut. r(v1 |Π) = (0, 2),
r(v3 |Π) = (1, 0),
r(v2 |Π) = (0, 1),
r(v4 |Π) = (2, 0).
Sembarang vertex v di P4 mempunyai representasi r(v|Π) yang berbeda sehingga terdapat 2-partisi pembeda. Jadi, dimensi partisi dari graf P4 adalah pd(P4 ) = 2.
2.3
Kerangka Pemikiran
Berdasarkan landasan teori yang telah diberikan, dapat disusun suatu kerangka pemikiran untuk menyelesaikan permasalahan dalam penelitian ini. Konsep Chartrand et al. [4] digunakan untuk menentukan dimensi partisi pada graf antiprisma, graf Mongolian tent, dan graf stacked book. Langkah pertama adalah membagi himpunan vertex pada graf G menjadi k-partisi pembeda yang mungkin dinotasikan dengan Π. Selanjutnya, menghitung jarak setiap vertex pada
11
graf tersebut terhadap Π, dinotasikan r(v|Π). Jika minimal terdapat dua vertex memiliki representasi yang sama terhadap Π maka himpunan vertex disusun kembali menjadi k-partisi yang baru. Langkah tersebut dilakukan sampai setiap vertex di G mempunyai representasi yang berbeda terhadap Π. Terakhir, menentukan kardinalitas minimum dari k-partisi yang mungkin, sehingga diperoleh dimensi partisi pada graf antiprisma, graf Mongolian tent, dan graf stacked book. Untuk mempermudah proses pengerjaan, peneliti menggunakan tabel pada microsoft excel. Tujuan menggunakan tabel pada microsoft excel adalah untuk mempermudah dalam menentukan pola partisi. Setiap pola diberi warna sehingga tersusun suatu pola terurut yang nantinya digunakan untuk menentukan rumus umum. Untuk membuat suatu teorema, diperlukan beberapa lema sebagai pendukung. Dalam Chartrand et al. [5] dijelaskan lema yang berkaitan dengan dimensi partisi. Lema tersebut yang digunakan sebagai acuan untuk menyusun dan membuktikan dimensi partisi pada graf Mongolian tent dan graf stacked book. Sedangkan, untuk membuktikan dimensi partisi pada graf antiprisma penulis menggunakan pembuktian dengan pola umum tanpa menggunakan lema.
12
