1
Pelabelan Total Sisi Ajaib Pada Subkelas Pohon Hilda Rizky Ningtyas, Dr. Darmaji, S.Si., M.T.[1] Jurusan Matematika, Fakultas MIPA, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 E-mail:
[email protected][1]
Abstrak— Graf G(V,E) dikatakan memenuhi pelabelan total sisi ajaib jika elemen-elemen graf yaitu simpul dan sisi dipetakan dengan satu bilangan asli dari 1,2,3,, V + E .
{
}
Sehingga untuk masing-masing sisi berlaku λ ( x) + λ ( xy ) + λ ( y ) = k , dengan x, y ∈ V (G ) dan xy ∈ E (G ) . Notasi λ merupakan fungsi bijektif yang memetakan sisi dan simpul graf ke bilangan asli sehingga penjumlahan label dari semua sisi yang melekat pada simpul tertentu ditambah dengan label simpul tersebut mempunyai hasil yang sama. Konstanta disebut bilangan ajaib (magic sum). Pada Tugas Akhir ini peroleh pelabelan total sisi ajaib pada graf kembang api
(
dan graf pohon pisang Bm, n
)
dengan m = 2 dan
n
(F ) m,n
bilangan
asli. Dari analisis yang dilakukan diperoleh hasil bahwa graf kembang api F2, n dengan n bilangan asli adalah graf edge magic
sehingga jumlah dari label sisi disetiap simpul di G semua sama[1]. Kotzig dan Rosa membuktikan beberapa pelabelan untuk n ≥ 3 , total sisi ajaib diantaranya pada graf cycle graf lengkap K n jika dan hanya jika n = {1,2,3,4,5,6} , dan semua graf caterpillar[2]. Karena pelabelan total sisi ajaib (edge magic total labeling) berkaitan dengan pengkonstruksian fungsi, maka dimungkinkan fungsi yang dibuat seorang peneliti akan berbeda dengan fungsi yang dibuat peneliti lain pada graf yang sama. Pada Tugas Akhir ini, dilakukan kajian pelabelan total sisi ajaib (edge magic total labeling) pada subkelas dari pohon yaitu graf kembang api dan graf pohon pisang dengan m = 2 dan sebarang bilangan asli.
total labeling dengan k = 4n + 12 , dan graf pohon pisang B2, n dengan n bilangan asli adalah graf edge magic total labeling dengan k = 4n + 10 . Kata kunci : Graf, Pelabelan Total Sisi Ajaib, Graf Kembang Api, Graf Pohon Pisang
I. PENDAHULUAN
T
EORI graf merupakan salah satu bagian penting dalam kehidupan manusia. Beberapa contoh masalah dalam kehidupan sehari-hari yang dapat diabstraksikan sebagai masalah yang berkaitan dengan teori graf, misalnya rangkaian listrik, menentukan jarak terpendek dari suatu lintasan dan desain komunikasi dengan aplikasi pelabelan graf. Pelabelan pada suatu graf adalah pemetaan sebarang atau fungsi yang memasangkan elemen-elemen graf yaitu simpul dan sisi dengan satu bilangan asli. Pemberian label pada elemen graf ini disebut weight. Weight untuk setiap sisi . Jika (edge) xy adalah domain dari pemetaan adalah simpul, maka pelabelan disebut pelabelan simpul (vertex labeling). Jika domainnya adalah sisi, maka disebut pelabelan sisi (edge labeling), dan jika domainnya simpul dan sisi, maka disebut pelabelan total (total labeling). Sedláčk telah menerbitkan sebuah makalah tentang jenis lain dari pelabelan graf. Ia menyebut pelabelan ajaib (magic labeling). Definisi pelabelan ajaib didorong oleh gagasan persegi ajaib. Pelabelan ajaib (magic labeling) adalah fungsi λ dari himpunan sisi graf G menjadi bilangan asli,
II. PELABELAN TOTAL SISI AJAIB Pelabelan total sisi ajaib (λ) pada suatu graph (G) dari
V (G ) E (G ) ke himpunan {1,2,3,, p + q} dimana p = V (G )
dan q = E (G ) sehingga untuk masing-masing sisi xy di G berlaku λ ( x) + λ ( xy ) + λ ( y ) = k , untuk k konstanta dan λ merupakan fungsi bijektif yang memetakan sisi dan simpul graf ke bilangan asli (N). Konstanta k disebut bilangan ajaib (magic sum) dengan kata lain, wt ( xy ) = k untuk setiap sisi (edge) [3]. Misalkan adalah pelabelan total sisi ajaib, jika x dan y adalah simpul yang berdekatan, maka sisi xy mempunyai label k − λ (x ) − λ ( y ) . Jadi
∑
didapat
xy∈E
(λ (xy ) + λ (x ) + λ ( y )) = qk .
Persamaan ini terdiri dari penjumlahan label tiap simpul dan sisi dan pelabelan simpul yang mempunyai derajat tambahan di − 1 , sehingga qk =
∑ f ( p ) + ∑ f (q ) + ∑ (d − 1)λ i
p∈V
i
(1)
q∈E
III. PELABELAN TOTAL SISI AJAIB PADA GRAF KEMBANG API DAN POHON PISANG A. Bilangan Ajaib Graf Kembang Api Graf kembang api didapatkan dengan menghubungkan satu simpul anting dari graf bintang secara berurutan. Lintasan
2 yang menghubungkan simpul-simpul daun dari barisan graf bintang tersebut disebut backbone dari graf kembang api. Jika banyaknya simpul anting sama maka graf tersebut merupakan graf kembang api teratur. Dinotasikan dengan dengan m adalah jumlah simpul backbone dan n adalah jumlah simpul anting. Sebuah graf kembang api mempunyai simpulsimpul dan sisi-sisi
(
)
{ {a21, a22 ,, a2 j }
}
V F2, n = {x1, x2 } {c1, c2 } a11, a12 ,, a1 j
(
)
Bilangan ajaib k dapat ditemukan jika terdapat nilai pada simpul tersebut. Bilangan ajaib tersebut didapat dengan meminimumkan dan memaksimalkan nilai pelabelannya[4]. Sehingga didapatkan rentang bilangan ajaib k untuk pelabelan total sisi ajaib pada graf F2, n . Teorema 1 Jika Graf adalah graf edge magic total, maka bilangan ajaibnya (magic sum) teletak pada
(
)
(
1 2 1 8n + 33n + 35 ≤ k ≤ 16n 2 + 51n + 37 q q
E F2, n = {x1x2 } {x1c1, x2c2 }
{c1a11, c2a12 ,, c1a1 j } {c2a21, c2a22 ,, c2a2 j }
)
Bukti: Bilangan ajaib akan bernilai minimum saat simpul berderajat paling besar dilabeli dengan label paling kecil[4]. Persamaan Lemma 1 menjadi:
Gambar 1 adalah contoh graf kembang api teratur
k=
m 1 2 8n + 30n + 28 + λ (x1 ) + λ (x2 ) + n λ (c1 ) q i =1 1 = 8n 2 + 30n + 28 + 3n + 3 + 4 q
(
)
(( 1 = (8n q
2
∑
) + 33n + 35)
)
Dan k akan bernilai maksimum saat simpul berderajat paling besar dilabeli dengan label paling besar[4]. Persamaan Lemma 1 menjadi: Gambar 1. Graf kembang api Graf kembang api
k=
Reguler V (G ) = p = 2n + 4
mempunyai
dan E (G ) = q = 2n + 3 . dikatakan Dari Persamaan (1) Graf kembang api yang memenuhi mempunyai pelabelan total sisi ajaib Lemma 1: Lemma 1 Jika Graf adalah graf edge magic total, maka bilangan ajaibnya (magic sum) adalah m 1 ( k = 8n 2 + 30n + 28 + λ (x1 ) + λ (x2 ) + n λ c1 ) q i =1
(
)
∑ p∈V
∑
q∈E
(2)
2
Persamaan (2) disubtitusikan kedalam persamaan (1) sehingga didapatkan nilai k untuk graf kembang api qk =
(4n + 7 )(4n + 8) + λ (x ) + λ (x ) + n m λ (c ) + 0 1 2 ∑ 1 2
(
)
qk = 8n 2 + 30n + 28 + λ (x1 ) + λ (x2 ) + n
=
(
1 16n 2 + 51n + 37 q
)
adalah graf edge magic total dengan Jadi terbukti jika bilangan ajib k terletak pada rentang
(
)
(
)
1 2 1 8n + 33n + 35 ≤ k ≤ 16n 2 + 51n + 37 ∎ q q
B. Pelabelan Total Sisi Ajaib Graf Kembang Api
m = 2 , dinotasikan dengan
λ (q ) = 1 + 2 + + (4n + 7 )
(4n + 7 )(4n + 8) =
)
Secara umum graf kembang api F2, n dengan
∑
Bukti: Diasumsikan bahwa graf adalah graf total sisi ajaib, dengan demikian simpul dan sisi dilabelkan dari angka 1 sampai ( p + q ) sehingga: λ( p) +
((
1 8n 2 + 30n + 28 + n(8n + 13) + 4n + 5 + 4n + 4 ) q
i =1 m
∑ λ (c ) + 0 1
i =1
Jadi terbukti, diperoleh bilangan ajaib k untuk pelabelan total sisi ajaib pada Graf Kembang Api.
. Mempunyai simpul dan
sisi:
( ) { E (F2, n ) = {x1x2 } {x1c1, x2c2 }
} {
V F2, n = {x1, x2 } {c1, c2 } a11, a12 ,, a1 j a21, a22 ,, a2 j
}
{c1a11, c2a12 ,, c1a1 j } {c2a21, c2a22 ,, c2a2 j }
Jumlah simpul dan sisi masing–masing adalah V ( F2, n ) = 2(n + 2 ) dan E ( F2, n ) = 2(n + 2) − 1 . Teorema 2 Jika adalah sebuah graf kembang api dengan dua simpul mempunyai backbone {x1x2 } dan buah anting , maka pelabelan total sisi ajaib dengan k = 4n + 12 . Bukti: Misalkan graf kembang api
mempunyai,
( ) { } E (F2, n ) = {x1x2 , x1c1, x2c2 , c1a11,, c1aij , c2 a21,, c2 a2 j }
V F2, n = x1, x2 , c1, c2 , a11,, a1 j , a21,, a2 j
3 Sehingga
(
mempunyai sisi
)
V F2, n = {λ (x1 ) + λ (x1x2 ) + λ (x2 )} {λ (x1 ) + λ (x1c1 ) + λ (c1 )}
{λ (x2 ) + λ (x2c2 ) + λ (c2 )} {λ (ci ) + λ (ci aij ) + λ (aij )} Didefinisikan V (F2, n ) E (F2, n ) ke himpunan {1,2,3,, p + q} dimana p = V (G ) dan q = E (G ) dengan pola sebagai berikut: λ (x1 ) = 2n + 6 λ (x2 ) = 2 λ (c1 ) = 2i − 1 λ aij = 2 j − i + 4
yang disebut simpul akar mempunyai:
(
)
(
)
. Sebuah Graf Pohon Pisang
{
} {
}
V B2, n = {c1 , c2 } {x1 , x2 } a11 , a12 , , a1 j a21 , a22 , , a2 j {r} E B2, n = {x1r , x2 r} {x1c1, x2c2 }
{c1a11, c2a12 ,, c1a1 j } {c2a21, c2a22 ,, c2a2 j }
Untuk 1 ≤ i ≤ m dan 1 ≤ j ≤ n − 1 . Gambar 3 adalah contoh graf pohon pisang
( )
λ (x1x2 ) = 2n + 4 λ (x1c1 ) = 2n + 5 λ (x2c2 ) = 4n + 7 λ c1aij = 4n + 9 − 2 j − i
( )
karena masing-masing sisi berlaku λ ( x) + λ ( xy ) + λ ( y ) = k , maka:
a.
{λ (x1 ) + λ (x1x2 ) + λ (x2 )} = (2n + 6 ) + (2n + 4 ) + 2
b.
{λ (x1 ) + λ (x1c1 ) + λ (c1 )} = (2n + 6 ) + (2n + 5) + (2i − 1) = (2n + 6 ) + (2n + 5) + (2(1) − 1)
= 4n + 12
= 4n + 12
c.
{λ (x2 ) + λ (x2c2 ) + λ (c2 )} = (2 ) + (4n + 7 ) + (2i − 1) = (2 ) + (4n + 7 ) + (2(1) − 1) = 4n + 12
d.
{λ (ci ) + λ (ci aij ) + λ (aij )} = (2i − 1) + (4n + 9 − 2 j − i ) + (2 j − i + 4 )
Gambar 3 Graf Banana Tree Graf
pohon pisang mempunyai V (G ) = p = 2n + 3 dan E (G ) = q = 2n + 2 . Sama seperti graf kembang api, graf pohon pisang dikatakan pelabelan total sisi ajaib jika mempunyai bilangan ajaib sesuai Persamaan (1). Sehingga didapat Lemma 2, Lemma 2 Jika Jika graf adalah graf edge magic total, maka bilangan ajaibnya (magic sum) adalah k=
= 4n + 12
Jadi terbukti bahwa graf kembang api dengan bilangan asli adalah graf yang mempunyai pelabelan total sisi ajaib dengan k = 4n + 12 ■ dengan Pelabelan Total sisi ajaib pada graf kembang api k = 28 digambarkan seperti pada Gambar 2
Reguler
1 2 8n + 22n + 15 + (m − 1)λ (r ) + q
(
)
m
∑
m
∑ λ (c )
λ (xi ) + (n − 1)
i =1
i
i =1
Bukti: Diasumsikan bahwa graf adalah graf yang mempunyai pelabelan total sisi ajaib, dengan simpul dan sisi diberi label dari angka 1 sampai ( p + q ) maka:
∑ λ ( p ) + ∑ λ (q ) = 1 + 2 + + (4n + 5) p∈V
q∈E
=
(4n + 5)(4n + 6)
(3)
2
Persamaan (3) disubtitusikan kedalam persamaan (1) sehingga didapatkan nilai k untuk graf pohon pisang qk =
Gambar 2 Graf Kembang Api C. Bilangan Ajaib Graf Pohon Pisang Graf pohon pisang Bm, n adalah sebuah graf yang diperoleh dengan menghubungkan satu simpul anting dari setiap buah salinan graf bintang ke sebuah simpul baru
(4n + 5)(4n + 6) + (m − 1)λ (r ) + + 2
qk = 8n 2 + 22n + 15 + (m − 1)λ (r ) + +
m
∑
i =1 m
∑ λ (x ) + (n − 1)∑ λ (c ) i
1 2 8n + 22n + 15 + (m − 1)λ (r ) + q
(
)
i
i =1 m
i
i =1
k=
m
∑ λ (c )
λ (xi ) + (n − 1)
i =1
m
m
∑ λ (x ) + (n − 1)∑ λ (c ) i
i =1
i
i =1
Jadi terbukti, diperoleh bilangan ajaib k untuk pelabelan total sisi ajaib pada Graf Pohon Pisang.
4 Dari Lemma 2 didapatkan nilai bilangan ajaib untuk graf . Bilangan ajaib k dapat ditemukan jika nilai pada simpul tersebut didapat dengan meminimumkan dan memaksimalkan nilai pelabelannya[4]. Sehingga didapatkan rentang bilangan ajaib k untuk pelabelan total sisi ajaib pada graf . Teorema 3 Jika graf adalah graf edge magic total, maka bilangan ajaibnya (magic sum) teletak pada rentang
(
)
(
)
(
)
(
)
1 2 1 8n + 33n + 12 ≤ k ≤ 16n 2 + 29n + 24 untuk n < 2 q q 1 2 1 8n + 25n + 24 ≤ k ≤ 16n 2 + 33n + 12 untuk n ≥ 2 q q
Bukti: Bilangan ajaib akan bernilai minimum saat simpul berderajat paling besar dilabeli dengan label paling kecil[8]. Sehingga Lemma 4.2 menjadi batas bawah dari rentang nilai k yaitu: Untuk n < 2 ;
((
)
(
)
)
D. Pelabelan Total Sisi Ajaib Graf Pohon Pisang
Secara umum graf pohon pisang Bm,n dengan . Mempunyai simpul dan m = 2 , dinotasikan dengan sisi
( (
) )
{
E B2, n = {x1r , x2 r} {x1c1, x2c2 }
1 2 8n + 31n + 12 q
Untuk 1 ≤ i ≤ m dan 1 ≤ j ≤ n − 1 . Jumlah simpul dan sisi masing–masing adalah V ( B2, n ) = 2n + 3 dan E (B2, n ) = 2n + 2 . Teorema 4 Graf adalah sebuah graf pohon pisang dengan salinan adalah graf yang graf bintang dan buah anting, maka mempunyai pelabelan total sisi ajaib dengan k = 4n + 10 . Bukti: Misalkan graf Pohon pisang
(
) (
) {
(( 1 k = (8n q
(
{x1r, x2r, x1c1, x2c2 , c1a11, c2a12 ,, c1a1 j } {c2a21, c2a22 ,, c2a2 j }
(( 1 k = (16n q
) + 25n + 24 )
)
(
) + 29n + 24 )
Untuk n ≥ 2 ;
((
) (
(
)
))
)
)
λ (x1 ) = n + i + 2 λ (x2 ) = 2i − 1 λ (rxi ) = 3n − i + 6 λ (xi ci ) = 3n − 3i + 9 λ (r ) = 2 λ a1 j = 2 + i + j
( ) λ (a2 j ) = n + i + j + 2 λ (c1a1 j ) = 4n + i − j + 5 λ (c2 a2 j ) = 3n + 2i − j − 1
karena masing-masing sisi berlaku λ ( x) + λ ( xy ) + λ ( y ) = k , maka:
1 k= 8n 2 + 22n + 15 + 8n 2 − n − 9 + (4n + 7 ) + (8n + 3) q 1 k = 16n 2 + 33n + 12 q
mempunyai sisi
dimana p = V (G ) dan q = E (G ) dengan pola sebagai berikut:
1 8n 2 + 22n + 15 + (4n + 5) + (8n + 7 ) + 8n 2 − 5n − 3 q 2
)
{λ (c1 ) + λ (c1a1 j ) + λ (a1 j )} {λ (c2 ) + λ (c2ai 2 j ) + λ (ai 2 j )} Didefinisikan V (B2, n ) E (B2, n ) ke himpunan {1,2,3,, p + q}
Dan k akan bernilai maksimum saat simpul berderajat paling besar dilabeli dengan label paling besar. Sehingga Lemma 4.2 menjadi batas atas dari rentang nilai k yaitu: Untuk n < 2 ; k=
}
V B2, n = {λ (r ) + λ (rxi ) + λ (xi )} {λ (xi ) + λ (xici ) + λ (ci )}
1 8n 2 + 22n + 15 + (3n − 3) + (3) + (9 ) q 2
mempunyai,
V B2, n E B2, n = c1, c2 , x1, x2 , r , a11, a12 ,, a1 j
Sehingga
Untuk n ≥ 2 ; k=
}
{c1a11, c2a12 ,, c1a1 j } {c2a21, c2a22 ,, c2a2 j }
1 8n 2 + 22n + 15 + (1) + (5) + (9n − 9 ) k= q
k=
} {
V B2, n = {c1, c2 } {x1, x2 } a11, a12 ,, a1 j a21, a22 ,, a2 j {r}
a.
{λ (r ) + λ (rxi ) + λ (xi )} = (2 ) + (3n − i + 6 ) + (n + i + 2 ) = 4n + 10
adalah graf edge magic total dengan bilangan Jadi jika ajaib, maka k terletak pada rentang
(
)
(
)
(
)
(
)
b.
1 2 1 8n + 33n + 12 ≤ k ≤ 16n 2 + 29n + 24 untuk n < 2 q q 1 2 1 8n + 25n + 24 ≤ k ≤ 16n 2 + 33n + 12 untuk n ≥ 2 q q
{λ (xi ) + λ (xici ) + λ (ci )} = (n + i + 2 ) + (3n − 3i + 9 ) + (2i − 1) = 4n + 10
■
c.
{λ (c1 ) + λ (c1a1 j ) + λ (a1 j )} = (2i − 1) + (4n + i − j + 5) + (2 + i + j )
= (2 × 1 − 1) + (4n + 1 − j + 5) + (2 + 1 + j )
= 4n + 10
5
d.
{λ (c2 ) + λ (c2ai 2 j ) + λ (ai 2 j )}
(
)
(
)
1 2 1 8n + 25n + 24 ≤ k ≤ 16n 2 + 33n + 12 untuk n ≥ 2 q q
= (2i − 1) + (3n + 2i − j − 1) + (n + i + j + 2 )
Dan mempunyai bilangan ajaib k = 4n + 10 dengan pola sebagai berikut:
= (2 × 2 − 1) + (3n + 2 × 2 − j − 1) + (n + 2 + j + 2 )
= 4n + 10
λ (x1 ) = n + i + 2 λ (x2 ) = 2i − 1 λ (rxi ) = 3n − i + 6 λ (xi ci ) = 3n − 3i + 9 λ (r ) = 2 λ a1 j = 2 + i + j
Jadi terbukti bahwa graf pohon pisang dengan bilangan asli adalah graf yang mempunyai pelabelan total sisi ajaib dengan k = 4n + 10 ∎
( ) ( ) λ (c1a1 j ) = 4n + i − j + 5 λ (c2 a2 j ) = 3n + 2i − j − 1
λ a2 j = n + i + j + 2
DAFTAR PUSTAKA [1]
Gambar 4 Graf Pohon Pisang Pelabelan Total sisi ajaib pada graf pohon pisang digambarkan seperti pada Gambar 4
[2]
dengan
IV. SIMPULAN
1. Graf
adalah sebuah graf kembang api dengan
dua simpul backbone {x1x2 } dan maka
buah anting ,
adalah graf yang mempunyai pelabelan
total sisi ajaib dan mempunyai bilangan ajaib (magic sum) teletak teletak pada
(
)
(
1 2 1 8n + 33n + 35 ≤ k ≤ 16n 2 + 51n + 37 q q
)
Dan mempunyai bilangan ajaib k = 4n + 12 dengan pola sebagai berikut: λ (x1 ) = 2n + 6 λ (x2 ) = 2 λ (c1 ) = 2i − 1 λ aij = 2 j − i + 4
( )
λ (x1x2 ) = 2n + 4 λ (x1c1 ) = 2n + 5 λ (x2c2 ) = 4n + 7 λ c1aij = 4n + 9 − 2 j − i
( )
2. Graf B2,n adalah sebuah graf pohon pisang dengan salinan graf bintang dan
buah anting, maka B2,n
adalah graf yang mempunyai pelabelan total sisi ajaib maka bilangan ajaibnya (magic sum) teletak pada
(
)
(
)
1 2 1 8n + 33n + 12 ≤ k ≤ 16n 2 + 29n + 24 untuk n < 2 q q
[3] [4]
J, Sedláčk. (1963). “Theory of Graphs and Its Applications”. Problem 27, Proc. Symposium Smolenice, June 1963. 163-167. Kotzig .A, Rosa .A. (1970). “Magic valuations of finite graphs”. Canad. Math. Bull, 13. 451-461. Wallis, W.D. (2001). “Magic Graphs”. Boston, Birkauser Muthoharoh. (2007). ”Pelabelan edge magic dan super edge magic pada pohon biner”. Tesis. ITS.
