Jurnal “LOG!K@” , Jilid 6, No. 2, 2016, Hal. 84 - 95 ISSN 1978 – 8568
DEKOMPOSISI - -ANTIAJAIB SUPER PADA GRAF GENERALIZED PETERSEN M. Irvan Septiar Musti, Nur Inayah, dan Irma Fauziah Program Studi Matematika, Fakultas Sains dan Teknologi Universitas Islam Negeri Syarif Hidayatullah Jakarta Email:
[email protected]
Abstract: This research will construct a decomposition -H-antimagic. Decomposition - -antimagic is a bijective function which is mapping set of vertex and edge in graph to positive integer that comply { for two certain positive integers and , and is the amount of subgraph in . In this research, H refers to The aim of this research is to determine decomposition - -super antimagic of generalized Petersen graph for , odd and m = 2. The author is using literature and experiment study as the research method. This research produced 4 theorems that explain decomposition - -super antimagic in generalized Petersen graph with . Keywords: Decomposition, Super Antimagic, , Generalized Petersen Graph. Abstrak: Penelitian ini mengkonstruksi sebuah dekomposisi -Hantiajaib. Dekomposisi - -antiajaib adalah suatu fungsi bijektif yang memetakan himouan titik dan sisi pada graf ke bilangan bulat positif yang memenuhi { untuk dua bilangan bulat positif dan tertentu serta adalah banyaknya subgraf di . H yang dimaksud adalah Tujuan penelitian ini adalah untuk menentukan dekomposisi - -antiajaib super pada graf generalized Petersen untuk , ganjil dan m = 2. Penelitian ini menghasilkan 4 teorema dekomposisi - -antiajaib super pada graf generalized Petersen dengan . Kata kunci: Dekomposisi, Antiajaib Super, , Graf Generalized Petersen.
PENDAHULUAN Teori graf pertama kali muncul karena adanya permasalahan pada jembatan Konigsbreg, sebuah jembatan di kota Kaliningrad, Rusia (dahulu Prusia). Masalah pada jembatan Konigsbreg adalah kemungkinan bisa atau tidaknya melewati tujuh jembatan di kota tersebut dengan tepat satu kali yang menghubungkan empat buah daratan. Pada tahun 1763, Leonhard Euler memecahkan permasalahan tersebut dengan menggunakan titik sebagai representasi dari daratan dan garis yang menghubungkan titik sebagai representasi dari masing-masing jembatan. Representasi titik (vertex) dan sisi (edge) yang diperkenalkan oleh Euler pada permasalahan tersebut dikenal sebagai Graf. Jenis-jenis dari suatu graf semakin banyak dan semakin beragam. Hal ini ditandai dengan adanya graf sederhana, graf berarah dan juga graf reguler. Graf reguler berderajat
Dekomposisi a, d P4 Antiajaib Super pada Graf Generalized Petersen
didefinisikan sebagai graf yang setiap titiknya mempunyai derajat yang sama yaitu . Graf generalized Petersen , ,1≤ ≤ , adalah sebuah graf regular dengan titik dan tiga macam sisi yaitu (sisi dalam), (jeruji), dan (sisi luar) dengan menyatakan banyaknya titik luar yang sama dengan banyaknya titik dalam dan nilai menyatakan lompatan sisi dalam pada graf tersebut. Graf generalized Petersen pertama kali diperkenalkan oleh Watkins [3]. Dekomposisi pada graf merupakan perluasan dari tema pelabelan dalam graf. Suatu pelabelan antiajaib pada graf G yang memuat suatu dekomposisi-H, ditulis dekomposisi -H-antiajaib adalah suatu fungsi bijektif yang memetakan himpunan titik dan sisi pada graf G ke bilangan bulat positif yang memenuhi { untuk dua bilangan bulat positif dan tertentu serta adalah banyaknya subgraf di . Permasalahan dalam paper ini adalah bagaimana mengkonstruksi dekomposisi -antiajaib super pada graf generalized Petersen dengan ganjil, dan . TINJAUAN PUSTAKA Terminologi Graf Graf
didefinisikan sebagai pasangan himpunan ditulis dengan notasi . dalam hal ini merupakan himpunan tidak kosong dari titik- titik dan adalah himpunan sisi yang mungkin kosong dan menghubungkan sepasang titik [4]. Suatu graf dikatakan kosong (null graf) jika [1]. Dari definisi tersebut menyatakan bahwa dalam suatu graf, himpunan titik tidak boleh kosong, akan tetapi himpunan sisi dimungkinkan kosong. Hal ini menandakan bahwa sebuah graf harus memiliki paling sedikit satu buah titik dan dimungkinkan tidak memiliki sisi. Graf yang hanya memiliki sebuah titik disebut graf trivial. Banyaknya unsur pada himpunan titik disebut dengan size dan dinotasikan dengan ǀ ǀ, sedangkan banyaknya unsur pada himpunan sisi disebut dengan order dan dinotasikan dengan ǀ ǀ. Graf yang memiliki size dan order dapat ditulis dengan Graf [2]. Definisi Subgraf Sebuah graf H adalah subgraf dari graf G jika setiap titik pada H adalah titik di G dan setiap sisi pada H adalah sisi di G. Dengan kata lain, dan [2]. Graf Lintasan dan Graf Generalized Petersen Graf lintasan yang dinotasikan adalah suatu graf dengan n titik yaitu sisi . Kemudian, Graf generalized Petersen 1≤ ≤ adalah sebuah graf regular dengan titik macam sisi yaitu
(sisi dalam),
(jeruji), dan
85
dan , dan tiga
(sisi luar) dengan
M. Irvan Septiar Musti dan Nur Inayah
menyatakan banyaknya titik luar yang sama dengan banyaknya titik dalam dan nilai menyatakan lompatan sisi dalam pada graf tersebut [5]. Pelabelan Total
- -Antiajaib
Misalkan G V G , E G dan H V H , E H graf berhingga dan memiliki selimaut-H. Pelabelan total - -antiajaib adalah fungsi bijektif : V G E G 1, 2, , vG eG sedemikian sehingga untuk setiap subgraf H ' yang isomorfik dengan H, himpunan bobot dari H adalah
H '
g v g e
vV H '
eE H '
Bobot setiap selimutnya membentuk barisan aritmatika
a, a d , a 2d ,
, a l 1 d
dengan d menyatakan jarak dan l menyatakan suatu bilangan subgraf isomorfik H, nilai a dan d adalah bilangan bulat positif. Kemudian dikatakan pelabelan - -antiajaib super jika - -antiajaib dikatakan super V G 1, 2, , vG atau dengan kata lain pelabelan jika titik merupakan label terkecil pada graf tersebut [6]. Dekomposisi Suatu graf G dikatakan terdekomposisi menjadi , jika dua buah subgraf dan dengan tidak memiliki sisi yang bersisian dan gabungan semua subgraf adalah G [1]. Suatu keluarga dari subgraf G dikatakan suatu dekomposisi-H dari G, jika Hi isomorfik dengan H, 1 i l , E H i E H j untuk i j dan
l
E H i E G . Dalam hal ini ditulis G H1
H k dan G dikatakan
i 1
terdekomposisi-H atau dengan kata lain G memuat suatu dekomposisi-H. Suatu pelabelan antiajaib pada graf G yang memuat suatu dekomposisi-H, ditulis dekomposisi H-antiajaib adalah suatu fungsi bijektif yang memetakan himpunan titik dan sisi pada graf G ke bilangan bulat positif yang memenuhi { untuk dua bilangan bulat positif dan tertentu serta adalah banyaknya subgraf di . Dalam hal ini dikatakan bobot dari (bobot-H), didefinisikan sebagai Kemudian, dikatakan dekomposisi - -antiajaib super, jika atau dengan kata lain bobot titik merupakan bobot terkecil pada graf tersebut. HASIL DAN PEMBAHASAN Langkah awal yang dilakukan dalam penelitian ini adalah menentukan selimut pada graf generalized Petersen berupa graf lintasan kemudian melabeli titik-titik dan sisi-sisi graf generalized Petersen dengan bilangan bulat positif pada graf tersebut. Setelah itu, peneliti menghitung bobot masing-masing selimut sehingga membentuk deret aritmatika dan
86
Dekomposisi a, d P4 Antiajaib Super pada Graf Generalized Petersen
kemudian mengkonstruksi dekomposisi Petersen.
- -antiajaib super pada graf generalized
Hasil dari penelitian ini berupa empat teorema baru yang ditemukan secara eksperimental yang akan disajikan dengan paparan teorema. Empat teorema yang merupakan hasil dari penelitian ini dikelompokkan sesuai dengan nilai yang didapat dalam penelitian ini. TEOREMA 1 Pada Graf Generalized Petersen - -antiajaib super.
terdapat dekomposisi selimut
Bukti. Setiap titik dan sisi dipetakan ke himpunan bilangan bulat positif oleh fungsi pelabelan di bawah ini,
seperti
= = = =
=
Pola bobot berikut:
masing-masing selimut pada graf generalized Petersen adalah sebagai
=
Berdasarkan pola bobot pelabelan di atas diperoleh graf generalized Petersen adalah sebagai berikut:
87
masing-masing selimut (
pada
M. Irvan Septiar Musti dan Nur Inayah
=
Berdasarkan bobot selimut diatas diperoleh dekomposisi - -antiajaib super pada graf generalized Petersen ( dengan , ganjil dan , dengan dan Ilustrasi dekomposisi - -antiajaib super dengan d = 1 pada graf generalized Petersen GP5,2 dan GP7,2 terdapat pada Gambar 1.
Gambar 1. Ilustrasi dekomposisi d = 1.
- -antiajaib super pada GP5,2 dan GP7,2 dengan
TEOREMA 2 Pada Graf Generalized Petersen
terdapat dekomposisi selimut
- -antiajaib super. Bukti. Setiap titik dan sisi dipetakan ke himpunan bilangan bulat positif oleh fungsi pelabelan di bawah ini,
88
seperti
Dekomposisi a, d P4 Antiajaib Super pada Graf Generalized Petersen
=
=
=
=
=
Pola bobot berikut:
masing-masing selimut pada graf generalized Petersen adalah sebagai
Berdasarkan pola bobot pelabelan di atas diperoleh graf generalized Petersen adalah sebagai berikut:
89
masing-masing selimut (
pada
M. Irvan Septiar Musti dan Nur Inayah
Berdasarkan bobot selimut diatas diperoleh dekomposisi - -antiajaib super pada graf generalized Petersen ( dengan , n ganjil dan , dengan dan Ilustrasi dekomposisi - -antiajaib super dengan d = 2 pada graf generalized Petersen GP5,2 dan GP7,2 terdapat pada Gambar 2. TEOREMA 3 Pada Graf Generalized Petersen (13n+5,3)- -antiajaib super.
terdapat dekomposisi selimut
Bukti. Setiap titik dan sisi dipetakan ke himpunan bilangan bulat positif oleh fungsi pelabelan di bawah ini,
Pola bobot berikut:
seperti
masing-masing selimut pada graf generalized Petersen adalah sebagai
90
Dekomposisi a, d P4 Antiajaib Super pada Graf Generalized Petersen
Gambar 2. Ilustrasi dekomposisi d = 2.
- -antiajaib super pada GP5,2 dan GP7,2 dengan
91
M. Irvan Septiar Musti dan Nur Inayah
Berdasarkan pola bobot pelabelan di atas diperoleh graf generalized Petersen adalah sebagai berikut:
masing-masing selimut (
pada
Berdasarkan bobot selimut diatas diperoleh dekomposisi - -antiajaib super pada graf generalized Petersen ( dengan , n ganjil dan , dengan dan Ilustrasi dekomposisi - -antiajaib super dengan d = 3 pada graf generalized Petersen GP5,2 dan GP7,2 terdapat pada Gambar 3.
Gambar 3. Ilustrasi dekomposisi d = 3.
- -antiajaib super pada GP5,2 dan GP7,2 dengan
92
Dekomposisi a, d P4 Antiajaib Super pada Graf Generalized Petersen
TEOREMA 4 Pada Graf Generalized Petersen
terdapat dekomposisi selimut
- -antiajaib super. Bukti. Setiap titik dan sisi dipetakan ke himpunan bilangan bulat positif oleh fungsi pelabelan di bawah ini,
Pola bobot berikut:
seperti
masing-masing selimut pada graf generalized Petersen adalah sebagai
Berdasarkan pola bobot pelabelan di atas diperoleh graf generalized Petersen adalah sebagai berikut:
93
masing-masing selimut (
pada
M. Irvan Septiar Musti dan Nur Inayah
Berdasarkan bobot selimut di atas diperoleh dekomposisi - -antiajaib super pada graf generalized Petersen ( dengan , n ganjil dan , dengan dan Ilustrasi dekomposisi - -antiajaib super dengan d = 4 pada graf generalized Petersen GP5,2 dan GP7,2 terdapat pada Gambar 4.
Gambar 4. Ilustrasi dekomposisi d = 4.
- -antiajaib super pada GP5,2 dan GP7,2 dengan
Dari keempat teorema yang telah dipaparkan, diperoleh empat jenis nilai yang sesuai dengan nilai d. Tabel 1 menyajikan eksistensi nilai dari keempat teorema di atas.
94
Dekomposisi a, d P4 Antiajaib Super pada Graf Generalized Petersen
KESIMPULAN Berdasarkan hasil dan pembahasan diperoleh kesimpulan bahwa graf generalized Petersen dengan n ganjil, dan memiliki dekomposisi - - antiajaib super dengan nilai dan yang berbeda seperti pada tabel di bawah ini. Pada penelitian ini dihasilkan empat teorema yang disesuaikan dengan nilai dan yang diperoleh dalam penelitian ini. 1 2 3 4
REFERENSI [1] [2] [3] [4] [5] [6]
Harary, F. 1969. Graph Theory. Philipina: Addison- Wesley Publishing Company Inc. Hardsfields, N. dan Rigel, G. 1994. Pearls in Graph Theory. London: Accademic Press Limeted M.E. Watkins. 1969. A Theorem on Tait colorings with an application to the generalized Petersen graph, J. Combin. Theory 6, 152-164. Munir, Rinaldi. 2010, Matematika Diskrit, Edisi Ketiga. Bandung: Penerbit Informatika. Sungeng, K.A. 2005. Magic and Antimagic Labeling of Graph. Ph.D Thesis. School of Information Technology and Mathematical Science University of Ballarat. Nur Inayah, A.N.M. Salman, R. Simanjuntak. 2009. On - -antimagic Coverings of Graph. The Combinatorial Mathematics and Combinatorial Computing 71, 273281.
95
