abstrak pelabelan total tak teratur total

PELABELAN TOTAL TAK TERATUR TOTAL

PADA GRAF HASIL KALI COMB

ANTARA GRAF LINGKARAN DAN GRAF LINTASAN

SKRIPSI

Oleh

Jaka Permana

1210701032

JURUSAN MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS ISLAM NEGERI SUNAN GUNUNG DJATI

BANDUNG

2014




SKRIPSI

Disusun sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains di

Jurusan Matematika

Oleh

Jaka Permana

1210701032

JURUSAN MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS ISLAM NEGERI SUNAN GUNUNG DJATI

BANDUNG

2014

i

LEMBAR PERSETUJUAN




SKRIPSI

Oleh:

Jaka PermanaNIM. 1210701032

Menyetujui,

Pembimbing I

Rismawati Ramdani, M.Si.

NIP. 198605182009122004

Pembimbing II

Siti Julaeha, M.Si.

NIP. 198301202006042002

Mengetahui,

Dekan Fakultas Sains dan Teknologi

Dr. H. Opik Taupik Kurahman, M.AgNIP. 196812141996031001

Ketua Jurusan Matematika

Dr. Elis Ratna Wulan, S.Si., MTNIP. 197301122000032001

ii

LEMBAR PENGESAHAN

Skripsi yang berjudul Pelabelan Total Tak Teratur Total pada Graf Hasil Kali

Comb Antara Graf Lingkaran dan Graf Lintasan dinyatakan sah dan telah

disidangkan dalam sidang munaqosyah Jurusan Matematika Fakultas Sains dan

Teknologi UIN Sunan Gunung Djati Bandung pada tanggal 24 Agustus 2014 oleh

Majelis Sidang yang terdiri dari:

Ketua Majelis

Rismawati Ramdani, M.Si.

NIP. 198605182009122004

Sekretaris

Siti Julaeha, M.Si.

NIP. 198301202006042002

Mengetahui,

Penguji I

Dr. Arief Fatchul Huda, S.Si.,M.KomNIP. 197206091999031003

Penguji II

Esih Sukaesih, M.SiNIP.

iii

LEMBAR PERNYATAAN

Yang bertanda tangan dibawah ini :

Nama

NIM

Judul Skripsi

: Jaka Permana

: 1210701032

: Pelabelan Total Tak Teratur Total pada Graf Hasil Kali

Comb antara Graf Lingkaran dan Graf Lintasan

menyatakan bahwa skripsi ini benar-benar merupakan hasil karya sendiri dan

bukan duplikasi ataupun plagiasi (jiplakan) dari hasil penelitian orang lain.

Sepengetahuan saya, topik/ judul Skripsi ini belum pernah ditulis oleh orang lain.

Apabila kemudian hari terbukti atau dapat dibuktikan skripsi ini hasil duplikasi

atau plagiasi dari hasil penelitian orang lain, maka saya bersedia menerima sanksi

akademik dan sanksi hukum yang berlaku.

Bandung, Agustus 2014

Yang Menyatakan,

JAKA PERMANA

NIM. 1210701032

iv

ABSTRAK

Nama

Jurusan

Judul

: Jaka Permana

: Matematika

: Pelabelan Total Tak Teratur Total Pada Graf Hasil Kali

Comb Antara Graf Lingkaran dan Graf Lintasan

Suatu pelabelan total f :V ∪U → {1 ,2 ,…,k } disebut pelabelan-k total tak teratur total pada graf G jika setiap dua titik yang berbeda x dan y di V (G) memenuhi wt (x)≠ wt ( y ) dan setiap dua sisi yang berbeda x1 x2 dan y1 y2 di E(G) memenuhi wt (x1 x2)≠ wt ( y1 y2), dengan wt ( x )=f ( x )+∑ f (xz ) dan wt ( x1 x2 )=f ( x1 )+ f ( x1 x2 )+ f (x2). Nilai minimum k sehingga G memiliki pelabelan-k total tak teratur total dinamakan nilai total ketakteraturan total (total irregularity strength) dari G dan dinotasikan dengan ts(G). Pada skripsi ini akan ditentukan nilai ts(G) untuk G graf hasil kali comb antara graf lingkaran Cn dan graf lintasan P3 yang dinotasikan dengan Cn⊳P3.

