nilai maksimum dan minimum pelabelan-g pada grafeprints.uns.ac.id/2795/1/101301009200908071.pdfii...

36
i NILAI MAKSIMUM DAN MINIMUM PELABELAN-g PADA GRAF POHON PISANG B n,k DAN PERSAHABATAN D 3 m oleh ENTYKA MAYHASTI ROSYIDA M0104028 SKRIPSI ditulis dan diajukan untuk memenuhi sebagian persyaratan memperoleh gelar Sarjana Sains Matematika FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SEBELAS MARET SURAKARTA 2009

Upload: trancong

Post on 01-Jul-2019

247 views

Category:

Documents


0 download

TRANSCRIPT

i

NILAI MAKSIMUM DAN MINIMUM PELABELAN-g PADA GRAF

POHON PISANG Bn,k DAN PERSAHABATAN D3m

oleh

ENTYKA MAYHASTI ROSYIDA

M0104028

SKRIPSI

ditulis dan diajukan untuk memenuhi sebagian persyaratan

memperoleh gelar Sarjana Sains Matematika

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SEBELAS MARET

SURAKARTA

2009

ii

SKRIPSI

NILAI MAKSIMUM DAN MINIMUM PELABELAN-g

PADA GRAF POHON PISANG Bn,k DAN PERSAHABATAN D3m

yang disiapkan dan disusun oleh

ENTYKA MAYHASTI ROSYIDA

M0104028

dibimbing oleh

Pembimbing I Pembimbing II

Dra. Mania Roswitha, M. Si. Dra. Yuliana Susanti, M. Si.

NIP. 19520628 198303 2 001 NIP. 19611219 198703 2 001

telah dipertahankan di depan Dewan Penguji

pada hari Senin, tanggal 27 Juli 2009

dan dinyatakan telah memenuhi syarat.

Anggota Tim Penguji Tanda Tangan

1. Dra. Diari Indriati, M. Si. 1.

NIP. 19610112 198811 2 001 ...................................

2. Drs. Tri Atmojo K, M. Sc., Ph. D. 2.

NIP. 19630826 198803 1 002 ...................................

3. Irwan Susanto, DEA. 3.

NIP. 19710511 199512 1 001 ...................................

Surakarta, 29 Juli 2009

Disahkan oleh

Fakutas Matematika dan Ilmu Pengetahuan Alam

Dekan, Ketua Jurusan Matematika,

Prof. Drs. Sutarno, M. Sc. Ph. D. Drs. Kartiko, M.Si.

NIP. 19600809 198612 1 001 NIP. 19500715 198601 1 001

iii

ABSTRAK

Entyka Mayhasti Rosyida, 2009. NILAI MAKSIMUM DAN MINIMUM PELABELAN-g PADA GRAF POHON PISANG Bn,k DAN PERSAHABATAN D3

m. Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sebelas Maret.

Suatu pelabelan-g graf G yang mempunyai order |V(G)| dan ukuran |E(G)| merupakan suatu fungsi satu-satu, f : V(G) → {0, 1, ..., |E(G)|}, yang menurunkan pelabelan f’ : E(G) → {1, 2, ..., |E(G)|} terhadap edge-edge G yang didefinisikan sebagai selisih dari label-label verteks pada kedua ujung edge, f’(e) = |f(u) – f(v)|, untuk setiap edge e = uv dari G. Setiap pelabelan-g graf G dengan order |V(G)| dan ukuran |E(G)|, menentukan suatu “nilai” yang dinotasikan dengan val(f) dan didefinisikan dengan val(f)=ΣeϵE(G)f’(e). Nilai maksimum dan minimum dari pelabelan-g graf G didefinisikan sebagai valmaks(G) = maks{val(f)} dan valmin(G) = min{val(f)}, dengan f adalah pelabelan-g graf G. Suatu pelabelan-g dari graf G disebut pelabelan maks-g jika val(f) = valmaks(G) dan pelabelan min-g jika val(f) = valmin(G).

Tujuan penulisan skripsi ini adalah menentukan nilai maksimum dan minimum pelabelan-g dari graf pohon pisang Bn,k dan persahabatan D3

m. Metode yang digunakan dalam penulisan skripsi ini adalah studi literatur.

Berdasarkan hasil pembahasan, diperoleh kesimpulan sebagai berikut : 1. nilai maksimum dan minimum pada graf pohon pisang Bn,k ,

2,( ) 3 2, 2maks n kval B k k n= - - =

dan 2

12 22 2

min , 2122

2,

4( )

22 , ,

4

k k

n kk

n nn n k n k genap

val Bn n

n k n k ganjil

æ ö æ ö+ç ÷ ç ÷

ç ÷ ç ÷ç ÷ ç ÷è ø è ø

æ ö+ç ÷ç ÷ç ÷è ø

ì é ù-+ + + =ï ê ú

ï ê ú= íé ù-ï + + =ê úïê úî

2. nilai maksimum dan minimum pada graf persahabatan D3m ,

22 13 2

( )m mmaksval D m

æ ö+ç ÷ç ÷è ø

= +

dan 1

min 3 2

1( ) 2 2 .

2mm m

val Dæ ö+ç ÷ç ÷è ø

+ê ú= + ê úë û

Kata Kunci : pelabelan-g, graf pohon pisang, graf persahabatan.

v

MOTO

Awal mula menuntut ilmu adalah diam,

kedua mendengarkan, ketiga paham dan hafal, dan keempat mengamalkannya

(Pepatah)

vi

PERSEMBAHAN

Karya ini ku persembahkan untuk

Ø Mama dan Papa tercinta

Ø Someone, thanks for all

Ø Sahabat-sahabatku

Ø All my family

vii

KATA PENGANTAR

Assalaamu’alaikum Wr. Wb.

Alhamdulillah, puji syukur penulis panjatkan kepada Allah SWT yang telah

melimpahkan rahmat serta hidayah-Nya sehingga skripsi ini dapat diselesaikan.

Sholawat dan salam semoga selalu tercurah kepada suri tauladan Rosulullah

Muhammad SAW, serta keluarga, sahabat, dan orang-orang yang istiqomah di

jalan-Nya.

Di dalam penulisan skripsi ini, penulis tidak lepas dari segala kesulitan dan

keterbatasan yang akhirnya dapat penulis atasi berkat bantuan dari beberapa

pihak. Oleh Karena itu, penulis mengucapkan terima kasih kepada

1. Dra. Mania Roswitha, M. Si. dan Dra. Yuliana Susanti, M. Si., sebagai

pembimbing I dan pembimbing II yang telah memberikan petunjuk

