BAB I PENDAHULUAN. 1.1 Latar Belakang Masalah

BAB I PENDAHULUAN

1.1 Latar Belakang Masalah Teori graf merupakan salah satu cabang matematika yang banyak berperan dalam pengembangan matematika dari sisi teori maupun terapannya. Beberapa masalah dalam dunia nyata dapat diselesaikan menggunakan konsep-konsep dalam teori graf, misal masalah jaringan di bidang ilmu komputer, riset operasi, komunikasi, dan ilmu-ilmu sosial atau ilmu pengetahuan alam (Chartrand (1977), Deo (1980)). Graf G dapat dituliskan sebagai G(V, E) dengan V menyatakan himpunan titik dan E menyatakan himpunan sisi. Dalam representasi graf, titik dinyatakan sebagai bulatan kecil atau noktah, sedangkan sisi dinyatakan sebagai garis yang menghubungkan dua titik. Graf yang terdiri dari himpunan titik dan sisi dapat merepresentasikan suatu bentuk jaringan. Ada beberapa bentuk jaringan yang dapat direpresentasikan oleh graf, antara lain yang banyak dikenal adalah graf bentuk bintang (star), lingkaran (cycle), lintasan (path), roda (wheel), gir (gear), helm, web, firecracker, banana tree, kipas (fan), dan lain-lain (Wallis, 2001). Di antara bidang-bidang kajian yang ada di teori graf, pelabelan graf merupakan salah satu bidang kajian yang banyak diteliti sehingga penelitian di bidang ini mengalami perkembangan yang sangat pesat. Menurut Gallian (2014), sejak sekitar tahun 1960 sampai saat ini sudah lebih dari 2000 paper yang membahas pelabelan pada graf. Beberapa jenis pelabelan graf dapat diterapkan untuk menyelesaikan kasus-kasus nyata, misalnya pada penentuan kode channel stasiun radio ataupun kode pada jaringan komputer yang dapat dilihat di Bloom dan Golomb (1977), Jin dan Yeh (2004), Clipperton (2008), Indriati, dkk. (2012, 2014). Selain itu, contoh penerapan yang lain adalah pada distribusi pemasaran menggunakan pelabelan yang dapat dilihat di Indriati dan Roswitha (2009a, 2009b, 2010) serta Indriati (2011). Ada beberapa jenis pelabelan pada graf yang dapat dilihat di Gallian (2014), dan salah satunya yang akan dibahas pada penelitian ini adalah pelabelan total tak 1

2 reguler (irregular total labeling). Pada awalnya, pelabelan total tak reguler dikelompokkan ke dalam pelabelan total tak reguler sisi (edge irregular total labeling) dan pelabelan total tak reguler titik (vertex irregular total labeling). Selanjutnya pada perkembangannya dikenal pelabelan total tak reguler total (totally irregular total labeling). Misalkan G(V, E), yang untuk selanjutnya dituliskan dengan G, adalah graf sederhana, yaitu graf yang tidak memuat loop dan sisi paralel. Menurut Wallis (2001), pelabelan suatu graf adalah pemetaan (fungsi) yang membawa elemen-elemen graf ke bilangan-bilangan bulat positif atau non-negatif. Jika domain pemetaan adalah himpunan titik (V ), maka pelabelan disebut pelabelan titik (vertex labeling), yaitu fungsi f : V → Z≥0 . Jika domainnya adalah himpunan sisi (E ), maka pelabelan disebut pelabelan sisi (edge labeling), yaitu fungsi f : E → Z≥0 . Jika domainnya adalah himpunan titik maupun sisi (V ∪ E ) maka pelabelan disebut pelabelan total (total labeling), yaitu fungsi f : V ∪ E → Z≥0 . Suatu pelabelan-k total adalah pelabelan total f : V ∪ E → {1, 2, 3, . . . , k} dengan k adalah bilangan bulat. Beberapa penelitian terbaru menunjukkan bahwa pelabelan dapat dilakukan dengan cara mengaitkan jumlah label dengan elemen-elemen graf. Jumlah label ini dikenal sebagai bobot (weight) dari elemen graf. Misalkan diketahui pelabelan total f : V ∪ E → {1, 2, 3, . . .}. Bobot titik x pada pelabelan total f dari elemen-elemen

graf G = (V, E) didefinisikan sebagai berikut (Wallis, 2001): wt(x) = f (x) + Σxy∈E f (xy)

dan bobot sisi xy sebagai wt(xy) = f (x) + f (xy) + f (y)

Pada tahun 1970, Kotzig dan Rosa (Gallian, 2014) mendefinisikan pelabelan total sisi ajaib pada graf G(V, E) yang merupakan fungsi bijektif f : V ∪ E → {1, 2, 3, ..., |V ∪ E|}

dengan |V ∪ E| adalah kardinalitas (banyak anggota) dari gabungan himpunan V dan E , sehingga untuk setiap sisi xy ∈ E berlaku bobot sisi-sisi tersebut sama (konstan). Bobot sisi xy yaitu nilai f (x) + f (y) + f (xy) yang konstan tersebut

3 disebut konstanta ajaib (magic constant). Salah satu aplikasi dari pelabelan tersebut adalah untuk penentuan internet protocol (IP) address pada suatu jaringan komputer (Dafik, 2015). Misal terdapat 6 komputer yang terhubung ke server dengan bentuk jaringan bintang (star). Pada tiap-tiap komputer harus diberikan IP address yang bersifat rahasia supaya tidak dimanfaatkan orang lain yang tidak berhak. Untuk memudahkan pendeteksian, harus diberikan pengkodean secara teratur pada penomoran IP address. Namun demikian, jika ada masalah terhadap jaringan, IP address masing-masing komputer harus dapat dideteksi dengan mudah. Salah satu cara adalah dengan memberikan tag code pada kabel penghubungnya. Jadi, permasalahannya adalah bagaimana mengembangkan tag code yang sekaligus bisa mendeteksi nomor IP address yang dirahasiakan. Gambar 1.1 berikut memberikan ilustrasi kasus tersebut di atas. Pada gambar ini, konstanta ajaibnya adalah M = 16.

