Bab 2. Landasan Teori. 2.1 Konsep Dasar

Bab 2 Landasan Teori Pada bab ini akan diuraikan konsep dasar dan teori graf yang berhubungan dengan topik penelitian ini, termasuk didalamnya mengenai pelabelan total tak teratur titik dan total vertex irregular strength serta hasil penelitian yang terkait.

2.1

Konsep Dasar

Pada bab sebelumnya telah dibahas pengertian dari G = (V, E), yaitu sebagai suatu pasangan himpunan terhingga tak kosong V dan E. Himpunan V = V (G) disebut himpunan titik dan E = E(G) disebut himpunan sisi, dengan anggota dari E(G) adalah pasangan titik dari subhimpunan V . Banyaknya titik di G disebut order dari G, sedang banyaknya sisi disebut ukuran (size) dari G. Definisi berikut diperoleh dari [1]. Titik u dikatakan bertetangga dengan titik v apabila u dan v dihubungkan oleh sebuah sisi e = uv atau terdapat e = uv di E(G). Dalam hal ini dapat dikatakan pula bahwa titik u dan sisi e (demikian juga v dengan e) saling terkait. Sebuah titik v di G dapat terkait dengan sebuah atau beberapa sisi di G. Banyaknya sisi yang terkait dengan titik v merupakan degree atau derajat dari titik v dinotasikan dengan degG (v). Jika seluruh titik di G berderajat k, maka graf G k − regular. Sebuah graf dengan himpunan titik V (G) = {u, v, w, x, y, z} dan himpunan sisi E(G) = {uv, uy, vy, vw, wy, wx, vz} dapat dilihat pada Gambar 2.1. Graf G mem-

4

BAB 2. LANDASAN TEORI

5

punyai 6 titik dan 7 sisi, sehingga order dan ukuran dari G berturut-turut adalah 6 dan 7. Pada graf G titik u dan v bertetangga, tetapi titik u dengan w tidak bertetangga. Titik u terkait dengan sisi uy tetapi titik tidak terkait dengan sisi vy. Derajat masing-masing titik pada G adalah degG (u) = degG (w) = degG (x) = 2, degG (y) = degG (v) = 4, dan degG (z) = 1. Lintasan adalah graf tak kosong P = (V, E) dengan V = {x0 , x1 , . . . , xk } dimana xi berbeda dan E = {x0 x1 , x1 x2 , . . . , xk−1 xk } (lihat [3]). Lintasan P diatas dapat dituliskan sebagai lintasan x0 − xk . Apabila untuk setiap pasangan titik u, v ∈ G terdapat lintasan u − v, maka graf G disebut terhubung. Dengan demikian lintasan adalah graf terhubung yang memiliki tepat dua titik berderajat 1 dan sisanya berderajat 2. Panjang dari lintasan P adalah banyaknya sisi pada P . Lintasan dengan panjang n, dinotasikan dengan Pn . Apabila d(u) = d(v) = 1 maka titik u dan titik v merupakan titik ujung lintasan. Titik dalam (internal vertex ) dari lintasan P : u − v adalah titik di P yang berbeda dengan u dan v. Koleksi {Pk1 , Pk2 , . . . , Pkn } dari lintasan u − v disebut internally disjoint jika setiap pasang lintasan tidak memiliki titik bersama kecuali u dan v.

Gambar 2.1: Graf G dengan beberapa subgrafnya

Misalkan G(V, E), graf H merupakan subgraf dari G jika V (H) ⊆ V (G) dan E(H) ⊆ E(G), ditulis dengan H ⊆ G. Kita dapat juga menyebutkan bahwa H termuat di G. Jika H ⊆ G dengan V (H) subhimpunan sejati dari V (G) atau E(H) merupakan subhimpunan sejati dari E(G) maka H merupakan subgraf sejati dari G. Gambar 2.1 memperlihatkan H sebagai subgraf G sekaligus juga merupakan subgraf sejati. Subgraf P pada Gambar 2.2 merupakan contoh dari lintasan dengan panjang


6

3.

Gambar 2.2: Lintasan P dan Siklus C, sebagai subgraf dari G

Graf C merupakan siklus, apabila C merupakan graf terhubung 2 − regular. Siklus dapat dituliskan dalam bentuk barisan titik-titik dengan titik awal sama dengan titik akhir, sedemikian sehingga titik-titik yang berurutan bertetangga. Ukuran atau panjang dari siklus dinyatakan dengan banyaknya titik pada siklus atau banyaknya sisi pada siklus. Jika banyaknya sisi siklus adalah bilangan genap maka disebut siklus genap, dan jika panjang siklus tersebut ganjil maka disebut siklus ganjil. Pada Gambar 2.2, C : u, v, y, x, w, u merupakan contoh siklus ganjil dengan panjang 5. Siklus dengan panjang n, untuk n ≥ 3 dinotasikan oleh Cn . Beberapa cara dapat digunakan untuk memperoleh graf yang baru dari graf yang ada. Cara-cara tersebut diantaranya dengan melakukan penjumlahan dan penggabungan. Penggabungan dua buah graf G dan H, dinotasikan dengan G∪H adalah sebuah graf dengan himpunan titik V (G ∪ H) = V (G) ∪ V (H) dan himpunan sisi E(G ∪ H) = E(G) ∪ E(H). Penjumlahan dua buah graf G dan H dinotasikan dengan G + H memuat G ∪ H dan semua sisi yang menghubungkan setiap titik di G dengan semua titik di H. Penjumlahan dari P3 dan K2 , P3 + K2 diperlihatkan pada Gambar 2.3.

