Volume 1 No. 1 Edisi April 2015
ISSN : 2338-0896
Pelabelan Super Graceful pada Graf Caterpillar Nisa Nur Arafah1, a) , Rismawati Ramdani2, b), dan Arief Fatchul Huda3, c) 1, 2, 3
Juruan Matematika, Fakultas Sains dan Teknologi, UIN Sunan Gunung Djati Jl. A H Nasution No. 105 Bandung a)
[email protected] [email protected] b)
[email protected]
b)
Abstrak Misalkan πΊ merupakan suatugraf dengan banyaknya titik πdan banyaknya sisi π. Pelabelan super graceful adalah pemetaan fungsi satu-satu pada π βΆ π(πΊ) βͺ πΈ(πΊ) β {1,2, β¦ , π + π}sehingga π(π’π£) = |π(π’) β π(π£)| berbeda untuk setiap sisi π’π£ β πΈ(πΊ). Sebuah graf πΊ disebut graf super graceful jika graf tersebut dapat dilabeli menurut definisi pelabelan super graceful. Graf caterpillar adalah graf yang jika semua titik pendannya dihilangkan akan menghasilkan lintasan. Pada makalah ini akan ditunjukkan bahwa graf caterpillar πΆππ dengan kepala dan ekor yang mempunyai n badan dan 2 kaki pada tiap badan, graf caterpillar πΆππ tanpa kepala dan ekor yang mempunyai n badan dan 2 kaki pada tiap badan,dan graf caterpillar πΆππ,π tanpa kepala dan ekor yang mempunyai π badan dan π kaki pada tiap badan merupakan graf super graceful. Kata kunci : Pelabelan Super Graceful, Graf Caterpillar. Pendahuluan Pelabelan merupakan pemetaan yang memetakan himpunan titik atau himpunan sisi ke suatu bilangan yang disebut label. Berdasarkan unsur yang dilabeli, pelabelan dibagi menjadi tiga jenis, yaitu pelabelan titik, pelabelan sisi, dan pelabelan total. Pelabelan titik adalah pelabelan dengan domain himpunan titik, pelabelan sisi adalah pelabelan dengan domain himpunan sisi, dan pelabelan total adalah pelabelan dengan domain gabungan antara himpunan titik dan himpunan sisi.Terdapat cukup banyak jenis pelabelan graf yang telah dikaji, antara lain pelabelan graceful, pelabelan harmoni, pelabelan ajaib, pelabelan anti ajaib, pelabelan prima, dan pelabelan k-graceful.pelabelan-pelabelan tersebut telah dipelajari lebih dari 1000 makalah. Pelabelan graf juga telah diaplikasikan pada beberapa bidang lainnya, diantaranya teori koding, kristalografisinar X, radar, astronomi, desain sirkuit, sistem jaringan komunikasi, dan penyimpanan data komputer. Salah satu jenispelabelan graf yang banyakdikaji yaitu pelabelan graceful.Pelabelangracefulpertama kali diperkenalkanolehRosa [1] pada tahun 1967 Pelabelan inikemudiandikembangkan dan menghasilkan jenis pelabelan baru, yaitu pelabelan supergraceful. Penelitianmengenaipelabelansuper graceful diantaradilakukanolehM.A. Perumal dkk [7] (2011), padamakalahnya yang berjudul super graceful labeling for some special graphs. Jenis graf yang telah dikaji diantaranya, graf ππβ1 (1,2, β¦ , π), graf pohon kelapa, graf bipartit lengkap πΎπ,π , graf superstarππ,π , dan graf π΅(π, π, π). Misalkan πΊ adalah suatu graf dengan banyaknya titik π dan banyaknya sisi π . Pelabelan super graceful pada πΊ adalah fungsi satu-satu pada π βΆ π(πΊ) βͺ πΈ(πΊ) β {1,2, β¦ , π + π} sehingga π(π’π£) = |π(π’) β π(π£)| berbeda untuk setiap sisi π’π£ β πΈ(πΊ). Sebuah graf πΊ disebut graf supergraceful jika graf tersebut dapat dilabeli menurut definisi pelabelan supergraceful.[7]
1
Volume 1 No. 1 Edisi April 2015
ISSN : 2338-0896
Pada makalah ini, akan dikonstruksi suatu pelabelan super graceful pada beberapa jenis graf caterpillar, yaitu graf graf caterpillar πΆππ tanpa kepala dan ekor yang mempunyai n badan dan 2 kaki pada tiap badan, graf caterpillar πΆππ dengan kepala dan ekor yang mempunyai n badan dan 2 kaki pada tiap badan,dan graf caterpillar πΆππ,π tanpa kepala dan ekor yang mempunyai π badan dan π kaki pada tiap badan merupakan graf super graceful.[2] Teori Dasar Definisi 2.1 Suatu Graf πΊadalah pasangan dua himpunanπ(πΊ)danπΈ(πΊ), dinotasikan dengaπΊ = (π(πΊ), πΈ(πΊ)),dimanaπ(πΊ)adalah himpunan yang tak kosong dari titik-titikdanπΈ(πΊ)adalah himpunan sisiyang menghubungkan dua titik di πΊ. Jikaπmenghubungkan titikπ’dengan titik π£, maka πdapat ditulis sebagai π = (π’π£).[6]Banyaknya titik pada graf πΊ disebut orde dari graf πΊ , sedangkan banyaknya sisi pada πΊdisebut ukuran dari πΊ.Bila titik π’ dan π£ terhubung oleh suatu sisi π di πΊ(π(πΊ), πΈ(πΊ)), maka titik π’ dan π£ dikatakan bertetangga di πΊ(π(πΊ), πΈ(πΊ)), dan jika ada sisi π = π’π£, maka sisiπdisebut terkait pada titikπ£.Titik π’ dan π£ disebut titik ujungdari π.[6] Banyaknya sisi yang menempel pada suatu titik π£ β π(πΊ) disebut sebagai derajat titik π£, dinotasikan dengan π(π£). Derajat terkecil dari suatu graf πΊ dinotasikan dengan πΏ(πΊ), sedangkan derajat terbesar dari graf πΊ dinotasikan dengan β(πΊ).[5] Suatu graf disebut sederhana jika tidak memuat loop dan sisi ganda.Titikpendanadalahtitikberberadat 1. [4] Jalan (walk) adalah suatuderetπ = π£0 π1 π£1 π2 π£2 β― π£πβ1 ππ π£π yang berselang seling antara titik dan sisi sedemikian sehingga ππ = π£πβ1 π£π . Lintasanadalahsuatujalandimanaπ£π β π£π untuk setiap 0 β€ π β€ π[4]. Graf caterpillar adalah graf yang jika semua titik ujungnya dihilangkan akan menghasilkan lintasan[2]. Misalkan πΊ terhubung,πΊ memuat tepat satu titik ujung yang terhubung langsung dengan badan bagian depan dan belakang maka masing-masing bagian disebut dengan kepala dan ekor, sedangkan yang disebut badan yaitu jika berderajat lebih dari 2, dan disebut kaki jika memuat tepat satu titik ujung yang terkait langsung dengan badan bagian kanan dan kiri.[2] Sebagai ilustrasi, berikut ini diberikan contoh graf caterpillar dengan kepala dan ekor dan contoh graf caterpillar tanpa kepala dan ekor. Kaki
Ekor
Kepala Badan
Gambar 1 Graf Caterpillar dengan kepala dan ekor yang mempunyai 3 badan dan 6 kaki
2
Volume 1 No. 1 Edisi April 2015
ISSN : 2338-0896
Gambar 2 Graf Caterpillar tanpa kepala dan ekor yang mempunyai 3 badan dan 6 kaki Hasil dan Pembahasan Pada bagian ini akan dibuktikan bahwa graf caterpillar πΆππ dengan kepala dan ekor yang mempunyai n badan dan 2 kaki pada tiap badan, graf caterpillar πΆππ tanpa kepala dan ekor yang mempunyai n badan dan 2 kaki pada tiap badan,dan graf caterpillar πΆππ,π tanpa kepala dan ekor yang mempunyai π badan dan π kaki pada tiap badan merupakan graf super graceful. 1. Pelabelan Super Graceful pada Graf Caterpillar πΆππ dengan Kepala dan Ekor Teorema 3.1 Graf caterpillar πΆππ , untuk π β₯ 2, dengan kepala dan ekor yang mempunyai π badan dan 2π kaki merupakan graf super graceful. Bukti. Misalkan π = π1 βͺ π2 βͺ π3 adalah himpunan titik pada graf caterpillar dimana π1 = {π£0 , π£1 , π£2 , β¦ , π£π , π£π+1 }, π2 = {π£1β² , π£2β² , π£3β² , β¦ , π£πβ² } dan π3 = {π£1" , π£2" , π£3" , β¦ , π£π" }, Titik π£0 adalah kepala dan titik π£π+1 adalah ekor. Definisikan suatupelabelan π βΆ π(πΆππ ) βͺ πΈ(πΆππ ) β {1,2, β¦ ,3(2π + 1)}pada graf caterpillar πΆππ dengan kepala dan ekor dengan aturan yaitu sebagai berikut: 3(2π β π + 2) untuk 1 β€ π β€ π + 1 danπ β‘ 1(πππ 2) π(π£π ) = { π+1 untuk 0 β€ π β€ π + 1 danπ β‘ 0(πππ 2) Untuk 0 β€ π β€ π + 1 danπ β‘ 0(πππ 2) bukan i+1 tapi 3i+1 3π untuk 1 β€ π β€ π danπ β‘ 1(πππ 2) π(π£πβ² ) = { 3(2π β π) + 5 untuk 1 β€ π β€ πdanπ β‘ 0(πππ 2) 3(π + 1) β 1 untuk 1 β€ π β€ πdanπ β‘ 1(πππ 2) π(π£π" ) = { 3(2π β π) + 7 untuk 1 β€ π β€ πdan π β‘ 0(πππ 2) Daripelabelan di atas, dapat dilihat bahwa label pada setiap titik berbeda. 1. Untuk π ganjil a. Untuk π = 1,3,5, β¦ , π + 1, label titik-titik π£π berturut-turut adalah 3(2π + 1), 3(2π β 1), 3(2π β 3), β¦ ,3(π + 2), sedangkan untuk π = 2,4,6 β¦ , π , label titik-titikπ£π berturut-turut adalah {1,7,13, β¦ ,3π + 4}. Bukan 2,4,6, . . . π, tapi dimulai dari π = 0,2,4, β¦ , π + 1. Saya misalkan: Diketahui π = 3 atau π ganjil Pelabelan pada graf ini, untuk π = 3 maka pelabelan terbesar yaitu 3(2π + 1) = 21 Untuk mencari label himpunan π1 = {π£0 , π£1 , π£2 , β¦ , π£π , π£π+1 } atau π(π£π ), disini ada dua rumus untuk i genap dan i ganjil. - Untuk π ganjil dengan rumus: 3(2π β π + 2), untuk setiap π = 1,3 atau π£1 dan π£3 , maka himpunan label diperoleh yaitu: {21,15} atau dengan hasil pembuktian himpunan label yaitu, {3(2π + 1), 3(2π β 1), 3(2π β 3), β¦ , π(π + π)}, 3
Volume 1 No. 1 Edisi April 2015
-
ISSN : 2338-0896
Dan jika π genap maka himpunan labelnya yaitu, {3(2π + 1), 3(2π β 1), 3(2π β 3), β¦ , π(π + π)}. Untuk π genap dengan rumus: 3π + 1 bukan π + 1, untuk setiap π = 0,2,4 atau π£0 ,π£2 , dan π£4 , maka himpunan label diperoleh yaitu: {1,7,13} atau dengan hasil pembuktian himpunan label yaitu, {1,7,13, β¦ , ππ + π}, Dan jika π genap maka himpunan labelnya yaitu, {1,7,13, β¦ , ππ + π}. Sehingga dipastikan himpunan label untuk π ganjil dan π genap akan berbeda !
Untuk π = 1,3,5, β¦ , π, label titik-titik π£πβ² berturut-turut adalah {3,9,15, β¦ ,3π}, sedangkan untuk π = 2,4,6, β¦ , π , label titik-titik π£πβ² berturut-turut adalah {3(2π β 2) + 5,3(2π β 4) + 5,3(2π β 6) + 5, β¦ ,3π + 8}. c. Untuk π = 1,3,5, β¦ , π, label titik-titik π£π" berturut-turut adalah {5,11,17, β¦ ,3π + 2} , sedangkan untuk π = 2,4,6, β¦ , π , label titik-titik π£πβ berturut-turut adalah {6π + 1,6π β 5,6π β 11, β¦ ,3π + 10}. 2. Untuk n genap a. Untuk π = 1,3,5, β¦ , π + 1, labeltitik-titik π£π berturut-turut adalah {3(2π + 1), 3(2π β 1), 3(2π β 3), β¦ ,3(π + 1)} sedangkan untuk π = 0,2,4,6 β¦ , π, label titik-titikπ£π berturutturut adalah {1,7,13, β¦ ,3π + 1}. b. Untuk π = 1,3,5, β¦ , π, label titik-titik π£πβ² berturut-turut adalah {3,9,15, β¦ ,3π β 1} , sedangkan untuk π = 2,4,6, β¦ , π , label titik-titik π£πβ² berturut-turut adalah {3(2π β 2) + 5,3(2π β 4) + 5,3(2π β 6) + 5, β¦ ,3π + 5}. c. Untuk π = 1,3,5, β¦ , π, label titik-titik π£π" berturut-turut adalah {5,11,17, β¦ ,3π β 1} , sedangkan untuk π = 2,4,6, β¦ , π , label titik-titik π£πβ² berturut-turut adalah {6π + 1,6π β 5,6π β 11, β¦ ,3π + 7} b.
Setelah pelabelan titik-titiknya diperoleh maka sisi-sisinya akan mendapat label menurut aturan pelabelan super graceful sebagai berikut. π(π£π π£π+1 ) = |π(π£π ) β π(π£π+1 )| = 2(3π β 3π + 1),untuk 0 β€ π β€ π |π(π£π ) β π(π£β²π )| = 6(π β π + 1) untuk 1 β€ π β€ πdanπ β‘ 1(πππ 2) π(π£π π£πβ² ) = { |π(π£π ) β π(π£ β² π )| = 2(3π β 3π + 2) untuk 1 β€ π β€ πdanπ β‘ 0(πππ 2) |π(π£π ) β π(π£"π )| = 2(3π β 3π + 2) untuk 1 β€ π β€ πdanπ β‘ 1(πππ 2) π(π£π π£π" ) = { |π(π£π ) β π(π£"π )| = 6(π β π + 1) untuk 1 β€ π β€ πdanπ β‘ 0(πππ 2) Dari pelabelan di atas, dapat dilihat bahwa label pada setiap sisi berbeda. 1. Untuk π = 0,1,2, β¦ , π , label titik-titik π£π π£π+1 berturut-turut adalah {2(3π + 1), 2(3π β 2), 2(3π β 5), 2(3π β 8), β¦ ,2}. Untuk label titik-titik π£π π£π+1 tidak berlaku untuk π ganjil dan π genap, karena dengan satu himpunan dapat memperoleh label untuk π ganjil dan π ganjil. 2. Untuk n ganjil a. Untuk π = 1,3,5, β¦ , π + 1, labeltitik-titik π£π π£πβ² berturut-turut adalah {6π, 6(π β 2), 6(π β 4), β¦ ,6} sedangkanuntuk π = 2,4,6, β¦ , π , labeltitik-titik π£π π£πβ² berturut-turutadalah {2(3π β 4), 2(3π β 10), 2(3π β 16), β¦ ,10}. b. Untuk π = 1,3,5, β¦ , π, label titik-titik π£π π£π" berturut-turut adalah {2(3π β 1), 2(3π β 7), 2(3π β 13), β¦ ,4}, sedangkan untuk π = 2,4,6, β¦ , π, label titik-titik π£π π£π" berturut-turut adalah {6(π β 1), 6(π β 3), 6(π β 5), β¦ ,12}.
4
Volume 1 No. 1 Edisi April 2015
ISSN : 2338-0896
3. Untuk n genap a. Untukπ = 1,3,5, β¦ , π, label titik-titikπ£π berturut-turut adalah {6π, 6(π β 2), 6(π β 4), β¦ ,12} sedangkan untuk π = 2,4,6 β¦ , π, label titik-titikπ£π berturut-turut adalah {2(3π β 4), 2(3π β 10), 2(3π β 16), β¦ ,4}. b. Untuk π = 1,3,5, β¦ , π, label titik-titik π£π π£π" berturut-turut adalah {2(3π β 1), 2(3π β 7), 2(3π β 13), β¦ ,10}, sedangkan untuk π = 2,4,6, β¦ , π, label titik-titik π£π π£π" berturut-turut adalah {6(π β 1), 6(π β 3), 6(π β 5), β¦ ,6}. Dapat dilihat bahwa semua pelabelan pada himpunan titik dan pelabelan pada himpunan sisi berbeda dengan gabungan dari kedua himpunan titik dan sisi adalah {1,2,3, β¦ ,3(2π + 1)}.Oleh karena itu, πadalah pelabelan super graceful. Dengan demikian, graf caterpillarπΆππ dengan kepala dan ekor dengan π badan dan 2 kaki ditiap badan untuk π β₯ 2 adalah graf super graceful. Sebagai ilustrasi, Gambar 3 di bawahini menunjukkan pelabelan super graceful pada graf caterpillarπΆπ6 dengan kepala dan ekor yang mempunyai 6 badan dan 12 kaki . 3
35
36 32
38 1
39
33
5
30 37
14
22 11
18 31
4 2
8 19
27
13
23
12
16 20
26 7
34
24
28
15
29
9
10 17
21 6
25
Gambar 3 Pelabelan super graceful pada graf caterpillar πΆππ dengan kepala dan ekor yang mempunyai 6 badan dan 12 kaki. 2. Pelabelan Super Graceful pada Graf Caterpillar πΆππ Tanpa Kepala dan Ekor dengan nBadan dan 2Kaki pada Tiap Badan. Teorema 3.2 Graf caterpillarπΆππ tanpa kepala dan ekor yang mempunyai π badan dan 2πkaki, untuk π β₯ 2,merupakan graf super graceful. Bukti Misalkan π = π1 βͺ π2 βͺ π3 adalah himpunan titik pada graf caterpillar dimana, π1 = {π£1 , π£2 , π£3 , β¦ , π£π }, π2 = {π£1β² , π£2β² , π£3β² , β¦ , π£πβ² } dan π3 = {π£1" , π£2" , π£3" , β¦ , π£π" }. Definisikan pelabelan π: π(πΆππ ) βͺ πΈ(πΆππ ) β {1,2, β¦ ,6π β 1}pada graf caterpillar πΆππ tanpa kepala dan ekor dengan aturan yaitu sebagai berikut: 3(2π β π + 2) untuk 1 β€ π β€ πdanπ β‘ 1(πππ 2) π(π£π ) = { 3π β 1 untuk 1 β€ π β€ πdanπ β‘ 0(πππ 2) 3π β 2 untuk 1 β€ π β€ πdanπ β‘ 1(πππ 2) π(π£πβ² ) = { 3(2π β π) + 1 untuk 1 β€ π β€ πdanπ β‘ 0(πππ 2) 3π untuk 1 β€ π β€ πdanπ β‘ 1(πππ 2) π(π£π" ) = { 3(2π β π + 1) untuk 1 β€ π β€ πdanπ β‘ 0(πππ 2) Dari pelabelan di atas, dapat dilihat bahwa label pada setiap titik berbeda. 1. Untuk π ganjil a. Untuk π = 1,3,5, β¦ , π, labeltitik-titik π£π berturut-turut adalah {6π β 1,6π β 7,6π β 13, β¦ ,3π + 2} sedangkan untuk π = 2,4,6 β¦ , π , label titik-titik π£π berturut-turut adalah {5,11,17, β¦ ,3π β 4}.
5
Volume 1 No. 1 Edisi April 2015
ISSN : 2338-0896
b. Untuk π = 1,3,5, β¦ , π, label titik-titik π£πβ² berturut-turut adalah {1,7,13, β¦ ,3π β 5} , sedangkan untuk π = 2,4,6, β¦ , π , label titik-titik π£πβ² berturut-turut adalah {6π β 5,6π β 136π β 17, , β¦ ,3π + 4}. c. Untuk π = 1,3,5, β¦ , π, label titik-titik π£π" berturut-turut adalah {3,9,15, β¦ ,3π}, sedangkan untuk π = 2,4,6, β¦ , π , label titik-titik π£πβ² berturut-turut adalah {3(2π β 1), 3(2π β 3), 3(2π β 5), β¦ ,3(π + 2)}. 2. Untuk n genap a. Untuk π = 1,3,5, β¦ , π, labeltitik-titik π£π berturut-turut adalah {6π β 1,6π β 7,6π β 13, β¦ ,3π β 1} sedangkanuntuk π = 2,4,6 β¦ , π , labeltitik-titik π£π berturut-turut adalah {5,11,17, β¦ ,3π β 1}. b. Untuk π = 1,3,5, β¦ , π, label titik-titik π£πβ² berturut-turut adalah {1,7,13, β¦ ,3π β 2} , sedangkan untuk π = 2,4,6, β¦ , π , label titik-titik π£πβ² berturut-turut adalah {6π β 5,6π β 136π β 17, , β¦ ,3π + 1}. c. Untuk π = 1,3,5, β¦ , π, label titik-titik π£π" berturut-turut adalah {3,9,15, β¦ ,3π β 1} , sedangkan untuk π = 2,4,6, β¦ , π , label titik-titik π£πβ² berturut-turut adalah {3(2π β 1), 3(2π β 3), 3(2π β 5), β¦ ,3(π + 1)}. Setelah pelabelan titik-titiknya diperoleh maka sisi-sisinya akan mendapat label menurut aturanpelabelansuper graceful sebagai berikut. π(π£π π£π+1 ) = |π(π£π ) β π(π£π+1 )| = 6(π β π), untuk 1 β€ π β€ π β 1 |π(π£π ) β π(π£πβ² )| = 2(3π β 3π + 2), untuk 1 β€ π β€ π, π β‘ 1(πππ 2) π(π£π π£πβ² ) = { |π(π£π ) β π(π£πβ² )| = 2(3π β 3π + 1), untuk 1 β€ π β€ π, π β‘ 0(πππ 2) |π(π£π ) β π(π£π" )| = 2(3π β 3π + 1), untuk 1 β€ π β€ π, π β‘ 1(πππ 2) π(π£π π£π" ) = { |π(π£π ) β π(π£π" )| = 2(3π β 3π + 2), untuk 1 β€ π β€ π, π β‘ 0(πππ 2) pelabelan di atas, dapat dilihat bahwa labelpadasetiaptitikberbeda. 1. Untuk π = 1,2,3, β¦ , π β 1, labeltitik-titik π£π π£π+1 berturut-turut adalah {6π β 6,6π β 12,6π β 18, β¦ ,6}. 2. Untuk π ganjil a. Untuk π = 1,3,5, β¦ , π, label titik-titik π£π π£πβ² berturut-turut adalah {2(3π β 1), 2(3π β 7), 2(3π β 13), β¦ ,4}, sedangkan untuk π = 2,4,6, β¦ , π, label titik-titik π£π π£πβ² berturut-turut adalah {2(3π β 5), 2(3π β 11), 2(3π β 17), β¦ ,8}. b. Untuk π = 1,3,5, β¦ , π, label titik-titik π£π π£π" berturut-turut adalah {2(3π β 2), 2(3π β 8), 2(3π β 14), β¦ ,2}, sedangkan untuk π = 2,4,6, β¦ , π, label titik-titik π£π π£π" berturut-turut adalah {2(3π β 4), 2(3π β 10), 2(3π β 16), β¦ ,4}. 3. Untukπ genap a. Untuk π = 1,3,5, β¦ , π, label titik-titik π£π π£πβ² berturut-turut adalah {1,7,13, β¦ ,3π β 2} , sedangkan untuk π = 2,4,6, β¦ , π , label titik-titik π£π π£πβ² berturut-turut adalah {2(3π β 5), 2(3π β 11), 2(3π β 17), β¦ ,2}. b. Untuk π = 1,3,5, β¦ , π, label titik-titik π£π π£π" berturut-turut adalah {2(3π β 2), 2(3π β 8), 2(3π β 14), β¦ ,4}, sedangkan untuk π = 2,4,6, β¦ , π, label titik-titik π£π π£π" berturut-turut adalah {2(3π β 4), 2(3π β 10), 2(3π β 16), β¦ ,10}. Dapat dilihat bahwa semua pelabelan pada himpunan titik dan pelabelan pada himpunan sisi berbeda dengan gabungan dari kedua himpunan titik dan sisi adalah {1,2,3, β¦ ,6π β 1}. Oleh karena itu, π adalah pelabelan super graceful. Dengan demikian, graf caterpillarπΆππ dengan kepala dan ekor tanpaπ badan dan 2 kaki ditiap badan untuk π β₯ 2 adalah graf super graceful. 6
Volume 1 No. 1 Edisi April 2015
ISSN : 2338-0896
Sebagai ilustrasi, Gambar 2 menunjukkan pelabelan super graceful pada graf caterpillarπΆπ6 tanpa kepala dan ekor yang mempunyai 6 badan dan 12 kaki merupakan graf super graceful. 1
26
34 30 35
3
28 33
20 9
17
23 16
27
2 6
12 11
19
10
14 18
29
13
25
22 24
5
32
7
31
8 15
4 21
Gambar 4 Pelabelan superTitik graceful caterpillar Gambar. Penotasian Grafpada Ulat graf utnuk π = 6 πΆπ6 tanpa kepala dan ekor yang mempunyai 6 badan dan 12 kaki. 3. Pelabelan Super Graceful pada Graf Caterpillar πΆππ,π tanpa kepala dan ekor Graf caterpillar πΆππ,π tanpa kepala dan ekor memiliki himpunan titik 1 1 2 2 π π 1 2 π {π£1 , π£2 , β¦ , π£π ; π£1 , π£2 , β¦ , π£π ; π£1 , π£2 , β¦ , π£π ; β¦ ; π£1 , π£2 , β¦ , π£π ; }. Berikut ini diberikan teorema pelabelan super graceful pada graf caterpillar πΆππ,π tanpa kepala dan ekor yang mempunyai π badan dan ππ kaki pada tiap badan. Teorema 3.3Setiap graf caterpillarπΆππ,π tanpa kepala dan ekor yang mempunyai π badan dan ππ kaki pada tiap badan merupakan graf super graceful. Bukti Akan dibuktikan graf caterpillar πΆππ,π tanpa kepala dan ekor yang mempunyai π badan (dimana π diambil hanya dari 3 sampai 5) dan ππ kaki, dimana π adalah badan dan π adalah kaki, yang mempunyai ππ + π titik dan ππ + π β 1 sisi. Definisikan pelabelan untuk titik-titik : π(πΆππ,π ) βͺ πΈ(πΆππ,π ) β {1,2,3, β¦ , 2(ππ + π) β 1} pada graf caterpillar πΆππ,π tanpa kepala dan ekor dengan aturan yaitu sebagai berikut: a. Untuk π = 3, yaitu graf caterpillar πΆππ,3 tanpa kepala dan ekor yang mempunyai 3 badan dan 3π kaki dengan aturan sebagai berikut: 2(ππ + π) β π, π = 1 π=2 π(π£π ) = { 2π + π β 1, 2(2π + π) β π, π = 3 2π β π, 1 β€ π β€ π, π=1 π π=2 π(π£π ) = {2(2π + π) + π + 1,1 β€ π β€ π, 2(π + π β 1) + π, 1 β€ π β€ π, π=3 Dari pelabelan di atas, dapat dilihat bahwa label pada setiap titik berbeda. 1. Untukπ = 1, label titik-titikπ£π berturut-turut adalah {2(ππ + π) β 1}, untuk π = 2, label titiktitikπ£π berturut-turut adalah {2π + 1}, sedangkan untuk π = 3, label titik-titikπ£π berturut-turut adalah {2(2π + π) β 3} π 2. Untuk π = 1,2,3, β¦ , π dan π = 1 label titik-titik π£π berturut-turut adalah {1,3,5, β¦ ,2π β 1} , untuk π = 1,2,3, β¦ , π dan π = 2, label titik-titik π£πβ² berturut-turut adalah {4π + 5,4π + 7,4π + 9, β¦ ,6π + 3} , sedangkan π = 1,2,3, β¦ , π dan π = 3 , label titik-titik π£πβ² berturut-turut adalah {2π + 3,2π + 5,2π + 7, β¦ ,4π + 1}.
Setelah pelabelan titik-titiknya diperoleh maka sisi-sisinya akan mendapat label menurut aturan pelabelan super graceful sebagai berikut. 7
Volume 1 No. 1 Edisi April 2015
ISSN : 2338-0896
|π(π£π ) β π(π£π+1 )| = 2(ππ + π β π) β π β 1, untuk π = 1 π(π£π π£π+1 ) = { |π(π£π ) β π(π£π+1 )| = 2(π + π β 1) β π, untuk π = 2 π
π
π(π£π π£π ) = |π(π£π ) β π(π£π )| = 2(ππ + π β π) + π β 1, untuk 1 β€ π β€ π, π = 1 π
π
π
π
π(π£π+1 π£π ) = |π(π£π+1 ) β π(π£π )| = 2(π + π) + π, untuk 1 β€ π β€ π, π = 2 π(π£π+2 π£π ) = |π(π£π+2 ) β π(π£π )| = 2(π + π β π) β π β 1, untuk 1 β€ π β€ π, π = 3 Dari pelabelan di atas, dapat dilihat bahwa label pada setiap sisi berbeda. 1. Untuk π = 1, label titik-titik π£π π£π+1 berturut-turut adalah {2(ππ + π β π β 1)} , untuk π = 2, sedangkan label titik-titikπ£π π£π+1 berturut-turut adalah {2(π + π β 2)}. π 2. Untuk π = 1,2,3, β¦ , π dan π = 1 label titik-titik π£π π£π berturut-turut adalah {2(ππ + π β 1), 2(ππ + π β 2), 2(ππ + π β 3), β¦ ,2(ππ + π β π)}, untuk π = 1,2,3, β¦ , π dan π = 2, label π
titik-titik π£π+1 π£π
b.
berturut-turut adalah {2(π + 2), 2(π + 3), 2(π + 4), β¦ ,2(2π + 1)} , π
sedangkan π = 1,2,3, β¦ , π dan π = 3, label titik-titik π£π+2 π£π berturut-turut adalah {2(π + π β 3), 2(π + π β 4), 2(π + π β 5), β¦ ,2π β 4}. Untuk π = 4, yaitu graf caterpillarπΆππ,4 tanpa kepala dan ekor yang mempunyai 4 badan dan 4π kaki dengan aturan sebagai berikut: 2(ππ + π) β π, π=1 2(π β π) + π + 1, π=2 π(π£π ) = { 2ππ + π + 1, π=3 4π + π β 1, π=4 2π β π, 1 β€ π β€ π, π = 1 2ππ + π + 1 β π(π β 1), 1 β€ π β€ π, π = 2 π π(π£π ) = { 2(π + π β 1) + π, 1 β€ π β€ π, π = 3 ππ + 2π + π β 1, 1 β€ π β€ π, π = 4 Dari pelabelan di atas, dapat dilihat bahwa label pada setiap titik berbeda. 1. Untukπ = 1, label titik-titikπ£π berturut-turut adalah {2(ππ + π) β 1}, untuk π = 2, label titiktitik π£π berturut-turut adalah {2π + π β 3}, untuk π = 3, label titik-titik π£π berturut-turut adalah {4π + π + 1}, sedangkan untuk π = 4, label titik-titikπ£π berturut-turut adalah {4π + 3} π 2. Untuk π = 1,2,3, β¦ , π dan π = 1 label titik-titik π£π berturut-turut adalah {1,3,5, β¦ ,2π β 1} , untuk π = 1,2,3, β¦ , π dan π = 2, label titik-titik π£πβ² berturut-turut adalah {2ππ + π + 1,2ππ + π β 1,2ππ + π β 3, β¦ ,2(ππ β π) + π + 3}, untuk π = 1,2,3, β¦ , π dan π = 3, label titik-titik π£πβ² berturut-turut adalah {2π + 3,2π + 5,2π + 7, β¦ ,4π + 1} , sedangkan untuk π = 1,2,3, β¦ , π dan π = 4, label titik-titik π£πβ² berturut-turut adalah {ππ + 5, π + 7, π + 9, β¦ , π(π + 2) + 3}.
Setelah pelabelan titik-titiknya diperoleh maka sisi-sisinya akan mendapat label menurut aturan pelabelan super graceful sebagai berikut. |π(π£π ) β π(π£π+1 )| = 2(ππ β π) + π β π + 3, untuk π = 1 untuk π = 2 π(π£π π£π+1 ) = { |π(π£π ) β π(π£π+1 )| = 2(2π + π), |π(π£π ) β π(π£π+1 )| = 2(ππ β 2π β 1) + π, untuk π = 3 π
π
π(π£π π£π ) = |π(π£π ) β π(π£π )| = 2(ππ + π β π) + π β 1, untuk 1 β€ π β€ π, π = 1 π
π
π
π
π
π
π(π£π+1 π£π ) = |π(π£π+1 ) β π(π£π )| = 2(ππ β π + 2) β π(π β 1), untuk 1 β€ π β€ π, π = 2 π(π£π+2 π£π ) = |π(π£π+2 ) β π(π£π )| = 2(2π β π) + π β π + 3, untuk 1 β€ π β€ π, π = 3 π(π£π+3 π£π ) = |π(π£π+3 ) β π(π£π )| = π(π β 4) + 2π + π β 4, untuk 1 β€ π β€ π, π = 4
8
Volume 1 No. 1 Edisi April 2015
ISSN : 2338-0896
Dari pelabelan di atas, dapat dilihat bahwa label pada setiap sisi berbeda. 1. Untuk π = 1, label titik-titik π£π π£π+1 berturut-turut adalah {2(ππ β π) + π + 2} , untuk π = 2, label titik-titik π£π π£π+1 berturut-turut adalah {2(2π + 2)} , untuk π = 3, sedangkan label titiktitikπ£π π£π+1 berturut-turut adalah {2(π β 1) + π}. π 2. Untuk π = 1,2,3, β¦ , π dan π = 1 label titik-titik π£π π£π berturut-turut adalah {2(ππ + π β 1), 2(ππ + π β 2), 2(ππ + π β 3), β¦ ,2(ππ + π β π)}, untuk π = 1,2,3, β¦ , π dan π = 2, label
titik-titik
π
π£π+1 π£π
berturut-turut
adalah
{2(ππ β π + 2), 2(ππ β π + 1), 2(ππ β π
π), β¦ ,2(ππ β 2π + 3)}, untuk π = 1,2,3, β¦ , π dan π = 3, label titik-titik π£π+2 π£π berturut-turut adalah {2(2π β 1) + π, 2(2π β 2) + π, 2(2π β 3) + π, β¦ ,2π + π} , untuk π = 1,2,3, β¦ , π
c.
π dan π = 4, sedangkan label titik-titik π£π+3 π£π berturut-turut adalah {ππ β 4π + 2, ππ β 4π + 4, ππ β 4π + 6, β¦ , ππ β 2π}. Untuk π = 5, yaitu graf caterpillar πΆππ,5 tanpa kepala dan ekor yang mempunyai 5 badan dan 5π kaki dengan aturan sebagai berikut: 2(ππ + π) β π, π=1 2π + π β 1, π=2 π=3 π(π£π ) = 3(π + π) + ππ β 2, π(π + 1) β 1, π=4 { ππ + π + π, π=5 2π β π, 1 β€ π β€ π, π = 1 2(ππ + π β π) + π, 1 β€ π β€ π, π = 2 π 1 β€ π β€ π, π = 3 π(π£π ) = 2(π + π β 1) + π, 2(ππ β π β π + π) β 1, 1 β€ π β€ π, π = 4 1 β€ π β€ π, π = 5 {ππ + π β 2π + π,
Dari pelabelan di atas, dapat dilihat bahwa label pada setiap titik berbeda. 1. Untukπ = 1, label titik-titikπ£π berturut-turut adalah {2(ππ + π) β 1}, untuk π = 2, label titiktitik π£π berturut-turut adalah {2π + 1} , untuk π = 3, label titik-titik π£π berturut-turut adalah {3π + ππ + 7} , untuk π = 4, label titik-titik π£π berturut-turut adalah {4π + 3} , sedangkan untuk π = 5, label titik-titikπ£π berturut-turut adalah {ππ + π + 5}. π 2. Untuk π = 1,2,3, β¦ , π dan π = 1 label titik-titik π£π berturut-turut adalah {1,3,5, β¦ ,2π β 1} , untuk π = 1,2,3, β¦ , π dan π = 2 , label titik-titik π£πβ² berturut-turut adalah {2(ππ + 1) + π, 2(ππ) + π, 2(ππ β 1) + π, β¦ ,2(ππ β π + 2) + π}, untuk π = 1,2,3, β¦ , π dan π = 3, label titik-titik π£πβ² berturut-turut adalah {2π + 3,2π + 5,2π + 7, β¦ ,4π + 1}, untuk π = 1,2,3, β¦ , π dan π = 4, label titik-titik π£πβ² berturut-turut adalah {2(ππ β π) + 5,2(ππ β π) + 3,2(ππ β π) + 1, β¦ ,2(ππ β 2π) + 7} , sedangkan untuk π = 1,2,3, β¦ , π dan π = 5 , label titik-titik π£πβ² berturut-turut adalah {ππ + π + 3, ππ + π + 1, ππ + π β 1, β¦ , ππ β π + 5}.
Setelah pelabelan titik-titiknya diperoleh maka sisi-sisinya pelabelan super graceful sebagai berikut. |π(π£π ) β π(π£π+1 )| = 2(ππ + π β π) β π β 1, |π(π£π ) β π(π£π+1 )| = ππ + π β π + 8, π(π£π π£π+1 ) = |π(π£π ) β π(π£π+1 )| = ππ β π + 3π β 5, { |π(π£π ) β π(π£π+1 )| = ππ + π β ππ β π + 6, π
akan mendapat label menurut aturan untuk π = 1 untuk π = 2 untuk π = 3 untuk π = 4
π
π(π£π π£π ) = |π(π£π ) β π(π£π )| = 2(ππ + π β π) + π β 1, untuk 1 β€ π β€ π, π = 1 π
π
π
π
π
π
π(π£π+1 π£π ) = |π(π£π+1 ) β π(π£π )| = 2(ππ β π β π + π) + π β 1, untuk 1 β€ π β€ π, π = 2 π(π£π+2 π£π ) = |π(π£π+2 ) β π(π£π )| = ππ + π β 2π β π + 9, untuk 1 β€ π β€ π, π = 3 π(π£π+3 π£π ) = |π(π£π+3 ) β π(π£π )| = 2(ππ β 3π β π + π β 2), untuk 1 β€ π β€ π, π = 4 9
Volume 1 No. 1 Edisi April 2015 π
ISSN : 2338-0896
π
π(π£π+4 π£π ) = |π(π£π+4 ) β π(π£π )| = 2π β π + 5, untuk 1 β€ π β€ π, π = 5 Dari pelabelan di atas, dapat dilihat bahwa label pada setiap sisi berbeda. 1. Untuk π = 1, label titik-titik π£π π£π+1 berturut-turut adalah {2(ππ + π β π + 1)} , untuk π = 2, label titik-titikπ£π π£π+1 berturut-turut adalah {ππ + π + 6}, untuk π = 3, label titik-titikπ£π π£π+1 berturut-turut adalah {ππ β π + 4}, sedangkan untuk π = 4, label titik-titikπ£π π£π+1 berturutturut adalah{ππ β 3π + 2}. π 2. Untuk π = 1,2,3, β¦ , π dan π = 1 label titik-titik π£π π£π berturut-turut adalah {2(ππ + π β 1), 2(ππ + π β 2), 2(ππ + π β 3), β¦ ,2(ππ + π β π)}, untuk π = 1,2,3, β¦ , π dan π = 2, label π titik-titik π£π+1 π£π berturut-turut adalah {2(ππ β π) + π + 1,2(ππ β π) + π β 1,2(ππ β π
π) + π β 3, β¦ ,2(ππ β 2π) + π + 3}, untuk π = 1,2,3, β¦ , π dan π = 3, label titik-titik π£π+2 π£π berturut-turut adalah {ππ + π + 4, ππ + π + 2, ππ + π, β¦ , ππ β π + 6} , untuk π = π
1,2,3, β¦ , π dan π = 4, label titik-titik π£π+3 π£π berturut-turut adalah {2(ππ β 3π + 1), 2(ππ β 3π), 2(ππ β 3π β 1), β¦ ,2(ππ β 4π + 2)}, sedangkan untuk π = 1,2,3, β¦ , π dan π = 5, label π
titik-titik π£π+4 π£π berturut-turut adalah {2,4,6, β¦ ,2π}. Dapat dilihat bahwa pelabelan pada himpunan titik dan pada himpunan sisi berbeda untuk 3 β€ π β€ 5, dengan gabungan dari kedua himpunan titik dan sisi adalah {1,2,3, β¦ ,2(ππ + π) β 1}. Maka π adalah pelabelan super graceful. Dengan demikian setiap graf caterpillarπΆππ,π tanpa kepala dan ekor adalah graf super graceful. Sebagai ilustrasi, Gambar 5 menunjukkan pelabelan super graceful pada graf caterpillar πΆππ,π tanpa kepala dan ekor yang mempunyai π badan dan ππ kaki, untuk π = 3 dan π = 3,4,5.
3
1
20
22
18
3
30
22
5 37 34
39
11
33 9 26
30 32
7
24
31
4 8
23
13 29
27
15
16
17
4 10
15
19
25 21
12 14
21 6
2
18
22
19
13 17
12 10
20
28
36 38
35
15
11
14
13 2
4
6 8
16
7
11
9
14
25 9
20 18
24
31
1
27
5 29
21
7
16
28 26
3
12
10
23
1
19
17
5
6
2 8
23
Gambar 5 Pelabelan super graceful pada graf caterpillar πΆπ3,3 , πΆπ3,4 , dan πΆπ3,5
10
Volume 1 No. 1 Edisi April 2015
ISSN : 2338-0896
Kesimpulan Dari uraian diatas dapat disimpulkan bahwa graf caterpillar πΆππ dengan atau tanpa kepala dan ekor yang mempunyai π badan dan 2 kaki pada tiap badan merupakan graf super graceful. Selain itu, Graf caterpillar πΆππ,π tanpa kepala dan ekor yang mempunyai 5 badan dan 5π juga merupakan graf super graceful. Referensi [1] Bala, E, dkk, Graph labeling in competition graph, Indian Journal of Science and Technology, 4(8): 0974-6846, 2011.
[2] Fathoni, A, Pelabelan Super Sisi Ajaib padaGraph Caterpillar, Tugas Akhir, Jurusan Matematika Fakultas Sains dan Teknologi, Universitas Islam Negeri Malang, 2009.
[3] Gallian, J.A, A Dynamic Survey of Graph Labeling, tenth edition, The Electronic Journal of Combinatorics, 17(11): 05C78, 2011.
[4] J.A. BondydanMurty, Graph Theory with Applications, Penerbit The Macmillan Press Ltd, 1976. [5] Kusumah, Y.S, Matematika Diskrit, Penerbit IKIP Bandung Press, 1997. [6] Munir, R, Matematika Diskrit, Penerbit Informatika, 2005. [7] Perumal, M.A., dkk, Super Graceful Labeling For Some Special Graphs, Journal Mathematics, 9(3): 06, 2011.
[8] Watson, R. Lynn, A Survey on The Graceful Labeling of Graph, This Thesis for the Master of Science, University of Colorado at Denver in Partial fulfillment of the requirements for the degree of Master of Science Applied Mathematics, 2000.
11
