KAJIAN DAN ALGORITMA PELABELAN PSEUDO EDGE-MAGIC. memiliki derajat maksimum dan tidak ada titik yang terisolasi. Jika n i adalah

BAB III KAJIAN DAN ALGORITMA PELABELAN PSEUDO EDGE-MAGIC

III.1 Batas Bawah Magic Number pada Pelabelan Total Pseudo Edge-Magic Teorema 3.1.11 Anggap G = (V,E) adalah sebuah graf dengan n-titik dan m-sisi dan memiliki derajat maksimum ∆ dan tidak ada titik yang terisolasi. Jika ni adalah jumlah titik dengan derajat i, dan Ni adalah jumlah titik dengan derajat paling sedikit i, maka nilai minimal magic-number dalam pelabelan total pseudo edge-magic dari G adalah :

1 1⎛ ∆ 1 ⎛ ⎞⎞ n + ( m + 1) + ⎜ ∑ ni i ⎜ Ni +1 + ( ni + 1) ⎟ ⎟ 2 2 m ⎝ i =1 ⎝ ⎠⎠ Bukti : λ adalah sebuah pelabelan pseudo edge-magic dari graf G dengan magic-number κ. Maka untuk setiap sisi vw ∈ E berlaku λ (v) + λ (vw) + λ ( w) = κ , karenanya, :

κ .m =

∑ ( λ ( v ) + λ ( vw ) + λ ( w ) ) = ∑

vw∈ E

1

vw∈ E ( v )

λ ( vw ) + ∑ ( deg ( v ) .λ ( v ) ) v∈V

Wood 2006 [8]

21 Pelabelan Pseudo Edge-Magic dan Pseudo Vertex-Magic pada Graf Sebarang

Bab IV Pelabelan Pseudo Vertex-Magic

dengan deg ( v ) adalah derajat titik v. Karena graf terhubung, maka pastilah deg ( v ) ≥ 1 untuk setiap titik v ∈ V , maka nilai

κ .m =

∑ λ ( vw ) + ∑ deg ( v ) .λ ( v )

vw∈ E

akan minimum bila setiap titik dilabeli

vw∈ E

dengan (1,2,...,n) dengan titik yang berderajat besar dilabeli dengan label yang kecil dan sebaliknya titik yang berderajat kecil dilabeli dengan label yang besar, dan setiap sisi dilabeli dengan (n+1,n+2,...,n+m). Maka untuk setiap titik berderajat i ,1 ≤ i ≤ ∆ dilabeli dengan {Ni+1+1,Ni+1+2,...,Ni+1+ni} dengan Ni+1+ni = Ni maka :

κ .m =

∆

ni

i =1

k =1

∑ λ ( vw ) + ∑ deg ( v ) .λ ( v ) ≥ ∑ i ∑ ( N

vw∈ E

∆

vw∈ E

⎛ ⎝

κ .m ≥ ∑ i ⎜ N i +1 .ni + i =1

m

i +1 + k ) + ∑ ( n + j ) j =1

1 1 ⎞ ⎛ ⎞ ni ( ni + 1) ⎟ + ⎜ n.m + m . ( m + 1) ⎟ 2 2 ⎠ ⎝ ⎠

dengan membagi kedua ruas dengan m, maka didapat

κ ≥

1⎛ ∆ ⎛ 1 1 ⎞⎞ ⎛ ⎞ i ⎜ N i +1 .ni + ni ( ni + 1) ⎟ ⎟ + ⎜ n + ( m + 1 ) ⎟ ∑ ⎜ m ⎝ i =1 ⎝ 2 2 ⎠⎠ ⎝ ⎠

κ ≥

1⎛ ∆ 1 1 ⎛ ⎞⎞ ⎛ ⎞ ni i ⎜ N i +1 + ( ni + 1 ) ⎟ ⎟ + ⎜ n + ( m + 1 ) ⎟ ∑ ⎜ m ⎝ i =1 2 2 ⎝ ⎠⎠ ⎝ ⎠