192.168.13.3

192.168.13.4

192.168.13.2

12 13

11 192.168.13.1

8

10 9

192.168.13.5

192.168.13.7

192.168.13.6

Gambar 1.1 Jaringan komputer berbentuk bintang (Dafik, 2015)

Pada perkembangannya, dipelajari kondisi bobot sisi atau titik pada graf berlainan dan label bisa dipakai lebih dari sekali (fungsi tidak bijektif). Baˇca dkk. (2007) telah mengenalkan jenis pelabelan baru tersebut, yaitu pelabelan total tak reguler sisi dan pelabelan total tak reguler titik. Ide ini dikemukakan pada tahun 2002, namun baru diterbitkan pada tahun 2007. Menurut Baˇca dkk. (2007), pemetaan f :

4 V ∪ E → {1, 2, 3, . . . , k} disebut pelabelan-k total tak reguler sisi (edge irregular

total k-labeling) pada G, jika pada setiap pasang sisi yang berlainan di G, xy 6= uv , mempunyai bobot yang berbeda, yaitu f (x)+f (xy)+f (y) 6= f (u)+f (uv)+f (v). Kekuatan tak reguler sisi total (total edge irregularity strength) dari graf G, dinotasikan dengan tes(G), didefinisikan sebagai bilangan bulat positif terkecil k sehingga G mempunyai pelabelan-k total tak reguler sisi. Penentuan kekuatan tak reguler si-

si total suatu graf bukan hal yang mudah sebab hal tersebut sangat dipengaruhi oleh struktur dan karakteristik suatu graf. Baˇca dkk. (2007) telah menemukan batas bawah dan batas atas tes(G) untuk sebarang graf G sebagai berikut. Misalkan G adalah suatu graf dengan banyak sisi |E| pada G, diperoleh ' & |E| + 2 ≤ tes(G) ≤ |E|. 3

(1.1)

Selain itu, dikaitkan dengan derajat maksimum suatu titik, yaitu maksimum banyaknya sisi yang insiden ke titik, pada sebarang graf G, Baˇca dkk. (2007) juga memberikan batas bawah dari tes(G) sebagai berikut. Misal G adalah graf dengan derajat maksimum 4 = 4(G), maka & tes(G) ≥

' 4+1 . 2

(1.2)

Dengan menggunakan hasil tersebut dan memperhatikan struktur grafnya, Baˇca dkk. (2007) telah mendapatkan kekuatan tak reguler sisi total untuk graf lintasan, graf lingkaran, graf bintang, graf lengkap K5 , graf roda dan graf friendship. Selain itu, beberapa peneliti lain telah menemukan kekuatan tak reguler sisi total untuk beberapa graf, antara lain Mikuf dan Jendrol’ (2007) untuk graf grid, Jendrol’ dkk. (2010) untuk graf lengkap dan bipartit lengkap, Nurdin dkk. (2006a, 2006b, 2008) masing-masing untuk graf gabungan K2,n , hasil korona (corona product) antara lingkaran dan komplemen graf lengkap dan hasil korona antara graf lintasan dengan beberapa graf. Ahmad dan Baˇca (2014) meneliti pada hasil kategorik (categorical product) dari 2 graf lintasan. Haque (2012) meneliti pada graf Petersen yang diperumum dan Siddiqui (2012) pada subdivisi graf bintang. Kekuatan tak reguler sisi total untuk graf berbentuk pohon (tree) secara umum ditemukan oleh

