BATAS ATAS UNTUK SCRAMBLING INDEX DARI GRAF PRIMITIF

BATAS ATAS UNTUK SCRAMBLING INDEX DARI GRAF PRIMITIF

TESIS

Oleh SILVIA HARLENI 127021010/MT

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2014

Universitas Sumatera Utara


TESIS

Diajukan Sebagai Salah Satu Syarat Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara

Oleh SILVIA HARLENI 127021010/MT

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2014


Judul Tesis

: BATAS ATAS UNTUK SCRAMBLING INDEX DARI GRAF PRIMITIF Nama Mahasiswa : Silvia Harleni Nomor Pokok : 127021010 Program Studi : Magister Matematika

Menyetujui, Komisi Pembimbing

(Prof. Dr. Saib Suwilo, M.Sc) Ketua

(Dr. Mardiningsih, M.Si) Anggota

Ketua Program Studi

Dekan

(Prof. Dr. Herman Mawengkang)

(Dr. Sutarman, M.Sc)

Tanggal lulus: 5 Juni 2014


Telah diuji pada Tanggal 5 Juni 2014

PANITIA PENGUJI TESIS Ketua

:

Anggota :

Prof. Dr. Saib Suwilo, M.Sc 1. Dr. Mardiningsih, M.Si 2. Prof. Dr. Tulus, M.Si 3. Prof. Dr. Opim Salim S, M.Sc


PERNYATAAN


TESIS

Saya mengakui bahwa tesis ini adalah hasil karya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing dituliskan sumbernya.

Medan, 5 Juni 2014 Penulis, Silvia Harleni

i


ABSTRAK Scrambling index dari graf primitif G, k(G), adalah bilangan bulat positif terkecil k, sehingga untuk setiap pasangan titik u, v terdapat titik w sedemikian sehingga terk k dapat jalan u ←→ w dan v ←→ w. Untuk graf primitif G dengan n titik dan cycle ganjil terkecil Cs sepanjang s diketahui bahwa k(G) ≤ (s−1)/2+(n−s). Andaikan d{v, Cs } merupakan jarak dari titik v ke cycle Cs , maka maxv∈V d{v, Cs } ≤ n − s. Tulisan ini memperlihatkan bahwa k(G) ≤ (s − 1)/2 + maxv∈V d{v, Cs }. Tulisan ini juga membahas family dari graf primitif yang scrambling indexnya merupakan (s − 1)/2 + maxv∈V d{v, Cs }.

Kata kunci: Batas atas, Graf primitif, Scrambling index

ii


ABSTRACT The scrambling index of a primitive graph G, k(G), is the least positive integer k such that for each pair of distinct vertices u and v there is a vertex w with k k the property that there are u ←→ w and v ←→ w walk. For a primitive graph G with n vertices and smallest odd cycle of length s it is known that k(G) ≤ (s − 1)/2 + (n − s). Let d{v, Cs } be the distance of the vertex v to the cycle Cs , so maxv∈V d{v, Cs } ≤ n− s. This paper show that k(G) ≤ (s − 1)/2+ maxv∈V d{v, Cs }. This paper also discuss family of primitive graphs whose scrambling index are (s − 1)/2 + maxv∈V d{v, Cs }.

Keyword: Upper bound, Primitive graph, Scrambling index

iii


KATA PENGANTAR Puji dan syukur penulis panjatkan kehadirat Allah SWT Tuhan Yang Maha Kuasa yang telah memberikan berkah serta kesempatan sehingga penulis dapat menyelesaikan tesis yang berjudul ”Batas Atas Untuk Scrambling Index Dari Graf Primitif”. Tesis ini merupakan salah satu syarat untuk menyelesaikan studi pada Program Studi Magister Matematika Fakultas MIPA Universitas Sumatera Utara. Penulis menyadari bahwa dari awal hingga selesainya penulisan tesis ini, penulis banyak mendapat dukungan dari berbagai pihak, maka pada kesempatan ini penulis mengucapkan terima kasih yang sebesar-besarnya kepada: Prof. Dr. dr. Syahril Pasaribu, DTM&H, M.Sc(CTM), Sp.A(K) selaku Rektor Universitas Sumatera Utara Dr. Sutarman, M.Sc selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA) Universitas Sumatera Utara. Prof. Dr. Herman Mawengkang selaku Ketua Program Studi Magister Matematika FMIPA USU yang telah banyak memberikan bantuan dalam penulisan tesis ini. Prof. Dr. Saib Suwilo, M.Sc selaku Sekretaris Program Studi Magister Matematika FMIPA USU dan selaku Pembimbing Utama yang telah banyak memberikan bimbingan dan arahan serta motivasi kepada penulis dalam penulisan tesis ini. Dr. Mardiningsih, M.Si selaku Pembimbing Kedua yang juga telah banyak memberikan bimbingan dan arahan kepada penulis dalam penulisan tesis ini. Prof. Dr. Tulus, M.Si dan Prof. Dr. Opim Salim S, M.Sc selaku pembanding yang banyak memberikan masukan dan saran untuk kesempurnaan tesis ini. Seluruh Staf Pengajar pada Program Studi Magister Matematika FMIPA USU yang telah banyak memberikan ilmu pengetahuan selama masa perkuliahan. Kak Misiani, S.Si selaku Staf Administrasi Program Studi Magister Matematika FMIPA USU yang telah banyak memberikan pelayanan yang baik kepada penulis selama mengikuti perkuliahan. iv