W

Akibat 3.1.1 2 Nilai minimal magic number untuk pelabelan pseudo edge-magic

sebuah graf regular G dengan n-titik dan m-sisi adalah :

κ ≥

1 ( m + 3 ) + 2.n 2

Bukti : Misalkan ada sebuah graf pelabelan pseudo edge magic dari sebuah graf ∆-reguler

2

Wood 2006 [8]

22 Pelabelan Pseudo Edge-Magic dan Pseudo Vertex-Magic pada Graf Sembarang


dengan n-titik dan m-sisi dengan magic number κ. Menurut Teorema 3.1.1, maka :

κ ≥

1⎛ ∆ ⎛ 1 1 ⎞⎞ ⎛ ⎞ i ⎜ N i +1 .ni + ni ( ni + 1) ⎟ ⎟ + ⎜ n + ( m + 1 ) ⎟ ∑ ⎜ m ⎝ i =1 ⎝ 2 2 ⎠⎠ ⎝ ⎠ ∆

Karena graf G adalah graf ∆-reguler, maka nilai

⎛

∑ i ⎜⎝ N i =1

i +1

.ni +

1 ⎞ ni ( ni + 1) ⎟ hanya 2 ⎠

akan ada untuk nilai i = ∆ dan karena Ni+1 adalah jumlah titik berderajat lebih dari i+1 maka N i +1 = 0 sedangkan karena ni adalah jumlah titik berderajat i, maka ni = n , sehingga ∆

⎛

1 ⎞ ⎛1 ⎞ ni ( ni + 1 ) ⎟ = ∆ ⎜ n ( n + 1 ) ⎟ 2 ⎠ ⎝2 ⎠ i =1 1 ∆ ⎛ 1 1 ⎞ ⎛ ⎞ persamaan κ ≥ ∑ i ⎜ N i +1 .ni + ni ( ni + 1) ⎟ + ⎜ n + ( m + 1) ⎟ 2 2 m i =1 ⎝ ⎠ ⎝ ⎠

∑ i ⎜⎝ N

dan

i +1

.ni +

akan

menjadi :

κ≥

∆ 1 1 ⎛ ⎞ n ( n + 1) + ⎜ n + ( m + 1) ⎟ m 2 2 ⎝ ⎠

karena G adalah graf ∆-reguler, maka tiap titik berderajat ∆ . Setiap satu buah titik terkait dengan ∆ buah sisi, dan setiap sisi terkait dengan dua buah titik, sehingga jumlah sisinya adalah m =

κ ≥

1 .n.∆ . Maka persamaan di atas akan menjadi : 2

1 n∆ ( n + 1) + ⎛⎜ n + ( m + 1) ⎞⎟ = 2m 2 ⎝ ⎠

=n+

