KAJIAN DAN ALGORITMA PELABELAN PSEUDO VERTEX-MAGIC. m m n 2. Misalkan ada pelabelan pseudo vertex-magic untuk sebuah graf G dengan n-titik dan

BAB IV KAJIAN DAN ALGORITMA PELABELAN PSEUDO VERTEX-MAGIC

IV.1 Batas Bawah Magic Number pada Pelabelan Total Pseudo

Edge-Magic Teorema 4.1.11 Nilai magic number terkecil dalam pelabelan pseudo vertex-magic sebuah graf G dengan n-titik dan m-sisi adalah :

m 1 ( m + 1) + m + ( n + 1) n 2 Bukti : Misalkan ada pelabelan pseudo vertex-magic untuk sebuah graf G dengan n-titik dan m-sisi, dengan nilai magic number κ, maka untuk setiap titik v ∈ V

κ = λ (v ) +

∑

vx∈ E ( v )

⎛

λ ( vx ) , sehingga κ .n = ∑ ⎜⎜ λ ( v ) + v∈V

sisi terkait dengan dua buah titik, maka

⎝

∑ ∑

v∈V vx∈ E ( v )

⎛

κ .n = ∑ ⎜⎜ λ ( v ) + v∈V

1

⎝

∑

vx∈ E ( v )

⎞

λ ( vx ) ⎟⎟ = 2 ⎠

∑

∑

vw∈ E ( v )

⎞

vx∈ E ( v )

λ ( vx ) = 2

berlaku

λ ( vx ) ⎟⎟ . Karena setiap

∑

⎠

vw∈ E ( v )

λ ( vw ) sehingga :

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

Wood 2006 [9]

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

Bab IV Pelabelan Pseudo Vertex-Magic Persamaan tersebut akan minimal bila setiap sisi diberikan label yang kecil dan setiap titik diberikan label yang besar. Karena semua label adalah bilangan bulat positif, maka : m

n

i =1

j =1

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

κ .n ≥ 2 ∑ i + ∑ ( m + 1) = 2 ⎜

Dengan membagi kedua ruas dengan n, maka didapat :

⎛m

⎞

⎛

⎞

1

κ ≥ ⎜ ( m + 1) ⎟ + ⎜ m + ( n + 1) ⎟ 2 ⎝ n ⎠ ⎝ ⎠ Akibat 4.1.1 2 Nilai magic number minimal untuk pelabelan pseudo vertex-magic

untuk sebuah graf ∆-reguler dengan n-titik dan m-sisi adalah :

1 ⎛1 ⎞ ∆ + 1 m + (n + 1 + ∆ ) ⎜ ⎟ 2 ⎝2 ⎠ Bukti : Misalkan ada pelabelan pseudo vertex-magic untuk sebuah graf ∆-reguler dengan n-titik dan m-sisi serta memiliki nilai magic number κ. Menurut Teorema 4.1.1, maka : ⎛m

⎞

⎛

⎞

1

κ ≥ ⎜ ( m + 1) ⎟ + ⎜ m + ( n + 1) ⎟ 2 ⎝ n ⎠ ⎝ ⎠ Karena graf adalah merupakan ∆-regular, maka m = ⎛ 1 n∆ ⎜ κ ≥ ⎜ 2 ⎜ n ⎝

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

(n

1 ⎞ + 1)⎟ = ∆ 2 ⎠

(m

1 .n.∆ sehingga : 2

1 ⎛ + 1)+ ⎜ m + 2 ⎝

(n

⎞ + 1)⎟ ⎠

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

2

Wood 2006 [9]

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

Bab IV Pelabelan Pseudo Vertex-Magic

IV.3 Algoritma Pelabelan Total Pseudo Edge-Magic Algoritma yang digunakan untuk melakukan pelabelan pseudo vertex-magic ini terbagi menjadi empat tahap. Tahap pertama adalah mencari Spanning Tree dari graf G=(V,E) yang diberikan. Tahap kedua adalah melakukan pelabelan sisi dengan menggunakan Pseudo Vertex-Antimagic Tree Edge-Labeling. Kemudian setelah semua sisi dalam Tree selesai dilabeli, pelabelan dilanjutkan dengan melabeli sisi-sisi yang belum dilabeli dari graf G=(V,E) dengan menggunakan algoritma Pseudo Vertex-Antimagic Edge-Labeling. Tahap terakhir setelah semua sisi dalam graf dilabeli adalah melabeli titikdengan menggunakan algoritma Extend Pseudo Vertex-Antimagic Edge-Labeling.