2.1.1

Amalgamasi Titik dan Amalgamasi Sisi Pada Siklus

Definisi berikut ini diambil dari [4]. Misalkan {Gi , xi } adalah koleksi dari graf dengan setiap graf Gi memiliki sebuah titik xi yang tetap. Amalgamasi titik {(Gi , xi )}


7

Gambar 2.3: Penjumlahan dari dua buah Graf

dibentuk dari gabungan graf Gi dengan meleburkan titik xi . Siklus memiliki bentuk yang simetri, sehingga apabila graf Gi berbentuk siklus, maka pemilihan titik xi menjadi tidak relevan. Dengan kata lain pengambilan sebarang titik xi pada setiap Gi akan menghasilkan graf amalgamasi titik yang isomorfik. Gambar 2.5 memperlihatkan amalgamasi titik dari C3 dan C4 . Amalgamasi titik dari n buah siklus dinotasikan dengan amal{Cni }ni=1 , dengan n ≥ 2.

Gambar 2.4: Amalgamasi titik dari C3 dan C4

Misalkan {Gi , xi yi } adalah koleksi dari beberapa graf dengan setiap graf Gi memiliki sebuah sisi (xi yi ) yang tetap. Amalgamasi sisi {(Gi , xi yi )} dibentuk dari gabungan graf Gi dengan meleburkan sisi xi yi . Ketika Graf Gi berbentuk siklus, maka pemilihan sisi xi yi menjadi tidak relevan, karena siklus memiliki bentuk yang simetri. Gambar 2.5 memperlihatkan amalgamasi sisi dari C5 dan C6 . Amalgamasi sisi dari n buah siklus dinotasikan dengan edgeamal{Cni }ni=1 , dengan n ≥ 2.

2.1.2

Graf Theta yang diperumum

Berdasarkan [5], misalkan n ≥ 3, dan Pi untuk i = 1, 2, . . . , n adalah sebuah lintasan yang memiliki panjang li , dimana li = 1 untuk paling banyak sebuah i. Penyatuan titik ujung dari masing-masing lintasan, akan membentuk sebuah graf yang baru.


8

Gambar 2.5: Amalgamasi sisi dari C5 dan C6

Graf baru tersebut dinamakan graf theta yang diperumum dan dinotasikan dengan Θ(l1 , l2 , . . . , ln ). Dengan perkataan lain graf theta Θ(l1 , l2 , . . . , ln ) terdiri dari n buah lintasan dengan panjang l1 , l2 , . . . , ln yang memiliki sepasang titik bersama, yaitu titik ujung lintasan. Graf Θ(4, 4, 5, 6) dapat dilihat pada Gambar 2.6

Gambar 2.6: Graf Θ(4, 4, 5, 6)

Pada saat n = 3 graf theta yang diperumum merupakan graf theta dalam pendefinisian awal [5]. Apabila l1 = l2 = . . . = ln = a, penulisannya disederhanakan menjadi Θ(an .) Misalkan n ≥ 3, graf theta Θ(l1 , l2 , . . . , ln ) dengan li = 1 untuk suatu i, memiliki sebuah sisi yang menghubungkan kedua titik ujung lintasan, dengan kata lain merupakan graf amalgamasi sisi dari siklus


2.1.3

9

Pelabelan Total Tak Teratur Titik dan Total Vertex Irregularity Strength

Wallis [7] mendefinisikan pelabelan sebuah graf sebagai suatu pemetaan dari elemen graf terhadap himpunan bilangan (biasanya bilangan bulat positif atau bilangan bulat non negatif). Pelabelan titik adalah pelabelan dengan domain berupa titik. Jika domain dari pemetaan berupa sisi dari graf maka dinamakan pelabelan sisi. Sedangkan jika domainnya titik dan sisi dari graf maka pelabelan tersebut adalah pelabelan total. Jumlah seluruh label yang terkait dengan elemen dari sebuah graf disebut bobot. Sebagai contoh bobot dari titik v dengan pelabelan λ total terhadap graf G = (V, E) adalah, wt(v) = λ(v) +

X

λ(uv)

(2.1.1)

uv∈E

Misalkan G = (V, E). Pelabelan k − total didefinisikan sebagai pemetaan, λ : V ∪ E −→ {1, 2, . . . , k}.