Seluruh rekan-rekan Mahasiswa Program Studi Magister Matematika FMIPA USU tahun 2012 ganjil yang telah memberikan bantuan moril dan dorongan kepada penulis dalam penulisan tesis ini. Tak lupa penulis mengucapkan terima kasih yang sebesar-besarnya kepada ibunda tercinta Hj. Halimah Hanum, S.Pd dan ayahanda Drs. H. Pahmi Efendi, M.Pd serta saudari penulis yang penulis sayangi Sofia Harlena Nasution, S.Pd, Dewi Harni Nasution, dan Aninda Aminah Nasution yang telah memberikan dorongan dan doa dalam menyelesaikan tesis ini. Akhirnya penulis mengucapkan terima kasih kepada sahabat-sahabat serta rekan-rekan lainnya yang tidak dapat disebutkan satu-persatu. Semoga Allah SWT memberikan balasan atas jasa-jasa yang telah diberikan kepada penulis. Penulis menyadari bahwa tesis ini masih banyak kekurangan, untuk itu penulis mengharapkan kritik saran untuk penyempurnaan tesis ini. Semoga tesis ini dapat bermanfaat bagi pembaca dan pihak-pihak lain yang memerlukannya. Terimakasih.

Medan, 5 Juni 2014 Penulis, Silvia Harleni

v


RIWAYAT HIDUP Silvia Harleni dilahirkan di Aek Mual pada tanggal 26 Agustus 1989 dari pasangan Bapak Drs. H. Pahmi Efendi, M.Pd & Ibu Hj. Halimah Hanum, S.Pd. Tamat dari pendidikan Sekolah Dasar Negeri 142594 Sipolu-polu, Mandailing Natal pada tahun 2002. Sekolah Menengah Pertama Negeri 2 Panyabungan, Mandailing Natal pada tahun 2005. Sekolah Menengah Atas (SMA) Negeri 1 Panyabungan, Mandailing Natal tahun 2008. Tahun 2008 memasuki Perguruan Tinggi Universitas Sumatera Utara (USU) fakultas MIPA jurusan Matematika pada Strata Satu (SI) dan lulus tahun 2012. Pada tahun 2012, penulis melanjutkan pendidikan pada Program Studi Magister Matematika Universitas Sumatera Utara.

vi


DAFTAR ISI Halaman PERNYATAAN

i

ABSTRAK

ii

ABSTRACT

iii

KATA PENGANTAR

iv

RIWAYAT HIDUP

vi

DAFTAR ISI

vii

DAFTAR GAMBAR

ix

BAB 1 PENDAHULUAN

1

1.1 Latar Belakang

1

1.2 Perumusan Masalah

2

1.3 Tujuan Penelitian

2

1.4 Manfaat Penelitian

3

1.5 Metode Penelitian

3

BAB 2 TINJAUAN PUSTAKA

4

BAB 3 SCRAMBLING INDEX DARI GRAF PRIMITIF

7

3.1 Graf

7

3.2 Jalan

8

3.3 Primitifitas dan Eksponen

9

3.4 Scrambling Index

10

BAB 4 BATAS ATAS SCRAMBLING INDEX

19

4.1 Batas Atas Scrambling Index dari Graf Primitif

vii

19


4.2 Family Graf Primitif Memenuhi Batas Atas BAB 5 KESIMPULAN DAN SARAN

23 26

5.1 Kesimpulan

26

5.2 Saran

27

DAFTAR PUSTAKA

28

viii


DAFTAR GAMBAR

Nomor

Judul

Halaman

1.1

Contoh graf dengan maxv∈V {d(v, Cs )} = n − s

2

3.1

Contoh graf

8

3.2

G0n,s , s ≡ 1(mod 2)dan 3 ≥ s ≥ n

14

3.3

Gm n,s , s ≡ 1(mod 2), 1 ≤ s ≤ n − 1 dan 1 ≤ m ≤ n − s

15

4.1

Contoh graf primitif dengan k(G) ≤ (s − 1)/2 + maxv∈V {d(v, Cs)} 20

4.2

Contoh graf Lollipop dengan s = 3

22

4.3

Contoh graf Lollipop dengan s = 1

22

4.4

Contoh Special path pada graf primitif

23

4.5

Contoh graf primitif yang memiliki special path

24

4.6

Contoh graf primitif yang memiliki cycle tunggal

24

4.7

Gm n,s .s ≡ 1(mod2), 1 ≤ s ≤ n − 1, 1 ≤ m ≤ n − s

25

ix


BATAS ATAS UNTUK SCRAMBLING INDEX DARI GRAF PRIMITIF

Recommend Documents