IV.2.1 Algoritma Mencari Spanning Tree

Langkah pertama dalam melakukan pelabelan pseudo vertex-magic adalah dengan mencari sebuah spanning tree dari graf G yang diberikan. Kita dapat mencari sebuah spanning tree dengan menggunakan algoritma berikut :

Masukan

: Graf G=(V,E) dengan n-titik dan m-sisi

Keluaran

: Spanning Tree T=(V,E’) dengan E ' ⊆ E

Langkah-langkah : 1. Memilih satu titik sebagai titik awal dari Spanning Tree 32 Pelabelan Pseudo Edge-Magic dan Pseudo Vertex-Magic pada Graf Sembarang


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

Semua titik yang berjarak 1 dari titik berjarak i dari titik awal dan belum termuat dalam Spanning Tree beserta sisi yang menghubungkan kedua titik tersebut dimasukkan ke dalam Spanning Tree

Di akhir iterasi ini kita akan mendapatkan sebuah spanning tree dari graf G yang diberikan untuk selanjutnya kita gunakan dalam pelabelan.

IV.2.2 Algoritma Pseudo Vertex-Antimagic Tree Edge-Labeling

Langkah kedua dalam melakukan pelabelan pseudo vertex-magic ini adalah pelakukan pelabelan sisi pseudo vertex-antimagic pada spanning tree yang kita dapatkan dari algoritma di atas dengan menggunakan algoritma Pseudo Vertex-Antimagic Edge-Labeling di bawah ini :

Masukan

: Spanning Tree T=(V,E’) dengan

Keluaran

: Pelabelan titik vertex-antimagic pada spanning tree

Langkah-langkah : 1.

Ambil sebuah titik r ∈ V berderajat lebih dari 1 sebagai root

2.

Untuk i = 1,2,...,n-1 33

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

Bab IV Pelabelan Pseudo Vertex-Magic ¾

Untuk setiap sisi vw ∈ E ' dengan v sebagai titik awal (parent) dan jarak w ke r adalah i : 9

Dengan S v =

Ambil label λ ( vw ) sebagai suabu bilangan bulat positif L sehingga :

Untuk semua sisi xy ∈ E yang telah terlabeli, L ≠ λ ( xy )

Untuk semua titik x ∈ V \ {v , w} , L ≠ S x − S v dan L ≠ S x

∑ λ ( vx )

vx∈V

Setelah algoritma ini berakhir, akan didapatkan pelabelan sisi pseudo vertex-magic pada spanning tree yang akan kita gunakan dalam algoritma selanjutnya untuk melabeli sisi-sisi yang belum terlabeli dari algoritma ini.

IV.2.3 Algoritma Pseudo Vertex-Antimagic Edge-Labeling

Setelah mendapatkan pelabelan sisi pada spanning tree, maka kita lakukan pelabelan pada sisi-sisi yang tersisa, yaitu pada sisi vw ∈ E \ E ' dengan menggunakan algoritma seperti di bawah ini :

Masukan

: Pseudo Vertex-Antimagic Tree Edge-Labeling pada Graf G

Keluaran

: Pelabelan sisi vertex-antimagic pada graf G=(V,E)

Langkah-langkah : 34 Pelabelan Pseudo Edge-Magic dan Pseudo Vertex-Magic pada Graf Sembarang


1.

Untuk setiap sisi vw ∈ E \ E ' , labeli λ ( vw ) sebagai bilangan bulat positif terkecil L sedemikian sehingga : ¾

Untuk semua sisi xy ∈ E , L ≠ λ ( xy )

¾

Untuk setiap titik x ∈ V \ {v , w} , L ≠ S x − S v dan L ≠ S x − S w

Pada akhir algoritma ini akan didapatkan pelabelan sisi pada graf yang diberikan, yang kita butuhkan untuk mendapatkan pelabelan total pseudo vertex-magic.

