SCRAMBLING INDEX DARI GRAF RING-STAR DAN VARIASINYA
SKRIPSI
FITRIANA 100803027
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2014
Universitas Sumatera Utara
SCRAMBLING INDEX DARI GRAF RING STAR DAN VARIASINYA
SKRIPSI
Diajukan untuk melengkapi tugas akhir dan memenuhi syarat mencapai gelar Sarjana Sains
FITRIANA 100803027
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2014
Universitas Sumatera Utara
PERSETUJUAN
Judul
: Scrambling Index dari Graf Ring Star dan Variasinya
Kategori
: Skripsi
Nama
: Fitriana
Nomor Induk Mahasiswa : 100803027 Program Studi
: Sarjana (S1) Matematika
Departemen
: Matematika
Fakultas
: Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara
Medan,
Oktober 2014
Komisi Pembimbing : Pembimbing 2
Pembimbing 1
Dr. Mardiningsih, M.Si NIP.19630405 198811 2 001
Prof. Dr. Saib Suwilo, M.Sc NIP.19640109 198803 1 004
Diketahui oleh : Departemen Matematika FMIPA USU Ketua,
Prof. Dr. Tulus, M.Si NIP. 19620901 198803 1 002
i Universitas Sumatera Utara
PERNYATAAN
SCRAMBLING INDEX DARI GRAF RING STAR DAN VARIASINYA
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan penting yang masing-masing disebutkan sumbernya.
Medan,
Oktober 2014
FITRIANA 100803027
ii Universitas Sumatera Utara
PENGHARGAAN
Puji dan syukur penulis panjatkan kepada Allah Tuhan Yang Maha Esa yang telah melimpahkan rahmat dan ridho-Nya sehingga penulis dapat menyelesaikan skripsi ini yang berjudul ”SCRAMBLING INDEX DARI GRAF RING STAR DAN VARIASINYA” . Shalawat dan salam dipersembahkan kepada Rasulullah Muhammad SAW, semoga keberkahan selalu tercurah kepada beliau, keluarga, sahabat dan para pengikutnya. Dalam menyelesaikan skripsi ini penulis banyak mendapatkan bantuan, motivasi, do’a dari berbagai pihak. Pada kesempatan ini penulis mengucapkan terima kasih kepada:
1. Bapak Prof. Dr. Tulus, M.Si, dan Ibu Dr. Mardiningsih, M.Si, selaku Ketua dan Sekretaris Departemen Matematika FMIPA USU Medan. 2. Bapak Prof. Dr. Saib Suwilo, M.Sc, selaku Dosen Pembimbing I dan Ibu Dr. Mardiningsih, M.Si, selaku Dosen Pembimbing II, yang telah banyak membantu penulis dan memberikan dukungan baik berupa nasihat, motivasi maupun ilmu pengetahuan kepada penulis dalam menyelesaikan penelitian ini. 3. Bapak Dr. Suwarno Ariswoyo, M.Si, selaku Dosen Pembanding I, dan Bapak Prof. Dr. Tulus, M.Si, selaku Dosen Pembanding II, yang telah memberikan nasehat, kritik dan saran yang membangun selama penelitian. 4. Seluruh staf pengajar dan staf administrasi Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sumatera Utara, Medan. 5. Ibunda Demsi Marpaung dan Ayahanda Parwono serta adinda Dwi Indah Noviana dan Riski Ramadhan yang dengan sabar membimbing, memotivasi, mend’oakan, mengingatkan dan memberikan dukungan moril maupun materil selama penulisan skripsi ini.
iii Universitas Sumatera Utara
Penulis juga menyampaikan terima kasih kepada teman-teman (Ayu, Ibah, Dewi, Husna, Lani, Rika dan Tria) yang senantiasa saling menyemangati dan saling memotivasi dalam menyelesaikan skripsi ini, semoga Allah meridhoi semua usaha yang dilakukan. Terima kasih kepada rekan-rekan Komutatif 2010, Murni 2010, Al FALAK, IM3 , HMM, dan lainnya yang telah banyak memberikan inspirasi dan pengalaman yang berharga dan berguna untuk bekal hidup di masa yang akan datang, hanya Tuhan yang dapat membalasnya. Penulis menyadari masih banyak kekurangan dalam penulisan skripsi ini, untuk itu saran dan kritik yang membangun dari pembaca sangat diharapkan. Penulis menyampaikan terima kasih atas perhatiannya, semoga tulisan ini dapat bermanfaat.
Medan,
Oktober 2014
FITRIANA
iv Universitas Sumatera Utara
SCRAMBLING INDEX DARI GRAF RING STAR DAN VARIASINYA
ABSTRAK Sebuah graf terhubung G dikatakan primitif bila terdapat bilangan bulat positif k sehingga untuk setiap pasangan titik u dan v terdapat jalan yang menghubungkan u dan v dengan panjang k. Scrambling index dari sebuah graf primitf G, k(G), adalah bilangan bulat positif terkecil k sehingga untuk setiap dua titik u dan v yang berbeda terdapat sebuah titik w dengan sifat bahwa ada jalan yang menghubungkan u dan w dengan panjang k. Untuk sebuah s-ring star R dengan panjang lingkaran ganjil s diperlihatkan bahwa k(R) = (s + 1)/2. Dua variasi graf ring star yang lainnya adalah graf s-wheel (W ) yang dan graf s-steering ship (S) dengan nilai scrambling index masing-masing graf adalah k(W ) = 1 untuk graf s-wheel dan k(S) = 2 untuk graf s-steering ship.
Kata kunci: terhubung, graf primitif, ring star, scrambling index.
v Universitas Sumatera Utara
SCRAMBLING INDEX OF RING STAR GRAPH AND ITS VARIATION ABSTRACT A connected graph G is called primitive provided that there is a positive integer k such that for each pair of vertices u dan v in G there is a walk of length k connecting u and v. A scrambling index of a primitive graph G, k(G), is the smallest positive integer k such that for each pair of distinct vertices u and v there is a vertex w with the property that there is a walk connecting u and v and a walk connecting v and w of length k. For a s-ring star R with cycle of odd length s we show that k(R) = (s + 1)/2. Two others variation of ring star graph is s-wheel (W ) graphand s-steering ship (S), we show that k(W ) = 1 for s-wheel graph and k(S) = 2 for s-steering ship graph. Keywords: connected, primitive graph, ring star, scrambling index.
vi Universitas Sumatera Utara
DAFTAR ISI Halaman PERSETUJUAN
i
PERNYATAAN
ii
PENGHARGAAN
iii
ABSTRAK
v
ABSTRACT
vi
DAFTAR ISI
vii
DAFTAR GAMBAR
ix
BAB 1 PENDAHULUAN
1
1.1 Latar Belakang
1
1.2 Perumusan Masalah
4
1.3 Tujuan Penelitian
5
1.4 Manfaat Penelitian
5
BAB 2 TINJAUAN PUSTAKA
6
2.1 Graf
6
2.2 Matriks Ketetanggaan (Adjacency)
7
2.3 Graf Terhubung
9
2.4 Primitifitas suatu Graf
11
2.5 Matriks Tak Negatif dan Eksponen dari Graf
12
2.5.1 Matriks Tak Negatif
12
2.5.2 Eksponen dari Graf
14
2.6 Scrambling Index
15
2.6.1 Scrambling Index Graf Primitif
15
2.6.2 Scrambling Index dari Lingkaran Ganjil
17
vii Universitas Sumatera Utara
2.6.3 Graf dengan Scrambling Index 1
18
BAB 3 METODE PENELITIAN
20
BAB 4 HASIL DAN PEMBAHASAN
21
4.1 Scrambling Index dari Graf Ring Star
21
4.2 Scrambling Index dari Graf Wheel
22
4.3 Scrambling Index dari Graf Steering Ship
24
BAB 5 KESIMPULAN DAN SARAN
25
5.1 Kesimpulan
25
5.2 Saran
26
DAFTAR PUSTAKA
27
viii Universitas Sumatera Utara
DAFTAR GAMBAR
Nomor Gambar
Judul
Halaman
1.1
Bentuk umum graf primitif s-ring star (R)
3
1.2
Bentuk umum graf primitif s-wheel (W )
4
1.3
Bentuk umum graf primitif s-steering ship (S)
4
2.1
Sebuah graf
6
2.2
Graf 4-wheel (W)
8
2.3
Contoh graf terhubung dan graf tidak terhubung
10
2.4
Contoh graf primitif
12
4.1
Lintasan terpendek yang menghubungkan vs+1 dan v2s
21
4.2
Setiap titik di W berada pada sebuah segitiga
23
4.3
u, v pada 2 segitiga berbeda terhubung dengan panjang jalan = 2
23
ix Universitas Sumatera Utara