dalam penyusunan skripsi ini,

2. Drs. Tri Atmojo K, M. Sc., Ph. D., sebagai Pembimbing Akademis yang

telah memberikan bimbingan, masukan, dan dorongan semangat untuk

terus maju,

3. seluruh staf dosen dan karyawan, khususnya di jurusan matematika dan

umumnya di fakultas MIPA,

4. rekan-rekan Matematika angkatan 2004 FMIPA UNS, terimakasih atas

kekeluargaan kita,

5. semua pihak yang telah membantu penulis dalam menyusun skripsi ini.

Semoga Allah SWT membalas segala bantuan yang telah diberikan kepada

penulis. Semoga skripsi ini dapat bermanfaat bagi semua pihak yang

membutuhkan.

Surakarta, Juli 2009

Penulis

viii

DAFTAR ISI

JUDUL .......................................................................................................... i

PENGESAHAN ............................................................................................ ii

ABSTRAK .................................................................................................... iii

ABSTRACT .................................................................................................. iv

MOTO ........................................................................................................... v

PERSEMBAHAN ......................................................................................... vi

KATA PENGANTAR .................................................................................. vii

DAFTAR ISI ................................................................................................. viii

DAFTAR GAMBAR .................................................................................... x

DAFTAR NOTASI ....................................................................................... xi

BAB I PENDAHULUAN 1

1. 1. Latar Belakang Masalah ........................................................... 1

1. 2. Perumusan Masalah ................................................................. 2

1. 3. Batasan Masalah ...................................................................... 3

1. 4. Tujuan Penelitian ..................................................................... 3

1. 5. Manfaat Penelitian ................................................................... 3

BAB II LANDASAN TEORI 4

2. 1. Tinjauan Pustaka ...................................................................... 4

2. 2. Landasan Teori ......................................................................... 6

2. 2. 1. Pengertian Dasar Graf ................................................. 6

2. 2. 2. Pelabelan Graf ............................................................ 9

2. 3. Kerangka Pemikiran ................................................................. 10

BAB III METODE PENELITIAN 12

BAB IV PEMBAHASAN 13

4. 1. Pelabelan-g pada Graf Pohon Pisang knB , ................................ 13

ix

4. 2. Pelabelan-g pada Graf Persahabatan 3mD .................................. 20

BAB V PENUTUP 23

5. 1. Kesimpulan .............................................................................. 23

5. 2. Saran ......................................................................................... 23

DAFTAR PUSTAKA 24

x

DAFTAR GAMBAR

Gambar 2. 1 Pelabelan pada Path P5 ......................................................... 4

Gambar 2. 2 Graf G ................................................................................... 7

Gambar 2. 3 Lintasan ................................................................................. 7

Gambar 2. 4 Graf lingkaran ....................................................................... 8

Gambar 2. 5 Graf Pohon ............................................................................ 8

Gambar 2. 6 Graf Star ................................................................................ 8

Gambar 2. 7 Graf Pohon Pisang ................................................................ 9

Gambar 2. 8 Graf Persahabatan ................................................................. 9

Gambar 4. 1 Graf Pohon Pisang Berlabel .................................................. 13

Gambar 4. 2 Pelabelan Minimum pada Graf Pohon Pisang ...................... 15

Gambar 4. 3 Pelabelan pada Graf Persahabatan ........................................ 20

xi

DAFTAR NOTASI

G : Suatu graf

(V(G),E(G)) : Graf G dengan himpunan verteks V(G) dan himpunan edge E(G)

V(G) : Himpunan verteks berhingga yang tidak kosong dari graf G

E(G) : Himpunan edge dari pasangan berhingga yang tidak berurutan dari

V(G)

n(G) : Order / banyaknya verteks

e(G) : Ukuran / banyaknya edge

G(n,e) : Graf berorder n dan ukuran e

e(vi,vj) : edge e antara vi dan vj

Pn : Path berorder n

Sn : Graf Star dengan n verteks

Bn,k : Graf Pohon Pisang dengan n-star dan setiap star ada k-verteks

D3m : Graf Persahabatan dengan m-cycle C3

Cn : Lingkaran dengan n verteks

Kn : Graf lengkap dengan n verteks

F2,n : Graf firecracker dengan 2 graf star berorder n

Sm,n : Graf double star berorder m dan n

val(fn) : Nilai pelabelan ke-n

valmin : Nilai minimum pelabelan

valmaks : Nilai maksimum pelabelan

xii

BAB I

PENDAHULUAN

1. 1. Latar Belakang

Teori graf merupakan salah satu cabang matematika yang banyak berperan

dalam pengembangan matematika terapan dan telah mengalami perkembangan

sejak tahun 1920-an. Penerapan teori graf sangat membantu menyelesaikan

masalah dalam kehidupan nyata, banyaknya aplikasi dalam berbagai bidang antara

lain ilmu komputer, riset operasi, komunikasi, dan ilmu pengetahuan alam. Dalam

representasi dari graf, verteks menunjukkan nodes atau titik, sedangkan edge

menunjukkan garis yang menghubungkan dua verteks. Menurut Wallis (2001),

pelabelan suatu graf yang telah diperkenalkan Rosa (1967) adalah pemetaan yang

membawa elemen-elemen graf ke bilangan-bilangan bulat positif atau non-negatif.

Saat ini banyak permasalahan yang berkaitan dengan teori graf yang telah

dikaji, terutama pelabelan. Salah satunya teori graf memberikan solusi dalam

masalah penentuan nilai maksimum dan minimum dalam pelabelan-g yang

merupakan salah satu pokok bahasan mengenai pelabelan dalam teori graf.

Chartrand et al. (2005), mendefinisikan pelabelan-g dari graf G sebagai fungsi 1-1

f : V(G)®{0, 1, 2, ..., m} yang menurunkan sebuah pelabelan f’ : E(G)®{1, 2,

..., m} terhadap edge-edge pada G dan didefinisikan sebagai selisih dari label-

label verteks pada kedua ujung edge, f’(e) = |f(u) – f(v)|, untuk setiap edge e = uv

dari G.

Setiap pelabelan-g f dari graf G berorder n dan ukuran m menetapkan nilai

yang dinotasikan dengan val(f) dan didefinisikan dengan

( )( ) '( )

e E Gval f f e

Î=å .