1 n.∆ ⎛ ⎞ n + 1) + ⎜ n + ( m + 1) ⎟ ( 2 ⎛1 ⎞ ⎝ ⎠ 2 ⎜ n.∆ ⎟ 2 ⎝ ⎠

1 1 ( m + 1) + ( n + 1) = ( m + 3 ) + 2 n 2 2

W

III.2 Algoritma pada Pelabelan Total Pseudo Edge-Magic Algoritma yang digunakan untuk melakukan pelabelan pseudo edge-magic ini terbagi



menjadi dua tahap. Tahap pertama adalah pelabelan titik dengan menggunakan algoritma Greedy Edge-Antimagic Vertex-Labeling. Kemudian setelah semua titik selesai

dilabeli,

pelabelan

dilanjutkan

dengan

algoritma

Extend

Pseudo

Edge-Antimagic Vertex-Labeling.

III.2.1 Algoritma Greedy Edge-Antimagic Vertex-Labeling

Langkah pertama yang kita lakukan dalam melakukan pelabelan pseudo edge-magic ini adalah dengan melakukan pelabelan titik pseudo edge-antimagic yang bisa kita peroleh dengan algoritma Greedy Edge-Antimagic Vertex-Labeling di bawah ini

Masukan

: Graf G=(V,E)

Keluaran

: Pelabelan titik edge-antimagic

Langkah-langkah : 1.

Mengurutkan titik-titik {v1,v2,...,vn} berdasarkan derajatnya. Dengan titik berderajat besar berada paling awal ( deg ( vi ) ≤ deg ( vi +1 ) ,1 ≤ i ≤ n − 1 )

2.

Untuk i = 1,2,...,n ¾

Ambil label λ ( vi ) sebagai bilangan bulat positif L yang memenuhi : i.

Untuk semua i < j , L ≠ λ ( v j )

ii.

Untuk semua sisi vi v j , v p v q ∈ E dengan j , p, q < i dan p ≠ j ≠ q 24

Pelabelan Pseudo Edge-Magic dan Pseudo Vertex-Magic pada Graf Sembarang


Berlaku : L ≠ λ ( v p ) + λ ( vq ) − λ ( v j )

Dengan demikian, dari algoritma ini didapatkan pelabelan titik edge-antimagic pada graf G yang diberikan yang dibutuhkan dalam algoritma Extend Edge-Antimagic Vertex-Labeling di bawah ini.

III.2.2 Algoritma Extend Edge-Antimagic Vertex-Labeling

Langkah kedua setelah kita mendapatkan pelabelan titik edge-antimagic ini adalah dengan melakukan pelabelan total pseudo edge-magic yang bisa kita peroleh dengan algoritma Extend Edge-Antimagic Vertex-Labeling di bawah ini

Masukan

: Pelabelan titik Pseudo edge-antimagic dari graf G=(V,E)

Keluaran

: Pelabelan total pseudo edge-magic

Langkah-langkah : 1.

Ambil nilai ΛV sebagai nilai label λ ( v ) yang terbesar dari semua v ∈ V

2.

Ambil nilai Λ E sebagai jumlah label λ ( v ) + λ ( w ) yang terbesar dari semua vw ∈ E

3.

Ambil κ sebagai nilai I minimum yang memenuhi : I ≠ λ ( x ) + λ ( v ) + λ ( w ) , ∀x ∈ V , vw ∈ E dan Λ E + 1 ≤ I ≤ ΛV + Λ E + 1



4.

Untuk setiap sisi vw ∈ E nilai dari label λ ( vw ) = κ − λ ( v ) − λ ( w )

Maka pada akhir algoritma Extend Edge-Antimagic Vertex Labeling ini akan didapat pelabelan total pseudo edge-magic untuk graf G

. III.2.3 Contoh Algoritma Pelabelan Total Pseudo Edge-Magic v2

v7 v1

2

7 1

v3

v6

3

6

v5

5

v4

Gambar 3.1 {v1,v2,...,vn} terurut

Gambar 3.2 Pelabelan {v1,v2,...,vn}

2

7 8 1

9

1 3 12

6 10 5

4

11 4

Gambar 3.3 Pelabelan Total Pseudo Edge-Magic



III.3 Batas Atas Magic Number pada Algoritma Pelabelan Total Pseudo Edge-Magic Lemma 3.3.13 Jika λ adalah sebuah pelabelan pseudo edge-magic, ΛE adalah jumlah

terbesar dari λ(v)+λ(w) untuk setiap vw ∈ E dan ΛV adalah label terbesar dari λ(v) untuk setiap v ∈ V , maka nilai maksimum magic number dari pelabelan λ adalah 3Λ V Bukti : Karena ΛV adalah label titik yang terbesar, sedangkan ΛE adalah jumlah label dua buah titik ujung dari sisi, maka ΛV +1 adalah label yang belum digunakan dalam pelabelan titik. Maka ΛE+ ΛV +1 pastilah merupakan suatu magic number κ yang berlaku untuk sebarang ΛE dan ΛV dan sebarang graf sehingga pastilah ada κ ' ≤ Λ E + Λ V + 1 . Karena label setiap titik haruslah berbeda, maka pastilah jumlah terbesar dua buah titik ujung

dari

sisi

tidak

mungkin

lebih

dari

dua

label

terbesar

yaitu

Λ E ≤ Λ V + Λ V − 1 = 2 Λ V − 1 . Sehingga bila kita substitusikan, akan didapat :

W

κ ≤ ( 2 Λ V − 1) + Λ V + 1 = 3Λ V

3

Wood 2006 [5]


Bab IV Pelabelan Pseudo Vertex-Magic Teorema 3.3.1 4 Untuk setiap n, graf lengkap Kn memiliki pelabelan pseudo

edge-magic dengan nilai magic number maksimum 3n 2 + o ( n 2 ) Bukti : Ambil nilai f(x) sebagai suku terbesar dari suatu barisan Sidon dengan x-suku, dan ambil nilai g(n) sebagai suku terbesar yang terkecil dari kemungkinan suatu barisan Sidon dengan n-suku karena barisan Sidon dapat dikonstruksi dan menghasilkan banyak kemungkinan barisan. Dapat kita lihat bahwa fungsi g adalah invers (kebalikan) dari fungsi f, dan batas bawah serta batas atas bagi fungsi g dan f didapat dari struktur barisan Sidon. Menurut Halberstam dan Roth, fungsi f(x) yang mendekati barisan Sidon adalah f ( x ) =

x +o

( x) .

Karena g(n) adalah invers dari f(x), maka

g ( n ) = n 2 + o ( n 2 ) , yang berarti bahwa ada sebuah barisan Sidon dengan banyak suku n dengan suku terbesar n 2 + o ( n 2 ) dalam hal ini, suku terbesar barisan Sidon ini adalah juga label titik yang terbesar ( ΛV ). Sehingga menurut Lemma 3.3.1 di atas, maka nilai magic number maksimal adalah sebesar 3ΛV = 3n 2 + o ( n 2 )

W

Teorema 3.3.25 Algoritma Greedy Edge-Antimagic Vertex-Labeling dapat melabeli

4

Wood 2006 [9]

5

Wood 2006 [14]



sebuah graf G dengan n titik dan m sisi yang memiliki derajat tertinggi ∆ dengan nilai label terbesar kurang dari ∆ ( m − ∆ ) + n

Bukti : Pada setiap langkah algoritma, untuk setiap sisi xy dengan kedua titik ujungnya telah terlabeli, jumlah λ ( x ) + λ ( y ) selalu berbeda untuk setiap xy ∈ E yang berbeda. Maka

ketika

menentukan

λ ( vi )

terdapat

paling

banyak

( i − 1) + pred ( vi ) .mi bilangan bulat positif yang tidak dapat dipakai di mana pred(vi) adalah jumlah vj yang bertetangga dengan vi dengan j < i, dan mi adalah jumlah sisi v p vq ∈ E dengan p,q
lebih besar dari ∆ sedangkan mi ≤ m − deg ( vi ) = m − ∆ . Karenanya label terbesar paling tinggi Λ v adalah :

W

n + ∆ (m − ∆)

Berdasarkan Lemma 3.3.1 dan Teorema 3.3.2 di atas, kita dapat menyimpulkan Akibat 3.3.1 6 Algoritma Greedy Edge-Antimagic Vertex-Labeling dan Extend Pseudo

Edge-Antimagic Vertex-Labeling memberikan sebuah pelabelan pada graf G dengan n-titik dan m-sisi yang memiliki derajat terbesar ∆ dengan nilai magic number kurang

W

dari 3ΛV = 3 ( n + ∆ ( m − ∆ ) )

6

Wood 2006 [15]


KAJIAN DAN ALGORITMA PELABELAN PSEUDO EDGE-MAGIC. memiliki derajat maksimum dan tidak ada titik yang terisolasi. Jika n i adalah

Recommend Documents