Kata Kunci : pelabelan total tak teratur total, nilai total ketakteraturan total,

graf

lingkaran, graf lintasan, hasil kali comb

v

ABSTRACT

Name

Departement

Title

: Jaka Permana

: Mathematics

: A Totally Irregular Total Labelling of Comb Product

Between Cycles and Path

A total labelling f :V ∪U → {1 ,2 ,…,k } is called totally irregular total k-labelling of G if every two distinct vertices x and y in V (G) satisfywt (x)≠ wt ( y ), and every two distinct edges x1 x2 and y1 y2 in E(G) satisfiywt (x1 x2)≠ wt ( y1 y2), where wt ( x )=f ( x )+∑ f (xz ) and wt ( x1 x2 )=f ( x1 )+ f ( x1 x2 )+ f (x2). The minimum k for which a graph Ghas totally irregular total k-labelling is called the total irregularity strengthofG,and denotedbyts(G). In this final project is determined ts(G) for Gcomb product between cyclesCn and paths P3, denoted by Cn⊳P3.

Keyword : totally irregular total labelling, total irregularity strength, cycle,

path, comb product.

vi

KATA PENGANTAR

Bismillaahirrahmaanirrahiim.

Alhamdulillaahirabbil’alamin. Puji dan syukur penulis panjatkan kehadirat

Allah SWT yang senantiasa memberikan rahmat dan kasih sayang-Nya yang tak

terbatas sehingga penulis dapat menyelesaikan skripsi yang berjudul “Pelabelan

Total Tak Teratur Total pada Graf Hasil Kali Comb antara Graf Lingkaran

dan Graf Lintasan” ini dengan baik. Shalawat serta salam senantiasa tercurah

limpah untuk Nabi Muhammad SAW, beserta keluarga, sahabat, dan umatnya.

Dalam proses penyusunan hingga terselesaikannya skripsi ini, penulis telah

banyak mendapatkan do’a, bimbingan, serta kebaikan dari berbagai pihak.

Dengan ini, penulis menyampaikan rasa terima kasih yang tulus dan sebesar-

besarnya kepada:

1. Bapak Dr. H. Opik Taupik Kurahman, M.Ag selaku Dekan Fakultas Sains dan

Teknologi.

2. Ibu Dr. Elis RatnaWulan, S.Si.,MT, selaku Ketua Jurusan Matematika

3. Ibu Rismawati Ramdani, M.Si., selaku Dosen Pembimbing I, dan Ibu Siti

Julaeha, M.Si., selaku Dosen Pembimbing II yang telah memberikan

bimbingan dan arahan selama penyusunan skripsi ini.

4. Staf pengajar di Fakultas Sains dan Teknologi, khususnya dosen dan staf di

Jurusan Matematika, yang telah banyak membantu dan membagi ilmunya

kepada penulis.

5. Kedua orang tua serta keluarga, yang dengan do’anya yang terus mengalir,

dukungan, bimbingan, serta kasih sayangnya, senantiasa menjadi motivasi

terbesar bagi penulis.

6. Sahabat-sahabat terbaik, serta rekan seperjuangan yang senantiasa

membangkitkan semangat dan motivasi penulis.

vii

7. Keluarga besar Matematika Sains: teman-teman angkatan 2010, teman-teman

pengurus HIMATIKA Sains periode 2012-2013, kakak-kakak angkatan 2006-

2009, serta teman-teman angkatan 2011 dan 2012.

8. Pihak-pihak lain yang namanya tidak dapat disebutkan satu persatu, dengan

segala kebaikannya.

Semoga segala amal baik semua pihak yang telah membantu dan

mendukung dalam penyelesaian tugas akhir ini dapat diterima dan dibalas oleh