Baˇ ca, Jendrol, Miller dan Ryan [2] mendefinisikan bahwa pelabelan k − total merupakan pelabelan k − total tak teratur titik dari graf G jika untuk setiap titik x dan y yang berbeda maka wt(x) 6= wt(y). Total vertex irregularity strength dari graf G atau tvs(G) adalah nilai k minimum sedemikian sehingga terdapat pelabelan k − total tak teratur titik. Gambar 2.7 adalah contoh pelabelan total tak teratur titik pada C4 . Pada kedua pelabelan tersebut dapat dilihat bahwa bobot pada setiap titik berbeda. Label terbesar pada pelabelan (a) adalah 3 sedangkan label terbesar pada pelabelan (b) adalah 2, hal tersebut memperlihatkan bahwa tvs(C4 ) ≤ 2. Apabila label yang terbesar adalah 1, maka setiap titik pada C4 memiliki bobot


10

Gambar 2.7: Pelabelan pada C4

yang sama yaitu 3, sehingga ketakteraturan titik tidak terpenuhi. Dengan demikian haruslah label terbesar pada C4 lebih besar dari 1. Akhirnya dapat disimpulan bahwa tvs(C4 ) = 2.

2.2

Hasil Penelitian Sebelumnya

Pada bagian ini disajikan hasil penelitian mengenai total vertex irregularity strength. Baˇ ca, dan rekan [2] menunjukkan batas bawah dan batas atas nilai dari total vertex irregularity strength untuk sebarang graf. Teorema 2.1. [2] Misalkan G adalah graf (p,q) dengan derajat minimum δ = δ(G) derajat maksimum ∆ = ∆(G), maka dan p+δ ≤ tvs(G) ≤ p + ∆ − 2δ + 1. ∆+1 Selain menemukan nilai batas untuk sebarang graf, Baˇ ca dan rekan [2] juga memperoleh nilai total vertex irregularity strength untuk beberapa kelas graf. Teorema 2.2. [2] Untuk n ≥ 2, tvs(Kn ) = 2. Wijaya dan rekan [8] pada tahun 2005 menunjukkan beberapa nilai tvs untuk graf bipartit lengkap. Graf G merupakan graf bipartit, jika V (G) dapat dipartisi menjadi dua buah subhimpunan U dan W yang disebut himpunan partisi sedemikian sehingga setiap sisi di G menghubungkan titik di U dengan titik di W . Jika titik di U bertetangga dengan setiap titik di W , maka G dinamakan graf bipartit lengkap K|U |,|W | . Beberapa graf yang telah ditentukan nilai tvsnya adalah K2,n , Kn,n , Kn,n+1 , Kn,n+2 dan Kn,an . Namun sebelumnya Baˇ ca dan rekan [2] telah


11

menemukan tvs untuk graf bintang K1,n , yang tidak lain adalah graf bipartit lengkap dengan n + 1 titik. Teorema 2.3. n+1[8] Misal (K1,n ) adalah bintang dengan n titik berderajat 1. Maka, tvs(K1,n ) = 2 . Sejauh ini, untuk graf bipartit Km,n dengan m ≤ n baru diperoleh batas bawahnya. Teorema 2.4. [8] Jika m ≤ n tetapi (m, n) 6= (2, 2) , maka , 2m+n−1 }. tvs(Km,n ) ≥ maks d m+n m+1 n Pada tahun 2008 Wijaya dan Slamin [9] memperoleh nilai tvs untuk beberapa kelas graf yang lain, yaitu graf roda (Wn ), kipas (Fn ), matahari (Sn) dan friendship (fn ). Graf Roda Wn diperoleh dari penjumlahan Cn + K1 . Nilai tvs dari graf roda dapat dilihat pada teorema berikut ini. Teorema 2.5. [9] tvs(Wn ) = n+3 ; untuk n ≥ 3. 4 Selain menentukan tvs untuk graf roda (Wn ), Wijaya dan rekan [9] juga memperoleh nilai tvs untuk graf kipas Fn . Graf kipas Fn memiliki (n + 1) titik. Banyak titik berderajat 3 adalah (n − 2) , titik berderajat 2 sebanyak 2, dan sebuah titik berderajat n. Graf kipas Fn diperoleh dari penjumlahan Pn + K1 . Teorema 2.6. [9] tvs(Fn ) = n+2 ; untuk n ≥ 3. 4 Kelas graf lain yang telah ditemukan nilai tvsnya adalah graf matahari Sn dan graf friendship fn . Graf matahari adalah graf yang diperoleh dari graf siklus Cn dengan menambahkan tepat sebuah pendan (titik berderajat 1) pada setiap titik di Cn . Sedangkan graf frienship fn , graf yang diperoleh dari penjumlahan nK2 + K1 . Dua teorema di bawah ini, memperlihatkan nilai tvs dari graf matahari Sn dan graf friendship fn . n+1

; untuk n ≥ 3. 2 2n+2 Teorema 2.8. [9] tvs(fn ) = ; untuk n ≥ 3. 3 Teorema 2.7. [9] tvs(Sn ) =

Bab 2. Landasan Teori. 2.1 Konsep Dasar

Recommend Documents