PELABELAN PADA GRAF STAR, FIRECRACKER, DAN BANANA TREE BERDASARKAN KONDISI JARAK
Penulis Utama
:
ADI PRAKOSO
NIM / NIP
:
M0104013
×ABSTRAK
Adi Prakoso, 2009. PELABELAN PADA GRAF STAR, FIRECRACKER, DAN
BANANA TREE BERDASARKAN KONDISI JARAK. Fakultas Matematika dan Ilmu
Pengetahuan Alam. Universitas Sebelas Maret.
Masalah pengiriman paket pesan dalam jaringan radio dapat diformulasikan
dalam pelabelan graf berdasarkan pada jarak yang dinotasikan L(d1,d2). Untuk (d1,d2)
bilangan bulat non negatif, pelabelan graf adalah pemetaan yang membawa elemen–
elemen graf ke bilangan bulat non negatif. Menurut Jin dan Yeh [3], L(d1,d2)-labelling
graf G, adalah suatu fungsi f : V(G) →{ 0, 1, 2, . . . } sedemikian sehingga
| f(u) – f(v)| ≥ di, dimana , ( ) u v V G Œ dan jarak antara u dan v adalah i dalam graf G,
untuk i = 1, 2. Bilangan L(d1,d2) dalam G, )(
21 ,
G dd l adalah bilangan k terkecil
sedemikian sehingga terdapat sebuah label L(d1,d2) dengan k adalah label terbesar.
Dari hasil pembahasan, diperoleh kesimpulan bahwa
1 2 ,
( ) d d G l dengan
1 2 ( , ) {(0,1), (1,1), (1, 2)} d d Πuntuk graf star, firecracker, dan banana tree masing-
masing adalah sebagai berikut
1. ( 2)( 1,0 - = nSn l , 1)( 1,1 -=nSn l , 42)( 2,1 -= nSn l ), n ≥ 4.
2. ( 2)( )4,(1,0 = n F l , 3)( )4,(1,1 = n F l , 5)( )4,(2,1 = n F l ), n ≥ 2.
3.
Ó
Ì
Ï
³-
=
=
4,1
32,2
)( )4,(1,0
nn
dann
B n l ,
Ó
Ì
Ï
³
=
=
4,
32,3
)( )4,(1,1
nn
dann
B n l ,
Ó
Ì
Ï
³-
=
=
4,22
32,4
)( )4,(2,1
nn
dann
B n l .
Kata kunci: pelabelan graf, L(d1, d2), star, firecracker, banana tree.
×
Penulis Utama
:
ADI PRAKOSO
Penulis Tambahan
:
-
NIM / NIP
:
M0104013
Tahun
:
2009
Judul
:
PELABELAN PADA GRAF STAR, FIRECRACKER, DAN BANANA TREE BERDASARKAN KONDISI JARAK