IV.2.4 Algoritma Extend Pseudo Vertex-Antimagic Edge-Labeling

Langkah terakhir dalam proses pelabelan total pseudo vertex-magic adalah pelabelan titik pada graf G=(V,E) dengan menggunakan pelabelan sisi yang telah kita dapatkan. Algoritma yang digunakan untuk melakukan pelabelan titik ini adalah seperti di bawah ini :

Masukan

: Greedy Vertex-Antimagic Edge-Labeling dari graf G=(V,E)

Keluaran

: Pelabelan total pseudo vertex-antimagic pada graf G=(V,E)

Langkah-langkah : 1.

Ambil nilai Λ E sebagai nilai label sisi λ ( vw ) yang terbesar dari semua vw ∈ E



2. 3.

Ambil nilai ΛV sebagai jumlah label SV =

∑ λ ( vx )

yang terbesar

vx∈E

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

4.

Untuk setiap sisi v ∈ V nilai dari label λ ( v ) = κ − SV = κ − ∑ λ ( vx ) vx∈E

Setelah iterasi berakhir, kita akan mendapatkan sebuah pelabelan total pseudo vertex-magic untuk graf G.

IV.2.5 Contoh Algoritma Pelabelan Total Pseudo Vertex-Magic

v1

x

1

2 v2

v3

Gambar 4.1 Mencari Spanning Tree

r

y

Gambar 4.2 Pelabelan Spanning Tree

x

5

1

3

1

2 r

3

2 y

Gambar 4.3 Pelabelan Sisi

6

4

Gambar 4.4 Pelabelan Total dengan κ = 8



IV.3 Batas Atas Magic Number pada Pelabelan Total Pseudo Vertex-Magic Lemma 4.3.13 Jika λ adalah sebuah pelabelan pseudo vertex-magic, ambil ΛE adalah

label terbesar dari λ(vw) untuk setiap vw ∈ E dan ΛV adalah jumlah label terbesar dari

∑ λ ( vx )

untuk setiap v ∈ V , maka nilai maksimum magic number dari

vx∈V

pelabelan λ adalah

( ∆ + 1) Λ E

Bukti :

Seperti pada pembuktian Lemma 3.3.1 pastilah Λ E + 1 adalah label terkecil yang belum digunakan dan karena Λ V adalah jumlah label sisi terbesar yang terkait suatu titik, maka pastilah Λ V + Λ E + 1 adalah suatu magic number yang cukup besar sehingga ada κ ≤ Λ E + Λ V + 1 . Ambil sebuah titik v ∈ V

∑ λ ( vx ) = Λ

vx∈V

Jika

V

derajat

yang memenuhi

. titik

v

adalah

1,

maka

Λ E = ΛV

dan

κ ≤ Λ E + Λ V + 1 = 2 Λ E + 1 ≤ 3 Λ E ≤ ( ∆ + 1) Λ E , karena untuk mendapatkan pelabelan pseudo vertex-magic jumlah titik dalam graf haruslah lebih dari 2 sehingga derajat tertinggi dalam graf G tersebut pastilah lebih dari 2 ( ∆ ≥ 2 ). Jika derajat titik v lebih dari 1, maka jumlah n buah sisi yang terkait dengan titik v pastilah

3

lebih

kecil

dari

jumlah

n

buah

label

terbesar

sehingga

Wood 2006 [7]



ΛV = Sv ≤

deg ( v )

∑ (Λ i =1

E

− i + 1) ≤ ∆Λ E − 1 . Selanjutnya kita substitusikan dan kita

dapatkan κ ≤ Λ E + Λ V + 1 ≤ ( ∆Λ E − 1 ) + Λ E + 1 = ( ∆ + 1 ) Λ E

Lemma 4.3.24 Algoritma Pseudo Vertex-Antimagic Tree Edge-Labeling memberikan

sebuah pseudo vertex-antimagic edge-labeling dari sebuah Tree T dengan label kurang dari 3n-5 Bukti : Sebuah Tree yang memiliki lebih dari satu sisi (berorde lebih dari 1) memiliki sebuah titik r dengan derajat lebih dari satu.misalkan sisi rx dan ry adalah sisi-sisi yang pertama dilabeli berdasarkan algoritma tersebut. Maka λ ( rx ) = 1, λ ( ry ) = 2 , dan

