Bab I Pendahuluan
I.1
Latar belakang masalah
Pelabelan graf pada suatu graf G adalah suatu fungsi satu-satu yang memetakan elemen-elemen graf G ke himpunan bilangan (biasanya himpunan bilangan bulat positif atau bilangan bulat non negatif) yang selanjutnya disebut label. Elemenelemen graf yang dipetakan dapat berupa himpunan titik, himpunan sisi, himpunan permukaan, atau kombinasinya. Jika domain dari fungsi tersebut adalah himpunan titik (atau himpunan sisi), maka pelabelannya disebut pelabelan titik, (atau pelabelan sisi ). Jika domain dari fungsi tersebut adalah himpunan titik dan himpunan sisi, maka pelabelannya disebut pelabelan total.
Pelabelan graf di samping mempunyai properti matematika yang menarik juga mempunyai aplikasi yang cukup luas pada berbagai bidang/permasalahan, seperti x-ray crystallography, teori koding, kriptografi, radar, astronomi, disain sirkuit, dekomposisi graf, dan disain jaringan komunikasi.
Disertasi ini hanya difokuskan pada pelabelan total, khususnya pelabelan total sisiajaib. Pelabelan total sisi-ajaib pada suatu graf dengan p titik dan q sisi adalah suatu fungsi bijektif dari himpunan titik dan himpunan sisi dari graf tersebut ke himpunan bilangan 1, 2, 3, . . . , p + q sedemikian sehingga jumlah label sisi dan label kedua titik yang menempel pada sisi tersebut adalah konstan k untuk setiap sisi pada graf tersebut. Pelabelan total sisi-ajaib ini diperkenalkan oleh Kotzig dan Rosa (1970) dengan nama magic-valuation. Pada tahun 1998, Ringel dan Llado memperkenalkan konsep yang sama dengan nama pelabelan sisi-ajaib. Wallis (2001) menyebutnya sebagai pelabelan total sisi-ajaib, untuk membedakan dengan pelabelan ajaib yang lain. Kemudian Enomoto, Llad´o, Nakamigawa dan Ringel mengkaji pelabelan ini dan memperkenalkan istilah pelabelan total sisi-ajaib super. Pelabelan total sisiajaib super pada suatu graf adalah pelabelan total sisi-ajaib dimana label-label terkecil menjadi label titik. Sejak pelabelan total sisi-ajaib (super) diperkenalkan, banyak hasil yang berkaitan dengan pelabelan ini telah dipublikasikan. Di samping
1
itu, banyak masalah terbuka dan konjektur yang dikemukakan dan belum terpecahkan sampai saat ini. Salah satu konjektur yang yang paling terkenal dalam area ini adalah bahwa setiap graf pohon mempunyai pelabelan total sisi-ajaib (super).
Pelabelan total sisi-ajaib (super) merupakan salah satu pelabelan graf yang memiliki banyak hubungan dengan pelabelan graf yang lain. Apabila suatu graf memiliki pelabelan total sisi-ajaib (super) (dengan sifat tertentu), maka graf tersebut juga memiliki pelabelan antiajaib, pelabelan sequential, pelabelan harmonius, pelabelan cordial, dan pelabelan-α. Hal ini telah dikaji oleh Figueroa-Centeno, Ichishima dan Muntaner-Batle (2001) serta Baca, Lin, dan Simanjuntak (2001).
Sementara banyak peneliti mempelajari sifat-sifat dari pelabelan total sisi-ajaib, peneliti yang lain mencoba mencari penerapannya. Misalnya Wallis (2001) menerapkan pelabelan total sisi-ajaib pada penentuan alamat pada jaringan komunikasi (assigning addresses of communications network ). Baru-baru ini Baskoro et al. (2004, 2005) menerapkannya pada masalah skema pembagian rahasia (secret sharing scheme).
Berkaitan dengan pelabelan total sisi-ajaib, diperkenalkan konsep defisiensi sisi-ajaib yang menyatakan seberapa “dekat” suatu graf ke suatu graf yang total sisi-ajaib. Defisiensi sisi-ajaib dari suatu graf G, µ(G), adalah minimal banyaknya titik terisolasi yang bila digabungkan dengan G dihasilkan suatu graf yang total sisi-ajaib. Konsep ini diperkenalkan oleh Kotzig dan Rosa pada tahun 1970. Konsep defisiensi juga dikembangkan untuk pelabelan total sisi-ajaib super oleh Figueroa-Centeno, Ichishima, dan Muntaner-Batle pada tahun 2002. Defisiensi sisi-ajaib super dari suatu graf G, µs (G), didefinisikan sebagai suatu bilangan bulat tak negatif terkecil n sedemikian sehingga G ∪ nK1 merupakan suatu graf total sisi-ajaib super atau tak berhingga jika bilangan bulat n tersebut tidak ada. Konsep ini, khususnya defisiensi total sisi-ajaib super, relatif baru diperkenalkan sehingga masih banyak terdapat masalah terbuka.
2
I.2
Tujuan penelitian dan rumusan masalah
Penelitian ini bertujuan untuk mengkaji ketotalsisiajaiban graf. Studi ketotalsisiajaiban beberapa kelas graf akan dilakukan, terutama untuk memverifikasi konjektur yang disampaikan oleh Kotzig dan Rosa (1970) maupun oleh Enomoto et al. (1998) mengenai ketotalsisiajaiban dari graf pohon. Di samping itu, penelitian ini juga mengkaji defisiensi total sisi-ajaib (super) dari beberapa kelas graf.
Berkaitan dengan tujuan penelitian ini, masalah yang dikaji dapat dirumuskan sebagai berikut: 1. studi klasifikasi kelas graf yang mempunyai pelabelan total sisi-ajaib (super); khususnya untuk beberapa kelas graf pohon, 2. studi penentuan defisiensi sisi-ajaib (super) dari beberapa kelas graf.
I.3
Hasil-hasil penelitian
Untuk studi klasifikasi beberapa kelas graf yang mempunyai pelabelan total sisi-ajaib (super), kami memperoleh hasil-hasil berikut: setiap graf pohon-seperti-lintasan merupakan graf total sisi-ajaib super, suatu subdivisi dari graf bintang K1,3 merupakan graf total sisi-ajaib super, graf kembang api dengan sifat tertentu merupakan graf total sisi-ajaib super, dan graf rantai kC4 -lintasan mempunyai pelabelan total sisi-ajaib. Kami menunjukkan bahwa graf-graf tersebut mempunyai pelabelan total sisi-ajaib (super) untuk beberapa konstanta ajaib yang mungkin. Kami juga menyajikan metode mendapatkan graf total sisi-ajaib (super) baru dari suatu graf total sisi-ajaib (super) yang sudah diketahui. Berdasarkan metode ini didapatkan beberapa kelas graf pohon baru yang total sisi-ajaib (super).
Untuk studi penentuan defisiensi sisi-ajaib (super) dari suatu graf, kami mengkaji graf rantai, kipas, kipas ganda, roda, bipartit dan multipartit. Hasil-hasil yang kami dapatkan antara lain adalah: µs (kK4 )-lintasan = 1 untuk setiap k ≥ 2, µs (Fn,2 ) = memenuhi
n−2 , 2
untuk n genap, n ≥ 4. Defisiensi sisi-ajaib super dari graf roda Wn 1, untuk n = 3, 4, 6, 7, µs (Wn ) = 2, untuk n = 5, 9, 10, 11, 12, 13. 3
Sedangkan untuk n yang lain, µs (Wn ) ≥ 2. Batas atas defisiensi sisi-ajaib super dari graf mK2,2 , m ≥ 1, dapat dinyatakan sebagai berikut. m, untuk m ganjil, µs (mK2,2 ) ≤ m − 1, untuk m genap. Untuk graf tripartit, batas bawah defisiensi sisi-ajaib supernya adalah 1 µs (Kn1 ,n2 ,n3 ) ≥ b (n2 n3 + (n1 − 2)(n2 + n3 ) − 2n1 + 4)c. 2 dimana n1 ≥ 1 dan n2 , n3 ≥ 2.
I.4
Sistematika penulisan disertasi
Disertasi ini terdiri dari enam bab dengan sistematika sebagai berikut.
Pada Bab I diuraikan tentang latar belakang, tujuan penelitian dan rumusan masalah, serta sistematika penulisan.
Pada Bab II diberikan konsep dasar dari teori graf yang digunakan dalam disertasi ini.
Pada Bab III disajikan hasil-hasil utama penelitian yang menyangkut pelabelan ajaib (super) pada graf subdivisi dari graf K1,3 , graf pohon-seperti-lintasan, graf kembang api, graf lobster dan graf rantai. Beberapa hasil tersebut memberikan contoh pendukung kebenaran konjektur dari Kotzig dan Rosa maupun konjektur Enomoto, Llado, Nakamigawa dan Ringel. Pembahasan dimulai dengan survey pelabelan total sisi-ajaib (super) dan permasalahan terbuka yang ada.
Pada Bab IV disajikan metode pembentukan graf total sisi-ajaib (super) baru dari graf total sisi-ajaib (super) yang sudah diketahui dengan cara menambahkan sisi pendan. Berdasarkan metode tersebut, beberapa kelas graf total sisi-ajaib (super) baru dihasilkan. Beberapa di antaranya memperkuat konjektur bahwa setiap graf pohon total sisi-ajaib (super).
4
Pada Bab V diberikan pembahasan tentang hasi-hasil utama penelitian dalam defisiensi graf. Penyajian dimulai dengan memberikan perkembangan dari kajian tentang defisiensi graf, kemudian dilanjutkan dengan pembahasan hasil-hasil utama penelitian yang menyangkut defisiensi ajaib (super) dari graf rantai, kipas, kipas ganda, roda, bipartit dan multipartit. Kajian meliputi penentuan batas bawah (atau atas) defisiensi ajaib (super) dari graf tersebut, dan penentuan nilai eksak dari defisiensi untuk kasus-kasus tertentu.
Pada Bab VI disajikan kesimpulan, konjektur dan masalah terbuka yang ada.
Hasil utama penelitian disertasi ini dinyatakan dalam bentuk lemma, teorema atau akibat yang diberi tanda .
5