Allah SWT.

Kritik dan saran untuk perbaikan skripsi ini sangat penulis harapkan.

Semoga skripsi ini dapat bermanfaat bagi pembaca umumnya dan bagi penulis

sendiri khususnya.

Bandung, Agustus 2014

Penulis,

viii

DAFTAR ISI

HALAMAN JUDUL ....................................................... i

LEMBAR PERSETUJUAN .............................................. ii

LEMBAR PENGESAHAN............................................... iii

LEMBAR PERNYATAAN............................................... iv

ABSTRAK................................................................... v

ABSTRACT................................................................. vi

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

DAFTAR ISI................................................................ ix

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

BAB I PENDAHULUAN ................................................ 1

1.1............................................................................................Lata

rBelakang............................................................................ 1

1.2............................................................................................Rum

usanMasalah....................................................................... 2

1.3............................................................................................Bata

sanMasalah......................................................................... 2

1.4............................................................................................Tuju

an& ManfaatPenelitian........................................................ 2

1.5............................................................................................Met

odePenelitian...................................................................... 2

1.6............................................................................................Sist

ematikaPenulisan................................................................ 3

BAB II LANDASAN TEORI ............................................ 5

2.1 ...........................................................................................Das

ar-dasar Teori Graf ............................................................. 5

2.2 ...........................................................................................Jeni

s-jenis Graf ......................................................................... 9

ix

2.3 ...........................................................................................Ope

rasi-operasi dalam Graf....................................................... 10

2.4 ...........................................................................................Pela

belan Graf .......................................................................... 12

BAB III PELABELAN TOTAL TAK TERATUR TOTAL PADA

GRAF HASIL KALI COMB ANTARA GRAF LINGKARAN DAN

GRAF LINTASAN ................................................................... 16

BAB IV PENUTUP

4.1 ...........................................................................................Kesi

mpulan................................................................................ 41

4.2 ...........................................................................................Sara

n.......................................................................................... 41

DAFTAR PUSTAKA ................................................................ 42

RIWAYAT HIDUP

x

DAFTAR GAMBAR

Gambar 2.1.1 Graf G1............................................................... 6

Gambar 2.1.2 Graf G2 dan G3................................................... 7

Gambar 2.1.3 Graf G4............................................................... 8

Gambar 2.1.4 Titik Pendan dan Sisi Pendan ........................... 9

Gambar 2.2.1 Graf Lintasan P6................................................ 9

Gambar 2.2.2 Graf Lingkaran C3 dan C4.................................. 9

Gambar 2.2.3 Graf Pohon ....................................................... 10

Gambar 2.2.4 Graf Lengkap K4 dan K5.................................... 10

Gambar 2.3.1 Graf C4 dan P3.................................................... 10

Gambar 2.3.2 Graf C4 □ P3......................................................... 11

Gambar 2.3.3 Graf C4⊙P3........................................................ 11

Gambar 2.3.4 Graf C4⊳P3........................................................ 12

Gambar 3.1 Graf Cn⊳P3 untuk n ganjil .................................... 16

Gambar 3.2 Graf Cn⊳P3 untuk n genap .................................. 17

Gambar 3.3 Pelabelan Total Tak Teratur Total pada Graf C12⊳P3

38

Gambar 3.4 Bobot Semua Titik pada Graf C12⊳P3.................... 39

Gambar 3.5 Bobot Semua Sisi pada Graf C12⊳P3..................... 39


40


40

xi

BAB I

PENDAHULUAN

1.1. LatarBelakang

Teori graf merupakan salah satu cabang ilmu pengetahuan di bidang

matematika. Teori graf pertama kali diperkenalkan pada tahun 1736 oleh seorang

matematikawan terkenal dari Swiss yang bernama Euler. Teori graf dapat

menggambarkan suatu interaksi antar objek, dimana setiap objek tersebut akan

direpresentasikan dengan sebuah titik (vertex) dan hubungan antar objek tersebut