S r = 2 + 1 = 3, S x = 1, S y = 2 sedang semua titik v ∈ V sisanya memiliki Sv = 0 Akan dibuktikan bahwa untuk semua titik v, w ∈ V yang berbeda, jika Sv = S w maka pastilah Sv = 0 = S w Perhatikan iterasi yang terjadi dalam pemilihan label L untuk sisi vw.karena pelabelan berjalan dari titik v sebagai parent dari titik w, maka semua sisi yang terkait dengan titik w juga belum dilabeli, dan S w = 0 dan Sv > 0 . Nilai Sv akan berubah menjadi Sv ' = Sv + L sedangkan nilai S w akan berubah menjadi S w ' = S w + L dan S x tidak

4

Wood 2006 [13]



berubah untuk titik yang lain. Karena Sv ≠ 0 , maka Sv ' = Sv + L ≠ L = S w ' dan S w ' = L ≠ S x demikian seterusnya iterasi berlangsung sampai semua sisi dalam Tree telah selesai terlabeli. Pada akhir iterasi ini, akan didapat nilai Sv ≠ S w untuk semua v, w ∈ V yang berbeda.Untuk setiap edge vw, paling banyak terdapat (m-1)+2(n-2) = 3n-6 menurut Teorema 2.1, maka m = n-1, sehingga (m-1)+2(n-2) = (n-2)+2(n-2) = 3n-6 label yang tidak dapat digunakan. Karenanya, label terbesar adalah 3n-5.

Dari Lemma 4.3.1 dan Lemma 4.3.2 dapat ditarik kesimpulan : Akibat 4.3.15 Algoritma Greedy Vertex-Antimagic Edge-Labeling dan Extend Pseudo

Vertex-Antimagic Edge-Labeling memberikan sebuah pelabelan pada graf Tree dengan n-titik yang memiliki derajat terbesar ∆ dengan nilai magic number kurang dari ( ∆ + 1)( 3n − 5 )

Teorema 4.3.16 Jika λ adalah pelabelan pseudo vertex-magic pada sebuah graf G

dengan n-titik dan m-sisi, maka nilai terbesar magic numbernya menurut algoritma Greedy Vertex-Antimagic Vertex-Labeling adalah m+2n-4. Bukti :

5

Wood 2006 [14]

6

Wood 2006 [15]



Setelah mendapatkan partial edge-labeling dari algoritma Pseudo Vertex-Antimagic Tree Edge-Labeling, untuk semua titik v, w ∈ V yang berbeda, Sv ≠ S w . Misalkan pada saat pelabelan sisi yang belum terlabeli, kita melabeli suatu sisi vw dengan label L, maka nilai Sv ' = Sv + L dan nilai S w ' = S w + L sedangkan nilai S x tidak berubah untuk titik x yang lain. Dengan memilih nilai L tertentu, sehingga untuk setiap titik

x ∈ V , x ≠ v, x ≠ w , Sv ' = Sv + L ≠ S x dan S w ' = S w + L ≠ S x , maka λ akan tetap merupakan pelabelan anti-magic sampai akhir iterasi. Menurut Lemma 4.3.2, label maksimum hasil pelabelan Tree adalah 3n-5. Maka untuk setiap sisi vw ∈ E \ E ' terdapat ( m − 1) + 2 ( n − 2 ) = m + 2n − 5 kemungkinan label yang tidak dapat dipakai. Karena G terhubung, maka nilai m+2n-5 akan selalu tidak kurang dari 3n-5, sehingga label maksimum untuk sebuah graf terhubung sembarang adalah m+2n-5.

Dari Lemma 4.3.1 dan Teorema 4.3.1 kita mendapat hasil : Akibat 4.3.27 Algoritma Greedy Pseudo Vertex-Antimagic Edge-Labeling dan Extend

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

W

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

7

Wood 2006 [16]


KAJIAN DAN ALGORITMA PELABELAN PSEUDO VERTEX-MAGIC. m m n 2. Misalkan ada pelabelan pseudo vertex-magic untuk sebuah graf G dengan n-titik dan

Recommend Documents