EKSPONEN TITIK KELUAR DARI SEBUAH KELAS DIGRAF DWIWARNA PRIMITIF DENGAN n-TITIK GANJIL
SKRIPSI
MARDHA TILLAH 090803044
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2013 Universitas Sumatera Utara
EKSPONEN TITIK KELUAR DARI SEBUAH KELAS DIGRAF DWIWARNA PRIMITIF DENGAN n-TITIK GANJIL
SKRIPSI Diajukan untuk melengkapi tugas akhir dan memenuhi syarat mencapai gelar Sarjana Sains
MARDHA TILLAH 090803044
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2013 Universitas Sumatera Utara
i PERSETUJUAN
Judul
: EKSPONEN TITIK KELUAR DARI SEBUAH KELAS DIGRAF DWIWARNA PRIMITIF ATAS n-TITIK GANJIL Kategori : SKRIPSI Nama : MARDHA TILLAH Nomor Induk Mahasiswa : 090803044 Program Studi : SARJANA (S1) MATEMATIKA Departemen : MATEMATIKA Fakultas : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA
Medan,
Oktober 2013
Komisi Pembimbing : Pembimbing 2
Pembimbing 1
Dra. 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
Universitas Sumatera Utara
ii PERNYATAAN
EKSPONEN TITIK KELUAR DARI SEBUAH KELAS DIGRAF DWIWARNA PRIMITIF ATAS n-TITIK GANJIL
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan penting yang masing-masing disebutkan sumbernya.
Medan,
Oktober 2013
MARDHA TILLAH 090803044
Universitas Sumatera Utara
iii PENGHARGAAN
Besar rasa syukur kepada Sang Khaliq dengan limpahan rahmat dan kasih sayang-Nya memberikan keluasan waktu serta kesempatan bagi saya untuk menyelesaikan penelitian ini dengan judul ”EKSPONEN TITIK KELUAR DARI SEBUAH KELAS DIGRAF DWIWARNA PRIMITIF ATAS n-TITIK GANJIL” . Serta salawat dan salam kepada baginda Rasul Muhammad SAW yang sampai detik ini merupakan panutan terbaik bagi setiap manusia. Serangkai ucapan terima kasih saya hanturkan kepada Ibunda Sabariah, Ibunda Waliyah dan Ayahanda Alm.H.Amiruddin Tholib yang tanpa pernah lelah menyayangi, menjaga, merawat serta mendoakan dalam setiap langkah. Semoga Ibunda dan Ayahanda tercinta selalu berada dalam cinta dan lindungan-Nya. Kepada Bapak Prof.Saib Suwilo,M.Sc selaku dosen pembimbing I dan Ibu Dra.Mardiningsih,M.Si selaku dosen pembimbing II terima kasih atas segala bentuk bimbingan dan motivasi dalam menyelesaikan penelitian ini sebagai tugas akhir akademik, dan kepada Bapak Prof.Tulus,M.Si dan Bapak Drs.Ariswoyo,M.Si selaku dosen penguji, terima kasih atas segenap sarannya. Kepada Bapak Prof.Dr.Sutarman,M.Sc, selaku Dekan FMIPA USU, Bapak Prof.Dr.Tulus,M.Si dan Ibu Dra.Mardiningsih,M.Si, selaku Ketua Departemen dan Sekretaris Departemen FMIPA USU serta seluruh Staf Pengajar yang telah memberikan pengetahuan-pengetahuan akademik dan seluruh Staf Departemen Matematika yang turut mempermudah jalannya proses penyelesaian tugas akhir ini. Semoga selalu dalam Rahmat dan Karunia-Nya. Terima kasih kepada seluruh abanganda tercinta Ahmad Aulia,S.Pd, Afzar Aulia, Alfi Syahrin,S.E, dr.Ibnu Hasyim, Ir.Anshor Khawari, dan abanganda Rafiq Kahfi serta adikku tercinta Samanthi Hibbah yang selalu memberikan motivasi, dukungan moral dan materi, serta doa yang tak pernah henti, semoga selalu dalam lindungan dan Rahmat Allah SWT, dan kepada sahabatku Anggita Fathimah Siregar yang tak pernah bosan mendengar segala keluh kesah perjalanan tugas akhir ini serta selalu mengingatkan bahwa pelajaran yang takkan habis dalam hidup ini adalah bab ikhlas, bab adil, dan bab sabar, terima kasih atas segala dukungannya. Semoga segala impianmu dapat terwujud. Kepada sahabat-sahabat Ilham Firdaus Siregar, Dewi Uli Sinulingga, dan teman-teman seperjuangan 1708 di pesantren Ar-Raudhatul yang ikut memberikan dukungan, terima kasih atas segala bantuan, motivasi serta doanya. Semoga visi dan misi hidup kita berjalan dalam Ridho-Nya. Tak lupa pula penulis berterima kasih kepada Wiwit, Nisa, Desi, Sari, Defi, Best, Isah, Dika, Ida,dan Wirda yang selalu ada dalam suka duka di awal perkuliahan hingga penyelesaian tugas akhir ini,kepada Putri dan Sarah terima kasih krna tak pernah bosan menjadi tempat bertanya persoalan akademik. Kepada teman-teman kelas murni Panca , Bakti , Lukas , Jundi , Vela , Fitri , dan Zati terima kasih atas kesolidaritasannya. Kepada Yudha, Fendi, Gilang , Dhani , Iman , Adinda Lita , Organisasi IM3, teman-teman sejawad dan seperjuangan selama perkuliahan yang tak Universitas Sumatera Utara
iv bisa disebutkan namanya satu persatu oleh penulis, terima kasih atas ikatan pertemanan dan silaturrahmi yang dijalani bersama. Semoga tali silaturrahmi ini dapat terjalin tanpa batas waktu. Sebagai manusia, sudah tentu banyak kekurangan penulis dalam bentuk apapun, baik dalam silaturrahmi ataupun dalam penulisan tugas akhir ini penulis hanturkan segenap permintaan maaf dan harapan dalam menyelesaikan tulisan ini semoga berguna bagi pembaca. Akhir kata, ribuan terima kasih penulis hanturkan atas segala doa dan dukungan pembaca. Wassalam. Medan, Oktober 2013 Penulis MARDHA TILLAH
Universitas Sumatera Utara
v ABSTRAK
Sebuah digraf dwiwarna D(2) adalah primitif jika terdapat bilangan bulat tak negatif g dan h sehingga untuk setiap pasang titik u dan v di D(2) terdapat (g, h)-walk dari u ke v. Bilangan bulat positif g + h terkecil dari semua bilangan bulat tak negatif g dan h disebut eksponen dari digraf dwiwarna D(2) , dinotasikan dengan expD(2) (v). Andaikan v adalah sebuah titik di D(2) . Eksponen titik keluar v pada D(2) adalah bilangan bulat positif terkecil g + h sehingga terdapat (g, h)-walk dari titik v ke setiap titik di D(2) , dinotasikan dengan expoutD(2) (v). Penelitian ini mempelajari eksponen titik keluar dari sebuah kelas digraf dwiwarna primitif D(2) atas n ≥ 5 titik ganjil yang terdiri dari n-cycle v1 → vn → vn−1 → · · · → v2 → v1 dan tepat satu arc v1 → v n+1 . 2 Andaikan vk , k = 1, 2, ..., n adalah sebuah titik di D(2) . Diperlihatkan bahwa jika arc biru berturut-turut terletak pada arc v2 → v1 dan arc v1 → vn di D(2) , maka eksponen titik keluar dari digraf dwiwarna D(2) adalah expoutD(2) (vk ) = n2 − n − 2 + k untuk semua k = 1, 2, ..., n .Jika arc biru berturut-turut terletak pada arc v n+3 → v n+1 2 2 dan arc v n+1 → v n−1 , maka eksponen titik keluar dari digraf dwiwarna primitif D(2) 2
2
adalah expoutD(2) (vk ) =
2n2 −3n−2+2k 2
untuk semua k = 1, 2, ..., n.
Kata kunci : Digraf dwiwarna, primitif, eksponen titik dan eksponen titik keluar.
Universitas Sumatera Utara
vi THE OUTER VERTEX EXPONENTS OF A CLASS OF PRIMITIVE TWO COLORED DIGRAPHS ON n-ODD VERTEX
ABSTRACT A two-colored digraph D(2) is primitive provided there are nonnegative integer g and h such that for each pair of vertices u and v there is a (g, h)-walk from vertex u to vertex v. The smallest positive integer g + h taken over all such nonnegative integers g and h is the exponent of a two-colored digraph D(2) , denoted by exp(D(2) ). Let v be a vertex of D(2) . The outer vertex exponent v is the smallest positive integer g + h there is a (g, h)-walk from v to every vertex in D(2) , denoted by expoutD(2) (v). This study explains about the outer vertex exponent of primitive two colored-digraph D(2) on n ≥ 5 odd vertices consisting the n-cycle v1 → vn → vn−1 → · · · → v2 → v1 and blue arc v1 → v n+1 . Let vk be a vertex of D(2) . We show that if two consecutive blue 2 arcs lies on arc v2 → v1 and arc v1 → vn in D(2) , then the outer vertex exponents is expoutD(2) (vk ) = n2 − n − 2 + k for all k = 1, 2, ..., n. If two consecutive blue arcs lies on arc v n+3 → v n+1 and arc v n+1 → v n−1 , then the outer vertex exponents is 2
expoutD(2) (vk ) =
2
2n2 −3n−2+2k 2
2
2
for all k = 1, 2, ..., n.
Key words : Two-colored digraph, primitive, vertex exponent and outer vertex exponent.
Universitas Sumatera Utara
vii DAFTAR ISI Halaman i ii iii v vi vii viii
PERSETUJUAN PERNYATAAN PENGHARGAAN ABSTRAK ABSTRACT DAFTAR ISI DAFTAR GAMBAR BAB 1 PENDAHULUAN 1.1 Latar Belakang Penelitian 1.2 Masalah Penelitian 1.3 Tinjauan Pustaka 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian
1 2 3 5 6
BAB 2 DIGRAPH DWIWARNA PRIMITIF 2.1 Definisi 2.2 Matriks Adjacency 2.3 Primitifitas Dari Digraph Dwiwarna Terhubung Kuat 2.4 Matriks Tak Negatif dan Eksponen Digraph Dwiwarna 2.5 Eksponen Titik Digraph dan Digraph Dwiwarna 2.6 Sistem Persamaan Diophantine 2.7 Formula Eksponen Titik Digraph Dwiwarna dengan Dua Cycle
7 10 12 16 24 26 28
BAB 3 METODOLOGI PENELITIAN 3.1 Menentukan Eksponen Titik Keluar 3.2 Pembuktian Bentuk Umum Eksponen Titik Keluar
31 31
BAB 4 EKSPONEN TITIK KELUAR
33
BAB 5 KESIMPULAN DAN SARAN 5.1 Kesimpulan 5.2 Saran
42 42
DAFTAR PUSTAKA
43
Universitas Sumatera Utara
viii DAFTAR GAMBAR
Gambar 1.1 1.2 2.1 2.2 2.3 2.4 2.5 2.6 2.7 4.1 4.2
Halaman Karakter Pertama D(2) Karakter Kedua D(2) Digraf dengan 4 titik dan 6 arc Digraf dwiwarna dengan 6 titik dan 8 arc Digraf terhubung kuat dan tidak terhubung kuat Digraf terhubung kuat dan primitif Digraf dwiwarna terhubung kuat dan tidak terhubung kuat Digraf dwiwarna terhubung kuat dan primitif Digraf dengan 3 titik dan 4 arc Digraf dwiwarna D(2) Tipe A Digraf dwiwarna D(2) Tipe B
5 5 8 9 12 13 14 15 20 34 34
Universitas Sumatera Utara