direpresentasikan dengan sisi (edge).

Teori graf banyak digunakan sebagai alat bantu untuk menggambarkan

atau menyatakan suatu permasalahan agar lebih mudah untuk dimengerti,

dipahami, dan diselesaikan. Banyak permasalahan yang dapat diselesaikan dengan

menggunakan teori graf, diantaranya adalah masalah penentuan rute dan

pewarnaan pada peta.

MisalkanG=(V , E) adalah suatu graf dengan himpunan titik V dan

himpunan sisi E. Pelabelan pada graf G adalah pemetaan yang membawa elemen-

elemen grafG ke nilai-nilai (biasanya bilangan bulat positif atau tak negatif) [6].

Berdasarkan domainnya, pelabelan dibagi menjadi tiga, yaitu pelabelan titik,

pelabelan sisi, dan pelabelan total. Pelabelan titik adalah suatu pelabelan dimana

domainnya adalah himpunan titik, pelabelan sisi merupakan suatu pelabelan

dimana domainnya adalah himpunan sisi, sedangkan pelabelan total yaitu suatu

pelabelan dimana domainnya adalah gabungan dari himpunan titik dan sisi pada

graf.

Seiring perkembangan zaman, kajian terhadap pelabelan mengalami

perkembangan yang pesat. Pada tahun 2007, Martin Baca dkk [6]

memperkenalkan pelabelan total tak teratur, yang mempunyai dua jenis yaitu

pelabelan total tak teratur titik dan pelabelan total tak teratur sisi.

1

Suatu pelabelan total f :V ∪U → {1 ,2 ,…,k }disebut pelabelan-k total tak

teratur titik jika untuk setiap dua buah titik yang berbeda u , v di G, wt (u)≠ wt (v ),

dimana wt (u )dan wt (v) berturut-turut adalah bobot dari titik u dan v. Bobot dari

suatu titik u di G didefinisikan sebagai wt (u )=λ (u )+ ∑uv∈E

λ(uv ). Nilai minimum k

sehingga G memiliki pelabelan-k total tal teratur titik dinamakan nilai total

ketakteraturan titik dari G, dinotasikan dengan tvs(G).

Suatu pelabelan total f :V ∪U → {1 ,2 ,…,k } disebut pelabelan-k total tak

teratur sisi jika untuk setiap dua buah sisi yang berbeda e , f di G, wt (e)≠ wt ( f ),

dimana wt ( e ) dan wt (f ) berturut-turut adalah bobot dari sisi e dan f . Bobot dari

suatu sisi e=(uv) di G didefinisikan sebagai wt ( e )= λ (u )+λ (uv )+λ ( v ). Nilai

minimum k sehingga G memiliki pelabelan-k total tal teratur sisi dinamakan nilai

total ketakteraturan sisi dari G, dinotasikan dengan tes(G).

C.C. Marzuki, A.N.M. Salman, dan M. Miller mengkombinasikan ide dari

pelabelan total tak teratur titik dan pelabelan total tak teratur sisi ke dalam sebuah

pelabelan baru yang disebut pelabelan total tak teratur total.

Suatu pelabelan totalf :V ∪E → {1, 2 ,⋯ ,k } disebut pelabelan-k total tak

teratur total dari G jika setiap dua titik x dan yyang berbeda di V (G) memenuhi

ωt (x )≠ ωt ( y ) dan setiap dua sisi x1 x2 dan y1 y2 yang berbeda di E(G) memenuhi

ωt (x1 x2)≠ ωt ( y1 y2), dimana ωt ( x )=f ( x )+∑ f (xz ) dan

ωt ( x1 x2 )=f ( x1)+ f ( x1 x2 )+ f (x2). Nilai minimum k sehingga G memiliki

pelabelan-k total tak teratur total disebut nilai total ketakteraturan total dari G,

yang dinotasikan dengan ts(G). [1]

Pada skripsi ini, akan ditentukan pelabelan total tak teratur total pada graf