5 Ivanˇco dan Jendrol’ (2006) sebagai berikut. Untuk semua graf pohon T dengan derajat maksimum titiknya 4 dan banyaknya sisi |E|, diperoleh ' & ') (& |E| + 2 4+1 , . tes(T ) = maks 2 3

(1.3)

Dari penelitian-penelitian yang sudah ada, kekuatan tak reguler sisi total untuk graf sederhana secara umum belum ditemukan. Namun demikian, Ivanˇco dan Jendrol’ (2006) telah memberikan konjektur untuk kekuatan tak reguler sisi total suatu graf G sebagai berikut. Konjektur 1.1.1 (Ivanˇco dan Jendrol’, 2006). Jika G adalah suatu graf yang bukan graf K5 dengan derajat maksimum titik 4, maka (& ' & ') 4+1 |E| + 2 tes(G) = maks , . 2 3 Karena graf sederhana dapat dikelompokkan menjadi graf pohon (graf yang tidak memuat lingkaran) dan graf cyclic (graf yang memuat lingkaran), sedangkan kekuatan tak reguler sisi total untuk graf pohon sudah ditemukan oleh Ivanˇco dan Jendrol’ (2006) yang dapat dilihat di persamaan (1.3), maka pada penelitian ini dikaji kekuatan tak reguler sisi total untuk graf cyclic yang hasilnya akan ditinjau kaitannya dengan Konjektur 1.1.1. Selain mengenalkan pengertian kekuatan tak reguler sisi total suatu graf, Baˇca dkk. (2007) juga mengenalkan pengertian kekuatan tak reguler titik total suatu graf sebagai berikut. Pemetaan f : V ∪E → {1, 2, 3, . . . , k} disebut pelabelan-k total tak reguler titik (vertex irregular total k-labeling) pada graf sederhana G, jika setiap pasang titik yang berlainan pada G, x 6= u, mempunyai bobot tidak sama, yaitu f (x) + Σxy∈E f (xy) 6= f (u) + Σuv∈E f (uv). Kekuatan tak reguler titik total (total vertex irregularity strength) dari graf G, dinotasikan dengan tvs(G), didefinisikan sebagai bilangan bulat positif terkecil k sehingga G mempunyai pelabelan-k total tak reguler titik. Penentuan kekuatan tak reguler titik total suatu graf juga bukan hal yang mudah dilakukan dan sampai saat ini belum diperoleh hasil untuk graf secara umum. Namun demikian Baˇca dkk. (2007) telah menghasilkan batas bawah dan batas atas kekuatan tak reguler titik total untuk graf dengan p titik dan q sisi

6 (dinotasikan dengan (p, q )-graph), yang mempunyai derajat minimum δ atau δ(G) dan derajat maksimum 4 atau 4(G) yaitu &

p+δ 4+1

' ≤ tvs(G) ≤ p + 4 − 2δ + 1.

(1.4)

Pada artikel yang sama, Baˇca dkk. (2007) juga telah menghasilkan kekuatan tak reguler titik total untuk graf bintang, graf lengkap, graf lingkaran dan graf prisma. Nurdin dkk. (2010) telah menghasilkan kekuatan tak reguler titik total pada graf pohon T yang mempunyai n1 titik daun dan tidak memuat titik berderajat 2, sebagai berikut & tvs(T ) =

' n1 + 1 . 2

(1.5)

Selain itu, Przbylo (2008, 2009) meneliti kekuatan tak reguler titik total pada graf reguler. Wijaya dan Slamin (2008) serta Wijaya dkk. (2005) telah memperoleh kekuatan tak reguler titik total untuk graf roda, graf kipas, graf matahari, graf friendship dan graf bipartit lengkap. Haque (2012) melakuan penelitian pada graf Petersen yang diperumum sedangkan Siddiqui dan Afzal (2011) meneliti pada subdivisi graf bintang. Selanjutnya Slamin dkk. (2012) bekerja pada gabungan disjoin dari beberapa graf matahari. Anholcer dkk. (2009) meneliti kekuatan tak reguler titik total pada graf dengan memperhatikan derajat titik minimumnya. Anholcer dkk. (2011) juga meneliti untuk graf hutan (himpunan dari beberapa graf pohon). Diberikan graf hutan F yang tidak memuat titik berderajat dua dan tidak memuat titik terisolasi dengan n1 menyatakan banyaknya titik yang berderajat satu (disebut titik & ' daun) dalam F . Kekuatan tak reguler titik total graf F adalah tvs(F ) =

n1 +1 2

.

Dari hasil-hasil penelitian di atas, kekuatan tak reguler titik total untuk graf secara umum belum diperoleh, tetapi untuk graf pohon yang berarti graf yang tidak memuat lingkaran, dengan memperhatikan banyaknya titik daun, telah diperoleh (pada persamaan (1.5)). Namun demikian, Nurdin dkk. (2010) memberikan suatu konjektur untuk kekuatan tak reguler titik total suatu graf terhubung G sebagai berikut. Konjektur 1.1.2 (Nurdin dkk., 2010). Jika G adalah suatu graf terhubung yang mempunyai sebanyak ni titik berderajat i, δ ≤ i ≤ 4, dengan δ dan 4 berturut-

7 turut menyatakan derajat minimum dan derajat maksimum untuk semua titik di G, maka ( tvs(G) = maks

& ') P n δ+ ∆ δ + nδ + nδ+1 δ + nδ i=δ i , ,..., . δ+1 δ+2 ∆+1

Seperti dikemukakan di atas, graf terhubung dapat dikelompokkan menjadi graf yang tidak memuat lingkaran (acyclic) dan graf memuat lingkaran (cyclic ). Karena pada graf yang tidak memuat lingkaran dengan memperhatikan banyaknya titik daun telah diperoleh kekuatan tak reguler titik totalnya (pada (1.5)), maka pada penelitian ini dikaji kekuatan tak reguler titik total pada graf yang cyclic dengan memperhatikan banyaknya titik daun pula, yang hasilnya akan ditinjau kaitannya dengan Konjektur 1.1.2. Pada perkembangannya, apabila persyaratan tak reguler diberlakukan pada bobot sisi dan bobot titiknya secara simultan, diperoleh pelabelan baru yang disebut pelabelan total tak reguler total (totally irregular total labeling) (Marzuki dkk., 2013). Apabila label terbesar pada sisi atau titiknya adalah k , maka pelabelan tersebut disebut pelabelan-k total tak reguler total (totally irregular total k-labeling). Nilai k yang minimum untuk semua pelabelan-k total tak reguler total yang mungkin pada suatu graf G disebut kekuatan tak reguler total (total irregularity strength), dan dinotasikan dengan ts(G). Menurut sepengetahuan penulis, baru ada 3 publikasi untuk pelabelan jenis ini, yaitu Marzuki dkk (2013), Ramdani dan Salman (2013) dan Ramdani dkk. (2015). Untuk kekuatan tak reguler total graf G, Marzuki dkk.(2013) mengemukakan suatu observasi bahwa ts(G) ≥ maks{tes(G), tvs(G)}.

(1.6)

Selain itu juga telah ditemukan kekuatan tak reguler total pada graf-graf lingkaran dan lintasan. Ramdani dan Salman (2013) telah memperoleh kekuatan tak reguler total pada beberapa graf hasil ganda Kartesius antara graf bintang K1,n dengan graf lintasan P2 , graf lintasan Pn dengan graf lintasan P2 , joint graf lintasan Pn dan P1 dengan graf lintasan P2 , dan graf lingkaran Cn dengan graf lintasan P2 . Ramdani dkk. (2015) juga telah menghasilkan kekuatan tak reguler total pada graf-graf gir, jamur fungus dan gabungan saling lepas graf bintang. Berdasarkan penelusuran penulis, sampai sejauh ini belum ditemukan kekuatan tak

8 reguler total pada graf pohon secara umum. Oleh karena itu untuk menuju ke hasil pada graf pohon secara umum, perlu dikaji penentuan kekuatan tak reguler total pada beberapa graf yang termasuk graf pohon. 1.2 Perumusan Masalah Berdasarkan latar belakang di atas, pada penelitian ini dikaji pelabelan total tak reguler sisi maupun titik pada graf-graf cyclic dan pelabelan total tak reguler total pada graf-graf pohon, serta diamati sifat karakteristik yang muncul berkaitan dengan bentuk graf. Secara lebih detil, perumusan masalahnya sebagai berikut: 1. Menentukan kekuatan tak reguler sisi total untuk beberapa graf cyclic. 2. Menentukan kekuatan tak reguler titik total untuk beberapa graf cyclic dan yang memuat titik daun. 3. Menentukan kekuatan tak reguler total pada beberapa graf pohon. 4. Menyelidiki sifat-sifat karakteristik yang muncul pada pelabelan graf item 1, 2 dan 3 dikaitkan dengan bentuk graf dan nilai kekuatan tak regulernya. 1.3 Batasan Masalah Supaya lingkup pembahasan tidak meluas, penelitian ini dilakukan dengan beberapa pembatasan sebagai berikut: 1. Graf yang dibahas adalah graf sederhana (graf yang tidak memuat loop dan sisi paralel), berhingga, dan tidak berarah. 2. Pelabelan total tak reguler sisi/titik diterapkan pada beberapa graf cyclic yang konstruksi awalnya graf lingkaran, sedangkan pelabelan total tak reguler total diterapkan pada graf pohon yang konstruksi awalnya graf bintang, dalam hal ini adalah graf bintang, dobel-bintang dan caterpillar yang dibentuk dari graf dobel-bintang dengan menyisipkan satu titik pada sisi yang insiden ke dua pusat bintang. 3. Label yang digunakan adalah bilangan bulat positif.

9

1.4 Tujuan Penelitian Tujuan penelitian ini adalah 1. Menentukan kekuatan tak reguler sisi total untuk beberapa graf cyclic. 2. Menentukan kekuatan tak reguler titik total untuk beberapa graf cyclic yang mempunyai titik daun. 3. Menentukan kekuatan tak reguler total pada beberapa graf pohon. 4. Memperoleh sifat-sifat karakteristik pelabelan dikaitkan dengan bentuk graf dan nilai kekuatan tak regulernya. 1.5 Manfaat Penelitian Manfaat penelitian ini adalah: 1. Memberikan wawasan tentang keterkaitan nilai kekuatan tak reguler sisi total maupun titik total antara graf cyclic dengan graf pohon yang sudah dihasilkan oleh peneliti terdahulu. 2. Memberikan wawasan tentang keterkaitan nilai kekuatan tak reguler total antara graf caterpillar dengan kekuatan tak reguler titik total graf pohon yang sudah dihasilkan oleh peneliti terdahulu. 3. Memperoleh proposisi, lemma dan teorema baru, yang implikasinya akan memperkaya teori di bidang graf, khususnya pada pelabelan tak reguler graf. Hasil penelitian ini juga memunculkan masalah-masalah terbuka (open problems) diharapkan akan mendorong peneliti lain untuk melanjutkan penelitian serta mempertajam dan memperluas temuan. 1.6 Tinjauan Pustaka Konsep pelabelan graf dikenalkan oleh Sedlˇcek pada tahun 1963 dengan memunculkan pengertian pelabelan ajaib (magic labeling), yaitu pemberian label pada sisi-sisi suatu graf menggunakan bilangan real sehingga untuk setiap titik

10 x ∈ V jumlah label dari semua sisi yang berinsidensi dengan x sama untuk se-

mua x. Dengan kata lain, pelabelan ajaib adalah fungsi f : E → R sehingga untuk setiap x ∈ V , berlaku Σxy∈E f (xy) sama. Dengan definisi yang sama, jika berlaku Σxy∈E f (xy) berbeda untuk setiap titik x, maka pelabelan disebut anti ajaib (anti

magic labeling). Konsep pelabelan ajaib kemudian diperluas dengan pemberian label tidak hanya pada sisi, namun juga pada titik-titik graf, yang disebut dengan pelabelan total. Kotzig dan Rosa pada tahun 1970 mendefinisikan pelabelan total sisi ajaib pada graf G yaitu fungsi bijektif f : V ∪ E → {1, 2, 3, ..., |V ∪ E|} sehingga untuk setiap sisi xy ∈ E berlaku bobot sisi-sisi tersebut sama, yaitu suatu konstanta yang disebut konstanta ajaib (magic constant) (Gallian, 2014). MacDougall dkk. (2002a) mengenalkan pelabelan total titik ajaib, f : V ∪ E → {1, 2, 3, ..., |V ∪ E|} yang merupakan fungsi ajaib sehingga untuk setiap titik x ∈ V berlaku bobot titik-titik tersebut sama, nilai f (x) + Σxy∈E f (xy) konstan, yang disebut konstanta ajaib (magic constant). Beberapa penelitian yang terkait dengan pelabelan total ajaib sudah dilakukan, antaranya oleh Calhoun dkk. (2005), membahas open problem dari buku Wallis (2001) tentang pelabelan total ajaib pada graf mK3 , Fronˇcek dkk. (2005) yang meneliti pelabelan total ajaib pada perkalian graf lingkaran, Balbuena dkk. (2006) membahas graf-graf yang mempunyai pelabelan ajaib yang konsekutif, Sugeng dan Miller (2008) meneliti tentang pelabelan total sisi ajaib yang konsekutif, Sugeng dkk. (2009) meneliti pelabelan ajaib berdasar jarak, MacDougall dkk. (2002b) meneliti pelabelan total titik ajaib pada graf roda dan graf-graf yang terkait. Hartsfield dan Ringel (1990) mengenalkan pelabelan anti ajaib, yaitu fungsi f : E → {1, 2, 3, . . .} sehingga untuk setiap x ∈ V , berlaku Σxy∈E f (xy) tidak

sama. Untuk pelabelan yang anti ajaib beberapa penelitian yang sudah dilakukan antara lain oleh Baˇca dan Murugan (2006) yang membahas pelabelan anti ajaib sisi super pada graf lingkaran yang memuat chord, Sugeng dkk.(2011) yang membahas tentang pelabelan ajaib dan anti ajaib pada gabungan 4-reguler graf circulant, Sugeng dan Bong (2010) membahas pelabelan total (a, d)-anti ajaib pada graf circulant, Baˇca dan Youssef (2007) yang meneliti graf-graf yang tidak mempunyai pelabelan anti ajaib sisi dan cara mengkonstruksi pelabelan untuk graf lingkaran.

11 Hasil yang lebih lengkap dapat dilihat di hasil survey Gallian (2014). Jika bobot sisi ataupun titik pada suatu graf tidak sama untuk setiap sisi/ titik, maka pelabelannya disebut pelabelan tak reguler (irregular labeling). Konsep pelabelan tak reguler pada suatu graf dikenalkan pertama kali oleh Chartrand, dkk. melalui makalah ”irregular Network” pada tahun 1986 (tetapi baru terbit pada tahun 1988). Menurut Chartrand, pelabelan tak reguler adalah pemetaan f : E → {1, 2, 3, . . .} dengan syarat bobot setiap titiknya berbeda, yaitu Σxy∈E f (xy) 6= Σuv∈E f (uv) untuk setiap titik x, u ∈ V dengan x 6= u. Kekuatan tak reguler

(irregularity strength) dari graf G, dinotasikan s(G), adalah bilangan bulat positif terkecil k dari graf G yang mempunyai pelabelan tak reguler dengan k adalah label terbesar untuk tiap sisi pada graf G. Beberapa penelitian yang terkait dengan pelabelan tak reguler diantaranya adalah Amar (1993) yang menentukan kekuatan tak reguler pada graf reguler, Amar dan Togni (1998) menentukan kekuatan tak reguler dari graf pohon, Jendrol’ dan oldk (1995) menentukan kekuatan tak reguler dari graf Petersen yang diperumum, Ferrara dkk. (2009) meneliti tentang kekuatan tak reguler dari graf berarah. Ferrara dkk. (2010) membahas tentang algoritma untuk menentukan kekuatan tak reguler pada graf pohon. Seperti pada pelabelan ajaib, konsep pelabelan tak reguler kemudian diperluas dengan pemberian label tidak hanya pada sisi, namun juga pada titik-titik graf, yang disebut dengan pelabelan total. Hal ini dikenalkan oleh Baˇca dkk. (2007) yang idenya dimunculkan sejak tahun 2002. Pada bidang pelabelan ini, beberapa penelitian sudah dilakukan seperti disampaikan di Latar Belakang, namun hasil umum untuk kekuatan tak reguler sisi total baru didapatkan untuk graf pohon, begitu pula kekuatan tak reguler titik total baru diperoleh untuk graf pohon dengan memperhatikan banyaknya titik daun. Beberapa peneliti terdahulu sudah menemukan kekuatan tak reguler sisi/ titik total untuk beberapa graf khusus yang cyclic, namun formula umum belum ditemukan. Oleh karena itu penelitian ini akan dilakukan untuk menuju ke formula kekuatan tak reguler sisi total pada graf cyclic secara umum, dan untuk kekuatan tak reguler titik total dilakukan penelitian juga pada graf cyclic (yang memuat titik daun). Beberapa hasil penelitian terdahulu pada graf cyclic di-

12 antaranya adalah sebagai berikut. a. Penelitian terdahulu untuk pelabelan total tak reguler sisi pada graf cyclic 1. Nurdin dkk. (2006b) menemukan kekuatan tak reguler sisi total untuk hasil korona antara graf lingkaran Cm dengan komplemen dari graf lengkap Kn dengan nilai (n+1)m+2 , untuk m ≥ 3, n ≥ 1. 3 2. Baˇca dkk. (2007) telah menemukan kekuatan tak reguler sisi total un tuk graf lingkaran yaitu tes(Cn ) = n+2 , n ≥ 3; graf roda yaitu 3 2n+2 tes(W n) = , n ≥ 3 dan untuk graf friendship fn , diperoleh 3 3n+2 tes(fn ) = , dengan n adalah banyaknya triangle. 3 3. Miskuf dan Jendrol’(2007) telah menemukan kekuatan tak reguler sisi total hasil ganda Kartesius dua graf lintasan Pm dan Pn dengan nilai (2mn−n−m+2 . 3 4. Nurdin dkk. (2008) menemukan kekuatan tak reguler sisi total untuk hasil korona antara graf lintasan Pm dengan graf lingkaran Cn sebesar (2n+1)m+1 , untuk m ≥ 2, n ≥ 3. 3 5. Jendrol’dkk. (2010) telah menemukan kekuatan tak reguler sisi total un 2 untuk sebarang n ≥ 6 tuk graf lengkap Kn , yaitu tes(Kn ) = n −n+4 6 mn+2 dan graf bipartit lengkap, yaitu tes(Km, n) = , m ≥ n > 1. 3 6. Haque (2012) menemukan kekuatan tak reguler sisi total untuk graf Petersen yang diperumum P (n, k), yaitu tes(P (n, k)) = n + 1 jika k 6= n/2 dan tes(P (n, k)) = 5n+4 untuk k = n/2 dengan n − 1 ≥ k ≥ 1. 6 7. Ahmad, dan Bacˇa (2014) telah menemukan kekuatan tak reguler sisi total pada hasil kategorik (categorical product) dari 2 lintasan. b. Penelitian terdahulu untuk pelabelan total tak reguler titik pada graf cyclic. 1. Wijaya dkk. (2005) menemukan kekuatan tak reguler titik total untuk 2m+n−1 graf bipartit lengkap Km,n , yaitu tvs(Km, n) ≥ maks m+n , m+1 n untuk (m, n) 6= (2, 2).

13 2. Baˇca dkk. (2007) telah menemukan kekuatan tak reguler titik total untuk graf lengkap Kn , yaitu tvs(Kn ) = 2, n ≥ 2; graf lingkaran Cn dengan , n ≥ 3 dan graf prisma bersisi n dengan n ≥ 3, tvs(Cn ) = n+2 3 2n+3 senilai 4 . 3. Wijaya dan Slamin (2008) telah menemukan kekuatan tak reguler titik total untuk graf roda Wn , yaitu tvs(Wn ) = n+3 , n ≥ 3; graf kipas 4 n+2 Fn , yaitu tvs(Fn ) = 4 , n ≥ 3; graf matahari Sn , yaitu tvs(Sn ) = n+1 2n+2 , n ≥ 3 dan graf friendship f , yaitu tvs(f n) = , untuk n 2 3 semua n. 4. Haque (2012) telah menemukan kekuatan tak reguler titik total untuk graf Petersen yang diperumum, yaitu tvs(P (n, k)) = n2 +1 jika k 6= n/2 dan tvs(P (n, k)) =

n 2

+ 1 untuk k = n/2 dengan n − 1 ≥ k ≥ 1.

5. Slamin dkk.(2012) telah menemukan kekuatan tak reguler titik total untuk gabungan disjoin graf matahari sMn , yaitu gabungan disjoin sebanyak s graf isomorfik dengan graf matahari Mn , diperoleh tvs(sM n) = sn+1 untuk s ≥ 1 dan n ≥ 3. 2 6. Ahmad dkk. (2012) telah meneliti tentang pelabelan total tak reguler titik pada gabungan saling asing graf helm. 7. Ahmad dkk. (2014) telah menemukan kekuatan tak reguler titik total pada klas graf yang unicyclic. Pada perkembangannya, Marzuki dkk. (2013) menggabungkan konsep pelabelan total tak reguler sisi dan pelabelan total tak reguler titik menjadi pelabelan total tak reguler total, yaitu pelabelan dengan bobot sisi maupun titiknya berbeda secara simultan untuk setiap sisi/ titik pada graf. Label terbesar yang minimum pada pelabelan ini disebut kekuatan tak reguler total, dinotasikan dengan ts(G). Sepengetahuan peneliti, baru ada 3 publikasi yang membahas pelabelan jenis ini, yaitu Marzuki dkk.(2013), Ramdani dan Salman (2013), dan Ramdani dkk.(2015). Oleh karena itu pada penelitian ini akan dilakukan kajian untuk jenis pelabelan tersebut, yang pada awalnya dimulai untuk graf-graf pohon.

14 Berikut ini hasil penelitian terdahulu untuk pelabelan total tak reguler total pada graf. 1. Marzuki dkk. (2013) telah menemukan kekuatan tak reguler total untuk graf , n ≥ 3; graf lintasan Pn yaitu lingkaran  Cn yaitu ts(Cn ) = n+2 3   n+2 , untuk n = 2 atau 5, 3 . ts(Pn ) =   n+1 , untuk n lainnya. 3 Selain itu juga observasi untuk batas bawah kekuatan tak reguler total graf G yaitu ts(G) ≥ max{tes(G), tvs(G)}. Untuk graf hutan T (V, E) dengan |V | ≥ 2, diperoleh ts(T ) ≤ 2|V | − 2. 2. Ramdani dan Salman (2013) telah menemukan kekuatan tak reguler total untuk graf-graf hasil ganda Kartesius graf matahari Sn dan graf lintasan P2 senilai n + 1, n ≥ 3, join graf Pn dan P1 dengan graf lintasan P2 senilai 5n+1 , n ≥ 3, graf lintasan Pn dengan P2 senilai n, n ≥ 3, dan hasil ganda 3 Kartesius graf lingkaran Cn dengan graf lintasan P2 senilai n + 1, n ≥ 3. 3. Ramdani dkk. (2015) telah memperoleh kekuatan tak reguler total untuk grafgraf gir, jamur fungus dan gabungan saling lepas graf bintang. Berdasarkan uraian pada Tinjauan Pustaka di atas, berikut ini diberikan diagram jenis pelabelan graf (yang memperhatikan bobot sisi atau titik graf) serta peneliti awal yang mengenalkan dan beberapa hasil penting yang terkait dengan penelitian ini. Pada diagram tersebut ditunjukkan alur ke permasalahan yang dikaji, dapat dilihat di Gambar 1.2.

15

Gambar 1.2 Diagram pelabelan graf (Gallian, 2014)

16

1.7 Metodologi Penelitian Penelitian ini merupakan penelitian yang didasarkan pada studi pustaka yang bersifat teoritis. Untuk menyelesaikan permasalahan yang ada di Subbab 1.2, dilakukan tahapan-tahapan sebagai berikut. 1. Menyelesaikan permasalahan 1, yaitu menentukan kekuatan tak reguler sisi total (tes(G)) pada beberapa graf cyclic G (graf yang memuat lingkaran) dan membuktikan nilai (tes(G)) tersebut dalam bentuk lemma ataupun teorema. Untuk menentukan kekuatan tak reguler sisi total graf, dicari batas bawah dan batas atasnya. Menurut Baˇca dkk. (2007), batas bawah ditentukan dengan memperhatikan banyak sisi graf dan minimum label terbesar dari sisisisi tersebut. Sedangkan batas atas ditentukan dengan cara mengkonstruksi suatu pelabelan total pada graf sehingga mempunyai label terbesar seminimum mungkin. Dari pelabelan tersebut selanjutnya ditentukan label terbesar yang digunakan, serta ditunjukkan bahwa setiap dua sisi yang berbeda mempunyai bobot yang berbeda. Bagan alur tahap ini diberikan di Gambar 1.3. 2. Menyelesaikan permasalahan 2, yaitu menentukan kekuatan tak reguler titik total (tvs(G)) pada beberapa graf cyclic G yang memuat titik daun dan membuktikan nilai (tvs(G)) tersebut dalam bentuk lemma ataupun teorema. Untuk menentukan kekuatan tak reguler titik total graf, dicari batas bawah dan batas atasnya. Menurut Baˇca dkk. (2007), batas bawah ditentukan dengan memperhatikan derajat titik dan bobot terkecil titik yang dimungkinkan. Label terbesar yang minimum dapat ditentukan dari nilai ceiling bobot titik dibagi derajat titik ditambah satu. Batas atas ditentukan dengan cara mengkonstruksi suatu pelabelan total pada graf sehingga diperoleh label terbesar yang minimum. Dari pelabelan tersebut selanjutnya ditentukan label terbesar yang digunakan, serta ditunjukkan bahwa setiap dua titik yang berbeda mempunyai bobot yang berbeda. Bagan alur tahap ini diberikan di Gambar 1.4.

17 3. Menyelesaikan permasalahan 3, yaitu menentukan kekuatan tak reguler total (ts(G)) pada beberapa graf pohon G dan membuktikan nilai (ts(G)) tersebut dalam bentuk lemma ataupun teorema. Untuk menentukan kekuatan tak reguler total graf, dicari batas bawah dan batas atasnya . Batas bawah ditentukan dengan menggunakan observasi yang dikemukakan oleh Marzuki dkk.(2013), sedangkan batas atas ditentukan dengan cara mengkonstruksi suatu pelabelan total pada graf sehingga diperoleh label terbesar yang minimum. Dari pelabelan tersebut selanjutnya ditentukan label terbesar yang digunakan, serta ditunjukkan bahwa setiap dua sisi dan dua titik yang berbeda mempunyai bobot yang berbeda. Bagan alur tahap ini diberikan di Gambar 1.5. 4. Menyelesaikan permasalahan 4, yaitu mengamati dan menunjukkan sifatsifat karakteristik yang dimungkinkan muncul dari pelabelan total tak reguler yang dikaji. Penentuan Kekuatan Tak Reguler Sisi Total ( Tes) Graf

Penentuan Batas Bawah Tes.

Penentuan Batas Atas Tes.

Bača dkk. (2007).

Dikonstruksi pelabelan-k total tak reguler sisi dengan cara:

Diperhatikan:

1. Simulasi pelabelan-k total untuk

1. Banyak sisi graf.

nilai n tertentu,

2. Bobot terbesar sisi.

2. Penentuan rumus pelabelan-k total

3. Penyusun bobot sisi.

untuk sebarang nilai n.

4. Minimal label terbesar titik/

3. Pembuktian bobot tiap sisi

sisi.

berbeda.

Batas Bawah tes = Batas Atas tes ?

Ya Nilai eksak tes

Tidak Nilai tes dalam interval

Gambar 1.3 Bagan alir penentuan tes(G)

18

Penentuan Kekuatan Tak Reguler Titik Total ( Tvs) Graf

Penentuan Batas Bawah Tvs.

Penentuan Batas Atas Tvs.

Bača dkk. (2007).

Dikonstruksi pelabelan-k total tak reguler titik dengan cara:

Diperhatikan:


1. Derajat titik.

nilai n tertentu.

2. Bobot terkecil titik.

2. Penentuan rumus pelabelan

3. Penyusun bobot no. 2.

untuk sebarang n.

4. Minimal label terbesar titik/

3. Pembuktian bobot tiap titik

sisi.

berbeda

Ya

Batas Bawah tvs = Batas Atas tvs ?

Nilai eksak tvs

Tidak Nilai tvs dalam interval

Gambar 1.4 Bagan alir penentuan tvs(G)

Penentuan Kekuatan Tak Reguler Total ( Ts) Graf

Penentuan Batas Bawah Ts.

Penentuan Batas Atas Ts.

Bača dkk. (2007).

Dikonstruksi pelabelan-k total tak reguler total dengan cara:

Marzuki dkk. (2013).


Dihitung

nilai n tertentu.

1. tes graf.

2. Penentuan rumus pelabelan-k total

2. tvs graf.

untuk sebarang nilai n.

3. maks {tes(G), tvs(G)}.

3. Pembuktian bobot tiap titik dan sisinya berbeda.

Batas Bawah ts = Batas Atas ts ?

Ya Nilai eksak ts

Tidak Nilai ts dalam interval

Gambar 1.5 Bagan alir penentuan ts(G)

19

1.8 Sistematika Penulisan Laporan penelitian disertasi ini terdiri dari lima (5) bab, dengan masingmasing bab terdiri dari beberapa subbab dan subsubbab . Bab I PENDAHULUAN. Bab ini terdiri dari delapan (8) subbab , yaitu: Latar Belakang Masalah, Perumusan Masalah, Batasan Masalah, Tujuan Penelitian, Manfaat Penelitian, Tinjauan Pustaka, Metodologi Penelitian dan Sistematika Penulisan. Ide/ motivasi munculnya topik penelitian disertasi dijelaskan di Latar Belakang Masalah, sehingga selanjutnya muncul Perumusan Masalah, Tujuan Penelitian dan Manfaat Penelitian. Batasan Masalah diberikan untuk membuat materi penelitian lebih terfokus. Tinjauan Pustaka menggambarkan peta perjalanan (roadmap) penelitian sejenis sehingga memberikan inspirasi untuk memperdalam atau mengembangkan penelitian terdahulu ataupun menjawab open problem ataupun konjektur (conjecture) yang diberikan oleh peneliti-peneliti terdahulu. Di subbab ini juga dijelaskan posisi/ perbedaan penelitian ini terhadap penelitian-penelitian sebelumnya. Metode Penelitian menjelaskan langkah-langkah yang peneliti lakukan untuk mencapai Tujuan Penelitian. Bab II KEKUATAN TAK REGULER PADA GRAF. Bab ini terdiri dari tiga (3) subbab , yaitu: Beberapa Pengertian Dasar pada Graf, Kekuatan Tak Reguler Sisi, Titik dan Total pada Graf dan Beberapa Teorema Penentuan Kekuatan Tak Reguler Sisi atau Titik. Definisi-definisi, terminologi dan notasi pada graf umum diberikan di Subbab 1 dengan cara narasi. Hal ini dilakukan supaya ada kesinambungan antar pengertian-pengertian tersebut sesuai dengan lingkup penggunaannya. Misalkan pada waktu menjelaskan pengertian derajat titik, sekaligus dijelaskan pengertian tentang insidensi dan ketetanggaan antar titik. Subbab 2 menjelaskan tentang definisi-definisi, terminologi dan notasi pada pelabelan graf, khususnya pelabelan total, yang menjadi topik pada penelitian ini. Isi pada subbab ini sudah lebih fokus ke topik materi penelitian dibandingkan isi pada Subbab 1. Sama dengan Subbab 1, penyajian pengertian-pengertian tersebut diberikan secara narasi. Subbab 3 menyajikan beberapa teorema dan konjektur yang sudah dihasilkan pada penelitian-penelitian sebelumnya. Hal ini menjadi dasar/ ide untuk langkah-langkah

20 pembuktian pada hasil-hasil yang penulis peroleh. Bab III KEKUATAN TAK REGULER SISI TOTAL. Pada bab ini mulai dibahas hasil-hasil penelitian yang diperoleh. Diberikan hasil-hasil untuk kekuatan tak reguler sisi total (total edge irregularity strength) pada graf cyclic yang terdiri dari tiga (3) subbab yaitu penentuan kekuatan tak reguler sisi total pada graf-graf bersisi daun (pendant edge), graf-graf diperumum (generalized graph) dan grafgraf diperumum bersisi daun. Masing-masing subbab terdiri dari beberapa subsubbab sesuai dengan jenis grafnya. Pada Subbab 1 untuk graf-graf bersisi daun dibahas graf helm, graf gir (Jahangir) bersisi daun dan graf web bersisi daun. Pada Subbab 2 untuk graf-graf diperumum dibahas graf helm, graf Jahangir, graf web dan graf prisma yang semuanya diperumum. Pada Subbab 3 untuk graf-graf diperumum bersisi daun dibahas graf web diperumum bersisi daun dan graf prisma diperumum bersisi daun. Bab IV KEKUATAN TAK REGULER TITIK TOTAL DAN KEKUATAN TAK REGULER TOTAL. Pada bab ini dibahas kekuatan tak reguler titik total (total vertex irregularity strength) pada graf cyclic dan kekuatan tak reguler total (total irregularity strength) pada graf pohon. Untuk kekuatan tak reguler titik total pada graf cyclic dan bersisi daun dibahas pada graf helm diperumum, graf prisma bersisi daun, hasil korona (corona product) graf dengan sejumlah sama titik terisolasi dan hasil korona graf reguler dengan sejumlah sebarang titik terisolasi. Untuk kekuatan tak reguler total, karena topik ini masih relatif baru dan belum banyak hasil yang diperoleh, maka dibahas pada graf-graf pohon sederhana, yaitu graf bintang (star), graf dobel-bintang (double-star) dan graf caterpillar yang dikonstruksi dari graf dobel-bintang dengan 1 cut vertex pada sisi yang insiden dengan dua pusat bintang. Bab V KESIMPULAN DAN MASALAH TERBUKA. Pada bab ini disajikan kesimpulan dari penelitian disertasi dan diberikan beberapa masalah terbuka (open problem) tentang kekuatan tak reguler total.

BAB I PENDAHULUAN. 1.1 Latar Belakang Masalah

Recommend Documents