Karena f adalah fungsi 1-1 dari V(G) ke {0, 1, 2, ..., m}, maka berlaku 1)(' ³ef

untuk setiap edge e pada graf G dan mfval ³)( .

Untuk graf G berorder n dan ukuran m, nilai maksimum dari pelabelan-g

graf G didefinisikan sebagai valmaks(G) = maks{val(f)} dengan f adalah sebuah

pelabelan-g dari G, dan nilai minimum dari pelabelan-g graf G didefinisikan

xiii

sebagai valmin(G) = min{val(f)} dimana f adalah sebuah pelabelan-g dari G.

Sebuah pelabelan-g g dari graf G adalah sebuah pelabelan maks-g jika val(g) =

valmaks(G) dan pelabelan-g h adalah sebuah pelabelan min-g jika val(h) =

valmin(G).

Penelitian mengenai pelabelan-g telah dilakukan oleh beberapa peneliti pada

kelas graf lain, seperti Chartrand et al. (2005) pada lintasan, lingkaran, dan graf

lengkap, Roswitha dan Indriati (2007) untuk graf n-sun, dan Indriati dkk. (2008)

pada graf firecracker dan double star. Pada skripsi ini, penulis tertarik untuk

mengembangkan penelitian tersebut dengan mencari pelabelan-g pada graf pohon

pisang Bn,k dan graf persahabatan D3m serta dicari pola pelabelan secara umum

untuk menentukan valmaks dan valmin dari kelas graf yang belum pernah dibahas

sebelumnya.

Selain graf tersebut belum diteliti, graf tersebut juga mempunyai karakter

unik. Misalnya graf pohon pisang yaitu graf yang menyerupai pohon pisang,

dimana pohon pisang bisa mempunyai beberapa batang pohon dalam satu akar.

Sedangkan graf persahabatan juga menyerupai keterkaitan dengan persahabatan

dalam dunia nyata, untuk orang pertama sebagai pusat graf mempunyai beberapa

sahabat dimana sahabatnya masih punya hubungan sahabat dengan salah satu

sahabat dari orang pertama.

1. 2. Perumusan Masalah

Berdasarkan latar belakang yang diuraikan di atas, maka masalah yang akan

dibahas pada penelitian ini adalah

1. bagaimana menentukan pelabelan-g pada graf pohon pisang Bn,k dan graf

persahabatan D3m,

2. bagaimana menentukan nilai maksimum dan minimum pelabelan-g dari

sebuah graf pohon pisang Bn,k dan graf persahabatan D3m.

xiv

1. 3. Batasan Masalah

Permasalahan dalam penelitian ini dibatasi oleh beberapa hal

1. pelabelan pada graf pohon pisang Bn,k untuk 2n ³ dan 4k ³ ,

2. pelabelan pada graf D3m untuk 2m ³ ,

1. 4. Tujuan Penelitian

Tujuan dari penelitian ini adalah menentukan pola pelabelan umum dan

membangun teorema dari pelabelan-g dengan mencari besarnya nilai maksimum

dan minimum pelabelan-g dari graf pohon pisang Bn,k dan graf persahabatan D3m.

1. 5. Manfaat Penelitian

Hasil dari penelitian ini diharapkan akan bermanfaat bagi peneliti dan

pembaca berkaitan dengan pelabelan-g pada graf pohon pisang Bn,k dan graf

persahabatan D3m. Manfaat dari penelitian ini adalah

1. menambah wawasan tentang teori graf khususnya tentang pelabelan,

2. mengetahui pola umum nilai maksimum dan minimum pelabelan-g dari

sebuah graf pohon pisang Bn,k dan graf persahabatan D3m.

xv

0 1 2 3 4

3 0 4 1 2

2 3 4 1 0

4 0 3 1 2

2 0 3 1 4

0 3 2 4 1

2 3 2 3 4 3 2 1

BAB II

LANDASAN TEORI

1. 6. Tinjauan Pustaka

Pelabelan menggunakan pelabelan-g telah dilakukan oleh beberapa peneliti,

dalam penelitian tersebut telah ditemukan pola pelabelan umum pada beberapa

kelas graf. Penelitian yang dilakukan Chartrand et al. (2005), pada Gambar 2. 1

enam pelabelan-g f1, f2, ..., f6 dari path P5, dimana label dari verteks ditunjukkan di

atas setiap verteks dan label dari edge ditunjukkan di bawah setiap edge.

f1 f2 f3

val(f1)=4 val(f2)=11 val(f3)=6

f4 f5 f6

val(f4)=10 val(f5)=10 val(f6)=9

Gambar 2. 1. Beberapa pelabelan-g dari path P5

Dari penelitian tersebut ditemukan val(f1) = 4 untuk pelabelan-g f1 dari P5

dimana f1 menunjukkan pelabelan min-g dari P5 dan val(f2) = 11 untuk pelabelan-g

f2 dari P5 dan f2 menunjukkan pelabelan maks-g dari P5.

Dalam penelitian Chartrand et al. (2005) tersebut, ditemukan juga pola

pelabelan umum untuk lintasan (path), lingkaran (cycle), dan graf lengkap

(complete graph). Nilai maksimum dan minimum pelabelan-g pada graf tersebut

adalah

6.1. Lingkaran

Didapat pola umum lingkaran dengan n ≥ 3

2)3)(1(

)(+-

=nn

Cval nmaks

1 1 1 1 3 4 3 1 1 1 3 1

3 1 2 3

xvi

)1(2)(min -= nCval n .

6.2. Graf lengkap

3 2

2 2

(3 5 6 4),

24( )( 1)(3 5 6)

, 24

maks n

n n n nn genap

val Kn n n

n ganjil

ì - + -ïï= í

- - +ïïî

min

1( ) , 3

3n

nval K n

+æ ö= ³ç ÷è ø

.

6.3. Lintasan

Didapat pola umum lintasan dengan n ≥ 2

úû

úêë

ê -=

22

)(2n

Pval nmaks

1)(min -= nPval n .

Selain penelitian yang dilakukan oleh Chartrand et al. (2005), Roswitha dan

Indriati (2007) melakukan penelitian pada graf n-sun untuk sebarang n, besarnya

nilai maksimum dan minimum dihitung dengan rumus

21( ) (5 2 ),

2maksval G n n n genap= + =

2min )1(2)( nnGval +-= .

Indriati dkk. (2008) melakukan penelitian pada graf firecracker F2,n dan graf

double star dengan hasil

a. graf firecracker F2,n

2,2 )1(

2)( -+÷÷

ø

öççè

æ= n

n

nFval nmaks

min 2,

1( )

2 2n

n nval F

æ ö +é ù= +ç ÷ ê úê úè ø,

xvii

b. graf double star

,

2( ) ( )( );

2maks m n

m nval S m n m n

+ +æ ö= + £ç ÷è ø

2

min ,2

3 3,2 2

2 22 2

( )3 3

, .2 22

2 2

m n

n nm m

n ganjil

val Sn n

mm n genap

ìæ ö æ ö+ +ê ú é ùé ù ê úïç ÷ ç ÷ê ú ê ú+ + + =ë û ê ú ê ú ê úïç ÷ ç ÷ ê ú ë ûç ÷ ç ÷ïïè ø è ø= í

æ ö æ ö+ +ê ú é ùïé ùç ÷ ç ÷ê ú ê úï + + + =ë û ê ú ê úç ÷ ç ÷ï ê úç ÷ ç ÷ïè ø è øî

1. 7. Landasan Teori

Bagian landasan teori memuat beberapa teori yang digunakan dalam

penelitian ini, antara lain pengertian dasar graf dan pelabelan graf.

2. 2. 1. Pengertian Dasar Graf

Ada beberapa pengertian dasar graf yang sering dipakai dalam penulisan

skripsi ini, ditunjukkan dengan definisi-definisi sebagai berikut

Definisi 2. 1 (Chartrand dan Lesniak, 1996)

Suatu graf G didefinisikan sebagai pasangan (V(G),E(G)) dengan V(G) adalah

himpunan verteks berhingga yang tidak kosong dan E(G) adalah himpunan

berhingga dari pasangan berhingga tidak berurutan (tidak harus beda) anggota-

anggota dari V(G), anggota dari E(G) disebut edge. Banyaknya verteks dalam

suatu graf G disebut order dari G, dinotasikan dengan n(G) dan banyaknya edge

dalam suatu graf G disebut ukuran dari G, dinotasikan dengan e(G). Suatu graf

yang dinotasikan dengan G(n,e) mempunyai order n dan ukuran e.

xviii

Definisi 2. 2 (Hartsfield dan Ringel, 1990)

Graf tak berarah (undirected graph) adalah graf yang edge-nya tidak mempunyai

arah. Edge e yang terhubung dengan pasangan tak berurutan verteks vi dan vj

ditulis e(vi,vj) atau e(vj,vi).

Gambar 2. 2 menunjukkan sebuah graf tidak berarah dengan himpunan titik V(G)

dan himpunan edge E(G), yaitu V(G) = {v1, v2, v3, v4} dan E(G) = {e1, e2, e3, e4,

e5} = {v1v2, v1v3, v1v4, v2v3, v3v4}. Dengan demikian, order graf G adalah n(G) = 4

dan ukuran graf G adalah e(G) = 5.

Gambar 2. 2 Graf G

Definisi 2. 3 (Gross and Yellen, 1999)

Lintasan merupakan sebuah pohon dimana dua verteksnya berdegree 1,

sedangkan n-2 verteks yang lain berdegree 2.

Contoh lintasan ditunjukkan pada Gambar 2.3

Gambar 2. 3 Litasan berorder 4

Definisi 2. 4 (Chartrand dan Oellermann, 1993)

Lingkaran merupakan lintasan yang panjangnya tidak sama dengan nol dan

verteks awal sama dengan verteks akhir.

Contoh lingkaran ditunjukkan oleh Gambar 2.4

v1 v2 v3 v4

v1 v2

v3 v4

e1

e2 e3 e4

e5

xix

Gambar 2. 4 Lingkaran dengan n = 3 dan n = 4

Definisi 2. 5 (Munir, 2006)

Pohon (Tree) adalah graf tak berarah terhubung yang tidak mengandung

lingkaran.

Contoh pohon berorder 6 ditunjukkan pada Gambar 2. 5

Gambar 2. 5 Pohon

Definisi 2. 6 (Harary, 1994; Pemmaraju dan Skiena, 2003; dan Tutte, 2005)

Graf star Sn atau dikenal dengan ”n-star” adalah pohon pada n verteks dengan

satu verteks mempunyai degree n-1 dan n-1 verteks yang lain mempunyai degree

1.

Contoh graf star Sn ditunjukkan pada Gambar 2. 6 dengan n = 6

Gambar 2. 6 Graf star S6

Definisi 2. 7 (Chen et al., 1997)

3v 2v

1v 2v

4v 3v

1v

a b

c

e

d

f

1v 6v

5v

4v

3v

2v

xx

Sebuah B(n,k) pohon pisang (Banana Tree) adalah sebuah graf yang diperoleh

dengan menghubungkan satu daun dari setiap n-copies pada sebuah k graf star

dengan satu verteks akar yang berbeda dari semua graf star.

Contoh graf pohon pisang Bn,k ditunjukkan pada Gambar 2. 7

Gambar 2. 7 Graf pohon pisang Bn,k

Definisi 2. 8 (Gallian, 2007)

Graf kincir angin Belanda D3m, sering disebut juga graf persahabatan

(Friendship), yaitu graf yang didapat dari gabungan graf lingkaran C3 sebanyak

m dengan satu verteks digunakan barsama.

Contoh graf persahabatan ditunjukkan Gambar 2.8

Gambar 2. 8 Graf persahabatan D3m

2. 2. 2. Pelabelan Graf

Menurut Wallis (2001), pelabelan suatu graf adalah pemetaan yang

membawa elemen-elemen graf ke bilangan-bilangan bulat positif atau non-negatif.

Definisi 2. 9 (Chartrand et al., 2005)

u1 u2

u3

u4

u2

u2m-1

u

1v 2v nv

11v 12v

13v

1( 1)kv -

21v 22v

23v

2( 1)kv - ( 1)n kv -

1nv 2nv

y

3nv

xxi

Untuk sebuah graf yang berorder n dan berukuran m, pelabelan-g graf G adalah

sebuah fungsi 1-1, f : V(G) ® {0, 1, 2, ..., m} yang menurunkan sebuah

pelabelan f’ : E(G) ® {1, 2, ..., m} terhadap edge-edge G yang didefinisikan

sebagai selisih dari label pada verteks-verteks pada kedua ujung edge, f’(e) =

|f(u) – f(v)|, untuk setiap edge e = (u, v) dari G.

Definisi 2. 10 (Chartrand et al., 2005)

Untuk sebuah graf yang berorder n dan berukuran m, ditentukan sebuah “nilai”

yang dinotasikan dengan val(f), yang didefinisikan sebagai val(f)=ΣeϵE(G)f’(e).

Dalam hal ini f adalah fungsi 1-1 dari V(G) ® {0, 1, 2, ..., m}.

Definisi 2. 11 (Chartrand et al., 2005)

Untuk sebuah graf G yang berorder n dan berukuran m ditentukan nilai

maksimum dari sebuah pelabelan-g dari graf G yang didefinisikan sebagai

valmaks(G) = maks{val(f)} dimana f adalah pelabelan-g graf G. Sedangkan nilai

minimum dari sebuah pelabelan-g dari graf G didefinisikan sebagai valmin(G) =

min{val(f)} dimana f adalah pelabelan-g graf G.

Definisi 2. 12 (Chartrand et al., 2005)

Sebuah pelabelan-g dari graf G disebut pelabelan maks-g jika val(f) = valmaks(G)

dan sebuah pelabelan-g dari graf G disebut pelabelan min-g jika val(f) =

valmin(G).

1. 8. Kerangka Pemikiran

Berdasarkan landasan teori di atas, dapat disusun suatu kerangka pemikiran

untuk menentukan nilai maksimum dan minimum pelabelan-g pada graf pohon

pisang Bn,k dan persahabatan D3m. Langkah pertama adalah memahami pengertian

dasar tentang graf pohon pisang Bn,k dan persahabatan D3m serta memahami cara

menggunakan pelabelan-g. Langkah kedua adalah pemberian label pada setiap

verteks dalam graf pohon pisang Bn,k dan persahabatan D3m sesuai dengan definisi

xxii

pelabelan-g graf G. Langkah berikutnya adalah menghitung f’ serta menentukan

pola pelabelan umum nilai maksimum dan minimum pelabelan-g untuk graf

pohon pisang Bn,k dan persahabatan D3m. Langkah terakhir adalah membuktikan

pola pelabelan umum nilai maksimum dan minimum yang telah didapat.

xxiii

BAB III

METODE PENELITIAN

Penelitian ini menggunakan metode studi literatur pada graf pohon pisang

Bn,k dan persahabatan D3m. Materi pendukung penelitian ini diambil dari referensi

buku-buku yang sudah ada dan penulis mengembangkan dari materi tersebut.

Definisi-definisi yang terdapat dalam buku-buku referensi dan jurnal-jurnal dikaji

ulang, kemudian digunakan dalam pembahasan permasalahan yang telah

dirumuskan.

Oleh karena itu, untuk mencapai tujuan penulisan diambil langkah-langkah

sebagai berikut :

8.1.1.1. menyajikan konsep dan pengertian tentang

pelabelan secara umum, khususnya pelabelan-g,

8.1.1.2. menerapkan pelabelan-g pada graf pohon pisang Bn,k

dan persahabatan D3m,

8.1.1.3. menentukan pola pelabelan umum nilai maksimum

dan minimum pelabelan-g,

8.1.1.4. membuktikan pola pelabelan umum nilai

maksimum dan minimum pelabelan-g yang telah didapatkan.

xxiv

BAB IV

PEMBAHASAN

Dalam bab ini dibahas mengenai pelabelan menggunakan pelabelan-g pada

pohon pisang Bn,k dan persahabatan D3m sehingga diperoleh rumus umum nilai

maksimum dan minimumnya, disertai dengan pembuktian setiap rumusan umum

yang telah diperoleh tersebut.

4. 1. Pelabelan-g pada Graf Pohon Pisang Bn,k

Graf pohon pisang Bn,k merupakan graf yang dikontruksikan dari graf star

dengan menghubungkan verteks y ke salah satu daun pada setiap graf star, dimana

y bukan bagian dari graf star. Setiap verteks pada graf pohon pisang diberi label

antara 0, 1, ..., nk. Contoh pelabelan pada graf pohon pisang ditunjukkan pada

Gambar 4.1.

Gambar 4.1 Graf pohon pisang berlabel

Gambar 4.1 (a) menunjukkan contoh pelabelan pada graf pohon pisang B2,6

dengan nilai 100 dan Gambar 4.1 (b) merupakan contoh pelabelan pada graf

pohon pisang B3,5 dengan nilai 36.

Teorema 4. 1 Untuk semua bilangan bulat 4k ³ dan 2n =

22,( ) 3 2maks kval B k k= - - .

6

12 0

1 5

4 3

2 7

11

10 9

8

(a)

2 6

0

1

5 4 3

7 11 10 9

8 12

13 14

15

(b)

xxv

Bukti :

Graf pohon pisang B2,k memiliki 2 buah graf star, misalkan pusat untuk graf

star adalah v dan u, dimana u1, u2, ..., uk-1 adalah verteks yang adjacent dengan u

dan v1, v2, ..., vk-1 adalah verteks yang adjacent dengan v, sedangkan akarnya

adalah y.

Jika f adalah pelabelan-g dari graf pohon pisang B2,k, maka graf pohon

pisang B2,k mempunyai pelabelan maks-g jika pusat u diberi label terkecil, pusat v

diberi label terbesar, sedangkan untuk akarnya y diberi label tengah. Didefinisikan

pelabelan maks-g pada B2,k sebagai berikut

0)( =uf , ( ) 2 ,f v k= … (4.1)

( ) 2 , 1, 2, ..., 1,if u k i i k= - = - … (4.2)

( ) , 1, 2, ..., 1,if v i i k= = - … (4.3)

( ) ,f y k= … (4.4)

Dari keempat persamaan di atas, yaitu Persamaan (4.1), (4.2), (4.3), dan

(4.4) serta mengacu pada Definisi 2.9 dan Definisi 2.10 maka diperoleh valmaks

dari graf pohon pisang Bn,k adalah

2, 1 1( ) ( ( )) ( ( )) ( ( )) ( ( ))

((2 1) 0 (2 2) 0 ... (2 ( 1)) 0) ((2 1) )

( 1) ((2 1) (2 2) ... (2 ( 1))

maks k i ival B val f uu val f yu val f v y val f vv

k k k k k k

k k k k k

= + + +

= - - + - - + + - - - + - -+ - + - + - + + - -

12

((2 1) (2 2) ... (2 ( 1)) ( 1) ( 1)

((2 1) (2 2) ... (2 ( 1)))

2(2 2 ... 2 ) 2(1 2 ... ( 1)) 2( 1)

2( 1)(2 ) 2 2( 1)k

k k k k k k

k k k k

k k k k k

k k k kæ ö-ç ÷è ø

= - + - + + - - + - + -+ - + - + + - -

= + + + - + + + - + -

= - - + -2 2 4 4 2 2k k k k k= - - + + -

23 2.k k= - -

Teorema terbukti. ■

Contoh pelabelan maksimum untuk graf pohon pisang ditunjukkan pada

Gambar 4.1 (a).

xxvi

Teorema 4. 2 Untuk semua bilangan bulat 4k ³ dan 2n ³ ,

2

min ,

2

1 2,2 2

42 2( )

12

2 , .242

n k

k kn n

n n k n k genap

val Bk

n nn k n k ganjil

ì æ ö æ ö+ é ù-ï ç ÷ ç ÷+ + + =ê úï ç ÷ ç ÷ç ÷ ç ÷ ê úï è ø è ø= í+æ öï é ù-ç ÷ï + + =ê úç ÷ï ç ÷ ê úè øî

Bukti :

Gambar 4.2 Pelabelan minimum pada graf pohon pisang

Gambar 4.2 (a) menunjukkan pelabelan minimum graf pohon pisang B2,4

untuk k genap dengan nilai 10, sedangkan Gambar 4.2 (b) untuk k ganjil,

pelabelan minimum pada graf pohon pisang B2,5 dengan nilai 14.

Graf pohon pisang Bn,k memiliki sebanyak n graf star, misalkan pusat pada

graf star adalah va, dengan a = 1, 2, ..., n, dimana va1, va2, ..., va(k-1) adalah verteks

yang adjacent dengan va, sedangkan akarnya adalah y.

Jika f adalah pelabelan-g dari graf pohon pisang Bn,k, maka graf pohon

pisang Bn,k mempunyai pelabelan min-g untuk k genap didefinisikan sebagai

berikut

( )2 1( ) , 1 ,

2a

a kf v a n

-= £ £ … (4.5)

10 6 2

3

4

5

0 7 8 1 2

1

1

1 1

1

1 2

(a) (b) 5

2

4

9

8 7

6

2 3 0

1

1

2 2

1 2 1

1 1

1

xxvii

( 1) , 12( )

( 1) 1, 1,2

ai

ka k i i

f vk

a k i i k

ì - + £ <ïï= íï - + + £ £ -ïî

untuk 2n

a ê ú£ ê úë û

… (4.6)

sedangkan 2n

a ê ú> ê úë û

... (4.7)

maka

/ 2 -1

1 1 1 ( / 2) 1

( ) ( ) - ( ) ( ) - ( )n k n k

a ai a aia i a i k

val f f v f v f v f v= = = = +

= +å å å å

( / 2)-1/2

1 1

(1 2 ... / 2) (1 2 ... (( /2) -1))

kk

i i

n i n i

n k n k= =

= +

= + + + + + + +

å å

1.2 2

2 2

k kn næ ö æ ö+ç ÷ ç ÷= +ç ÷ ç ÷ç ÷ ç ÷è ø è ø

… (4.8)

Sedangkan untuk k ganjil, pelabelannya adalah

… (4.9)

Untuk 2n

a ê ú£ ê úë û

... (4.10)

(2 -1) -1,

2 2( )

(2 -1) 1, ,

2 2

a

a k na

f va k n

a n

ì ê ú£ï ê úï ë û= í+ ê úï < £ê úï ë ûî

1( 1) 1, 1

2( )1

( 1) , 1,2

ai

ka k i i

f vk

a k i i k

-ì - + - £ £ïï= í +ï - + £ £ -ïî

( 1) 1, 12( )

( 1) , 1 1,2

ai

ka k i i

f vk

a k i i k

ì - + - £ £ïï= íï - + + £ £ -ïî

xxviii

dan 2n

a ê ú> ê úë û

… (4.11)

Oleh karena itu,

( -1) / 2/ 2 -1

1 1 ( 1) / 2

( -1) / 2 -1

/ 2 1 ( 1) / 2

( ) ( ) - ( ) ( ) - ( )

( ) - ( ) ( ) - ( )

kn k

a ai a aia i i k

kn k

a ai a aia n i i k

val f f v f v f v f v

f v f v f v f v

= = = +

= = = +

æ öç ÷= +ç ÷è ø

æ öç ÷+ +ç ÷è ø

å å å

å å å

( 1) / 2 ( 1) / 2 ( 1) / 2 ( 1) / 2

1 1 1 1

( 1) / 2

1

2 2

2

2 (1 2 ... ( 1) / 2)

k k k k

i i i i

k

i

n ni i i i

n i

n k

- - - -

= = = =

-

=

æ ö æ öç ÷ ç ÷= + + +ç ÷ ç ÷è ø è øæ öç ÷=ç ÷è ø

= + + + -

å å å å

å

12 .2

2

kn

+æ öç ÷= ç ÷ç ÷è ø

… (4.12)

Jika verteks star yang adjacent dengan akar y adalah vc dengan c = 1, 2, ..., n,

maka untuk n genap didefinisikan sebagai berikut

… (4.13)

… (4.14)

1, 12( )

( 1) 1, 1 ,2

c

nck c

f vn

c k c n

ì - £ £ïï= íï - + + £ £ïî

( ) ,2nk

f y =

1( 1) , 1

2( )1

( 1) 1, 1 .2

ai

ka k i i

f vk

a k i i k

-ì - + £ £ïï= í +ï - + + £ £ -ïî

xxix

jadi

1/ 2

1 ( / 2) 1

/ 2

1 ( / 2) 1

/ 2

1 ( / 2) 1

( ) ( ) - ( )

( ) - ( ) ( ) - ( )

( ) - ( ) ( ) - ( )2 2

- -1 ( -1) 1 -2 2 2 2

n

ccn n

c cc c n

n n

c cc c n

n n

c c n

val f f y f v

f y f v f v f y

n nf y f v f v f y

n nk n nkck c k

=

= = +

= = +

= = +

=

= +

æ öç ÷= +ç ÷è ø

æ öç ÷= + +ç ÷è ø

å

å å

å å

å å

/ 2 / 22

1 1 ( / 2) 1 ( / 2) 1

2 2

2

- 1 ( -1) 1 -4 2 2

- 2 ... 1 ... ( -1) -4 2 2 2 2 2 4

-4 4 2 4 2

n n n n

c c c n c n

n k n nkck c k

n k nk n nk nk n n kk k n k

n k n nk n nkk

= = = + = +

æ öç ÷= + + +ç ÷è ø

æ öæ öæ ö æ ö= + + + + + + + + + +ç ÷ç ÷ç ÷ ç ÷è ø è øè øè ø

æ ö= + +ç ÷è ø

å å å å

2

2 2

2

( -1) -4

- - -8 4 4 8

2 -

4 4

n kn k n

n k nk nk n kn

n k nkn

æ öæ ö+ +ç ÷ç ÷è øè ø

= + +

= +

( )2 2.

4

n n kn

-= + … (4.15)

Sedangkan untuk n ganjil, didefinisikan sebagai berikut

… (4.16)

( 1)

( ) ,2

n kf y

-= … (4.17)

11, 1

2( )1

( 1) 1, ,2

c

nc k c

f vn

c k c n

-ì - £ £ïï= í +ï - + £ £ïî

xxx

kemudian diperoleh

( 1) / 2

1 1 ( 1) / 2

( ) ( ) - ( ) ( ) - ( ) ( ) - ( )nn n

c c cc c c n

val f f y f v f y f v f v f y-

= = = +

= = +å å å

( 1) / 2

1 ( 1) / 2

( 1) / 2

1 ( 1) / 2

( 1) / 2 ( 1) / 22

1 1

1 1 ( ) - ( ) ( ) - ( )

2 2

1 ( 1) 1 ( 1) - -1 ( -1) 1 -

2 2 2 2

( 1) - 1 (

4

n n

c cc c n

n n

c c n

n n

c c

n nf y f v f v f y

n n k n n kck c k

n kck

-

= = +

-

= = +

- -

= =

æ ö- +ç ÷= + ç ÷ç ÷è ø

æ ö- - + -ç ÷= + +ç ÷ç ÷è ø

-= + +

å å

å å

å å( 1) / 2 ( 1) / 2

2

2

1 ( 1)-1) 1 -

2 2

( 1) ( 1) 1 - 2 ...

4 2 2

( 1) ( 1) 1 ( 1)( 1) 1 ... ( -1) -

2 2 2 4

( 1) 1 -

4

n n

c n c n

n n kc k

n k n k nk k

n k n k n n n kn k

n k n

= + = +

æ ö + -ç ÷+ç ÷ç ÷è ø

- - -æ ö= + + + +ç ÷è ø

æ öæ - - ö + + -æ ö+ + + + + +ç ÷ç ÷ç ÷è øè øè ø

- -=

å å

2 2

2 2

( 1) 1 ( 1) ( 1)( 1)( -1) -

4 2 4 2 4

( 1) ( 1) ( 1) -

8 4 8

( 1) (2 2 1) -

8 8

n k n n k n n kk n k n

n k n k n kn

n k n n kn

- æ + - ö + -æ ö æ ö+ + + +ç ÷ç ÷ ç ÷è ø è øè ø

- - -= + +

- - - += +

( )2 2 1.

4

n n kn

- += + … (4.18)

Dari Persamaan (4.15) dan (4.18) untuk sebarang n diperoleh

2 2

( ) .4

n nval f k n

é ù-= +ê ú

ê ú … (4.19)

Untuk k genap, menggunakan (4.8) dan (4.19), diperoleh

21 22 2min , 42 2

( ) ,k k

n nn kval B n n k n

æ ö æ ö é ù+ -ç ÷ ç ÷ ê úç ÷ ç ÷ ê úç ÷ ç ÷ ê úè ø è ø

= + + +

sedangkan untuk k ganjil, menggunakan (4.12) dan (4.19) diperoleh

212min ,2

2( ) 2 .

4

k

n kn n

val B n k næ ö+ç ÷ç ÷ç ÷è ø

é ù-= + +ê ú

ê úê ú

Jadi teorema terbukti. ■

xxxi

4. 2. Pelabelan-g pada Graf Persahabatan D3m

Graf persahabatan merupakan graf yang dikonstruksikan dari lingkaran yang

panjangnya sama. Pelabelan dilakukan dengan memperhatikan label tiap verteks

harus berbeda, contoh pelabelannya pada Gambar 4.3

Gambar 4.3 Pelabelan pada graf persahabatan

Pelabelan graf persahabatan dibatasi pada lingkaran C3 dengan m ≥ 2, pada

Gambar 4.3 (a) merupakan pelabelan graf persahabatan D34 dengan jumlah

nilainya 24, sedangkan Gambar 4.3 (b) menunjukkan palabelan graf persahabatan

D33 dengan nilai 16, dan Gambar 4.3 (c) adalah pelabelan pada graf persahabatan

D35 yang bernilai 80.

Teorema 4. 3 Untuk semua bilangan bulat 2m ³

23

2 1( ) .

2m

maks

mval D m

+æ ö= +ç ÷è ø

Bukti :

Suatu graf persahabatan D3m mempunyai graf lingkaran sebanyak m dimana

setiap graf lingkaran berorder 3. Misalkan pusat-nya adalah u dan verteks yang

adjacent dengan u adalah ui, dimana i = 1, 2, ..., 2m.

Jika f adalah pelabelan-g dari graf persahabatan D3m maka graf persahabatan

mempunyai pelabelan maks-g. Jika pusatnya u diberi label 0, didefinisikan

pelabelan maks-g pada D3m adalah sebagai berikut

0 1

2

3

5 6

8

7

4

(a)

6

5

4 2

0

1

3

(b)

2

7

3 8

9 4

0

(c)

5

10

1 6

xxxii

0)( =uf , … (4.20)

… (4.21)

Mengacu pada Definisi 2.9 dan Definisi 2.10, maka dengan persamaan

(4.20) dan (4.21) diperoleh valmaks graf persahabatan D3m sebagai berikut

3( ) ( ( )) ( ( ))mmaks i i genap i ganjilval D val f uu val f u u= == +

(1 0 2 0 ... 0) ( 1 0 2 0 ... 2 0)m m m m= - + - + + - + + - + + - + + -

( 1 1 2 2 ... 2 )m m m m+ + - + + - + + -

(1 2 ... ) (( 1) ( 2) ... 2 ) ( ... )m m m m m m m= + + + + + + + + + + + + +

(1 2 ... ( 1) ( 2) ... 2 ) .m m m m m m= + + + + + + + + + +

22 1

2

m mæ ö+ç ÷ç ÷è ø

= + .

Terbukti. ■

Contoh pelabelan maksimum pada graf persahabatan ditunjukkan pada

Gambar 4.3 (c).

Teorema 4. 4 Untuk semua bilangan bulat 2m ³

min 3

1 1( ) 2 2 .

2 2m m m

val D+æ ö +ê ú= +ç ÷ ê úë ûè ø

Bukti :

Suatu graf persahabatan D3m mempunyai graf lingkaran sebanyak m dan

setiap graf lingkaran terdiri dari 3 verteks. Misalkan pusat-nya adalah u dan

verteks yang adjacent dengan u adalah ui dengan i = 1, 2, ..., 2m.

Jika f adalah pelabelan-g dari graf persahabatan D3m maka graf persahabatan

mempunyai pelabelan min-g. Jika pusatnya u diberi label tengah. Pelabelan min-g

pada D3m dapat adalah sebagai berikut

( ) , 1, 2, ..., ,

, 1, 2, ..., 2 , ,i

l l m i ganjilf u

n n m m m i genap

= =ì= í = + + =î

xxxiii

( )f u m= , … (4.22)

… (4.23)

Pada persamaan (4.22) dan (4.23) yang mengacu pada Definisi 2.9 dan

Definisi 2.10, untuk m genap maka diperoleh valmin graf persahabatan D3m adalah

min 3 1( ) ( ( )) ( ( ))

( 0 1 ... ( 1)) ( 1 2 ... 2 )

(1 0 3 2 ... ( 2) ( 3)) ( 1 ) ( 3 ( 2)

5 ( 4) ..

mi i ival D val f uu val f u u

m m m m m m m m m m

m m m m m m

m m

-= += - + - + + - - + + - + + - + + -+ - + - + + - - - + + - + + - ++ + - + + . 2 (2 1))

( ( 1) ... 1) (1 2 ... ) (1 1 ... 1) (1 1 ... 1)

2(1 2 ... ) (1 1 ... 1)

m m

m m m

m

+ - -= + - + + + + + + + + + + + + + += + + + + + + +

12 .

2

mm

+æ ö= +ç ÷

è ø … (4.24)

Sedangkan untuk m ganjil

min 3 1 1 1( ) ( ( )) ( ( )) ( ( )) ( ( ))

( 0 1 ... ( 1)) ( 1 2 ... 2 )

(1 0 3 2 ... ( 2) ( 3)) ( 1 ( 1))

mi l l l m n m n nval D val f uu val f u u val f u u val f u u

m m m m m m m m m m

m m m m

- = = + -= + + += - + - + + - - + + - + + - + + -+ - + - + + - - - + + - -

(( 3) ( 2) ... 2 (2 1))

( ( 1) ... 1) (1 2 ... ) (1 1 ... 1) (2 1 ... 1)

2(1 2 ... ) (1 1 ... 1)

m m m m

m m m

m

+ + - + + + - -= + - + + + + + + + + + + + + + += + + + + + + +

12 1.

2

mm

+æ ö= + +ç ÷

è ø … (4.25)

Dari dua pembuktian (4.24) dan (4.25) di atas didapat,

min 3

1 1( ) 2 2 .

2 2m m m

val D+æ ö +ê ú= +ç ÷ ê úë ûè ø

Teorema terbukti. ■

Contoh untuk pelabelan minimum graf persahabatan dapat dilihat pada

Gambar 4.3 (a) untuk m ganjil, sedangkan 4.3 (b) untuk m genap.

1, 1, 2, ..., ( )

, 1, 2, ..., 2 ,i

l l mf u

n n m m m

- =ì= í = + +î

xxxiv

BAB V

PENUTUP

5. 1. Kesimpulan

Berdasarkan uraian pembahasan, maka dapat disimpulkan

1. nilai maksimum dan minimum pelabelan-g pada graf pohon pisang Bn,k

dengan 4k ³ adalah

22,( ) 3 2, 2maks kval B k k n= - - =

dan

21 22 2

42 2min ,

21 22

42

,

( )

2 , .

k kn n

n kk

n n

n n k n k genap

val B

n k n k ganjil

æ ö æ ö é ù+ -ç ÷ ç ÷ ê úç ÷ ç ÷ ê úç ÷ ç ÷ ê úè ø è ø

æ ö é ù+ -ç ÷ ê úç ÷ ê úç ÷ ê úè ø

ì+ + + =ï

ï= íï

+ + =ïî

2. nilai maksimum dan minimum pelabelan-g pada graf persahabatan D3m

adalah

23

2 1( )

2m

maks

mval D m

+æ ö= +ç ÷è ø

dan

min 3

1 1( ) 2 2 .

2 2m m m

val D+æ ö +ê ú= +ç ÷ ê úë ûè ø

5. 2. Saran

Penelitian mengenai pelabelan-g masih dapat dikembangkan lagi. Oleh

karena itu, bagi pembaca yang tertarik dengan topik ini dapat mengembangkan

pelabelan-g untuk graf pohon pisang untuk nilai maksimum pada sebarang n, atau

kelas-kelas graf yang lain.

xxxv

DAFTAR PUSTAKA

Chartrand, G.; Erwin, D.; VanderJagt, D. W.; and Zhang, P. (2005). g-labeling of

Graphs. Western Michigan University

Chartrand, G. and Lesniak, L. (1996). Graphs and Digraphs, 3rd edition. Chapman

and Hall, London.

Chartrand, G. and Oellermann, O. R. (1993). Applied and Algorithmic Graphs

Theory. McGraw-Hill International, London.

Chen, W. C.; Lü, H. I.; and Yeh, Y. N. (1997). "Operations of Interlaced Trees

and Graceful Trees" Southeast Asian Bull. Math.

Gallian, J. A. (2007). “Dynamic Survey DS6: Graph Labeling.” Electronic J.

Combinatorics, DS6, 1-58.

Gross, J. T. and Yellen, J. (1999). Graphs Theory and Its Application. Boca

Raton, FL : CRC Press.

Harary, F. (1994). Graph Theory. Reading, MA: Addison-Wesley.

Hartsfield, N and G. Ringel,. (1990). Pearls in graph Theory : A Comprehensive

Introduction. Academic Press, Inc., San Diego.

Indriati, D.; M. Roswitha,; and I. Slamet,. (2008). Aplikasi g-labeling pada Graf

Forest dan Firecracker sebagai Alternative Model Distribusi Minyak Goreng.

Penelitian DIPA 2008, FMIPA UNS.

Munir, R. (2006). Diktat Kuliah IF2153 Matematika Diskrit. Program Studi

Teknik Informatika, Institut Teknologi Bandung.

Pemmaraju, S. and S. Skiena,. (2003). "Cycles, Stars, and Wheels."

Computational Discrete Mathematics: Combinatorics and Graph Theory in

Mathematica. Cambridge, England: Cambridge University Press.

Rosa, A. (1967). On certain valuations of the vertices of a graph, in Theory of

Graphs. Gordon and Breach, New York.

Roswitha, M. and D. Indriati,. (2007). g-labeling pada Graf n-sun. Penelitian

DIPA 2007, FMIPA UNS.

Tutte, W. T. (2005). Graph Theory. Cambridge, England: Cambridge University

Press.

xxxvi

Wallis, W.D. (2001). Magic Graphs. Birkhauser. Boston.