hasil kali comb antara graf lingkaran Cn dan graf lintasan P3 yang dinotasikan

dengan Cn⊳P3. Oleh karena itu, pada skripsi ini penulis mengangkat judul

“PELABELAN TOTAL TAK TERATUR TOTAL PADA GRAF HASIL

KALI COMB ANTARA GRAF LINGKARAN DAN GRAF LINTASAN”.

2

1.2. RumusanMasalah

Berdasarkan judul dan latar belakang di atas dapat dirumuskan bahwa

permasalahan yang diangkat dalam skripsi ini adalah menentukan nilai

ketakteraturan total (ts) dari graf hasil kali comb antara graf lingkaran Cn dan graf

lintasan P3 yang dinotasikan dengan Cn⊳P3.

1.3. BatasanMasalah

Dalam pembahasan penyusunan skripsi ini masalah dibatasi pada

pencarian nilai ketakteraturan total pada graf hasil kali comb antara graf lingkaran

Cn dan graf lintasan P3, yang dinotasikan dengan ts(Cn⊳x2P3), dengan n ≥ 3.

1.4. TujuandanManfaatPenelitian

Tujuan dari skripsi ini adalah sebagai berikut :

1. Menentukan batas bawah dan batas atas nilai ketakteraturan total (ts)

dari graf hasil kali comb antara graf lingkaran Cndan graf lintasan P3,

Cn⊳x2P3.

2. Menentukan algoritma pelabelan-k total tak teratur total pada graf hasil

kali comb antara graf lingkaran Cndan graf lintasan P3.

Adapun manfaat dari skripsi ini secara umum yaitu hasil penelitian ini

dapat bermanfaat untuk memperluas wawasan mengenai pelabelan total tak teratur

total, serta dapat menjadi referensi tambahan bagi matematikawan yang tertarik

dalam bidang teori graf ataupun bidang matematika lain yang terkait.

1.5. Metode Penelitian

Metode yang digunakan dalam penyusunan skripsi ini adalah:

1. Studi Literatur dan Pemahaman

Pada tahapan ini penulis mengumpulkan dan memahami materi-

materi yang terkait dengan penelitian.

2. Penelitian

Beberapa hal yang dilakukan pada tahap ini adalah sebagai berikut:

3

a. Menentukan batas bawah ts(G) untuk Ggrafhasil kali comb antara graf

lingkaran Cndan graf lintasan P3 dengan memanfaatkan teorema-

teorema yang telah dikaji sebelumnya.

b. Menentukan batas atas ts(G) untuk Ggrafhasil kali comb antara graf

lingkaranCndan graf lintasan P3 dengan membentuk pelabelan total tak

teratur total pada G.

c. Menentukan nilai ts(G) untuk Ggraf hasil kali comb antara graf

lingkaran Cndan graf lintasan P3.

1.6. SistematikaPenulisan

Sistematika penulisan dalam skripsi ini dibagi menjadi empat bab, yaitu

sebagai berikut:

BAB I PENDAHULUAN

Bab ini berisi tentang latar belakang, rumusan masalah,

batasan masalah, tujuan dan manfaat penelitian, metodologi

penelitian, dan sistematika penulisan skripsi ini.

BAB II LANDASAN TEORI

Bab ini berisi teori-teori dasar yang melandasi pembahasan

dalam skripsi ini.

BAB III PELABELAN TOTAL TAK TERATUR TOTAL PADA

GRAF HASIL KALI COMB ANTARA GRAF

LINGKARAN DAN GRAF LINTASAN

Bab iniberisi tentang hasil utamadari skripsi ini, yaitu

pelabelan total tak teratur total pada graf hasil kali comb

antara graf lingkaran dan graf lintasan.

BAB IV PENUTUP

Bab ini berisi simpulan sebagai jawaban dari rumusan

masalah yang telah dipaparkan, sertasaran untuk penelitian

selanjutnya sebagai pengembangan dari topik skripsi ini.

4

abstrak pelabelan total tak teratur total

Documents