2-EKSPONEN DARI 2-DIGRAPH DENGAN LOOP
SKRIPSI
RICHARD ALBERT NASUTION 010803013
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2007
Universitas Sumatera Utara
2-EKSPONEN DARI 2-DIGRAPH DENGAN LOOP
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains
RICHARD ALBERT NASUTION 010803013
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2007
Universitas Sumatera Utara
PERSETUJUAN
Judul Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: : : : : : :
2-EKSPONEN 2-DIGRAPH DENGAN LOOP SKRIPSI RICHARD ALBERT NASUTION 010803013 SARJANA (S1) MATEMATIKA MATEMATIKA MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA
Medan, September 2007 Komisi Pembimbing : Pembimbing 2
Pembimbing 1
Dra. Mardiningsih, M.Si NIP.131803344
Dr. Saib Suwilo, MSc. NIP. 131796149
Diketahui oleh Departemen Matematika FMIPA USU Ketua, Dr. Saib Suwilo, MSc NIP. 131796149
i Universitas Sumatera Utara
PERNYATAAN
2-DIGRAPH DENGAN LOOP
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan,
September 2007
RICHARD ALBERT NASUTION 010803013
ii Universitas Sumatera Utara
PENGHARGAAN
Setinggi puji dan sedalam syukur penulis serahkan kehadirat Allah SWT yang telah memberikan berkat dan rahmatNya sehingga penulis dapat menyelesaikan skripsi yang berjudul ” 2-EKSPONEN DARI 2-DIGRAPH DENGAN LOOP ” ini dengan baik. Skripsi ini sebagai salah satu mata kuliah wajib yang harus diselesaikan oleh seluruh mahasiswa Fakultas MIPA Departemen Matematika. Pada kesempatan ini penulis mengucapkan terima kasih kepada Bapak Dr. Eddy Marlianto, M.Sc, selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sumatera Utara. Bapak Dr. Saib Suwilo, M.Sc, dan Bapak Henry Rani S, M.Si selaku Ketua dan Sekretaris Departemen Matematika di FMIPA USU Medan. Bapak Dr. Saib Suwilo, M.Sc, selaku dosen pembimbing I dan Dra. Mardiningsih, M.Si selaku dosen pembimbing II yang telah memberi dukungan moral, motivasi dan ilmu pengetahuan bagi penulis dalam menyelesaikan penelitian ini. Seluruh Staf Pengajar dan Staf Administrasi Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sumatera Utara. Ibunda Ruminah tercinta yang selalu memberikan dukungan moril dan materiel serta doa yang tiada hentinya kepada penulis serta kepada Adinda Sudarno Hariadi tercinta yang telah memberikan dorongan semangat kepada penulis. Tak lupa, penulis juga mengucapkan terima kasih kepada para teman dan seniorku di Lab. Ekstension, yaitu b’Toni, b’Indra, Didi, Salman, Santri, Radhi, Andika yang telah membantu dalam penyelesaian skripsi ini, dukungan dan motivasi dalam pengerjaan skripsi ini. Juga buat seniorku di stambuk ’00 serta seluruh rekanrekan ’01. Semoga Allah SWT memberikan balasan atas jasa-jasa mereka yang telah diberikan kepada penulis. Penulis menyadari masih banyak kekurangan dalam penulisan ini, untuk itu penulis meminta saran dan kritik yang membangun dari pembaca sekalian. Akhir kata penulis mengucapkan terima kasih atas perhatiannya, semoga tulisan ini berguna bagi yang membutuhkan.
iii Universitas Sumatera Utara
ABSTRAK
Pada 2-digraph D, 2-eksponen didefinisikan sebagai bilangan bulat terkecil pada h + k sehingga untuk setiap pasangan vertex u dan v di D terdapat walk dari u ke v dengan panjang h +k yang terdiri dari h arc merah dan k arc biru. 2-eksponen dari 2-digraph D dinotasikan oleh exp2 (D). Shader dan Suwilo memperlihatkan 2-eksponen dari 2digraph primitif terletak pada interval ((n3 − 5n2 )/2, (3n3 + 2n2 − 2n)/2). Tulisan ini akan memberikan bentuk umum dari 2-digraph dengan 2-eksponen tepat 2n, 2n − 1, dan 2n − 2
iv Universitas Sumatera Utara
2-DIGRAPH WITH LOOPS
ABSTRACT
On 2-digraph D, 2-exponent being defined as smallest integer h+ k therefore for every pairs of vertex u and v in D there is walk from u to v with legth h + k consist of h red arc and b blue arc. 2-exponent from 2-digraph D denoted by exp2 (D) Shader and suwilo show that 2-exponent from primitive 2-digraph lying on ((n3 − 5n2 )/2, (3n3 +2n2 −2n)) interval. This paper will give the general form of 2-digraphwith 2-exponent exactly 2n,2n-1,2n-2
v Universitas Sumatera Utara
DAFTAR ISI
Halaman PERSETUJUAN
i
PERNYATAAN
ii
PENGHARGAAN
iii
ABSTRAK
iv
ABSTRACT
v
DAFTAR ISI
vi
DAFTAR GAMBAR
viii
BAB 1. PENDAHULUAN 1.1. 1.2. 1.3. 1.4. 1.5. 1.6.
1
Latar Belakang Penelitian Perumusan Masalah Tinjauan pustaka Tujuan penelitian Manfaat penelitian Metode penelitian
1 3 3 4 4 5
2. 2-DIGRAPH PRIMITIF 2.1. 2.2. 2.3. 2.4. 2.5.
6
Notasi Matriks Adjacency Primitifitas Dari 2-Digraph Terhubung Kuat Matriks tak negatif & Eksponen 2-digraph Beberapa fakta tentang 2-digraph dengan loop
6 12 14 19 25
3. 2-DIGRAPH DENGAN LOOP
27
4. KESIMPULAN
34
4.1. Kesimpulan
34
vi Universitas Sumatera Utara
4.2. Saran
35
DAFTAR PUSTAKA
36
vii Universitas Sumatera Utara
DAFTAR GAMBAR
Gambar
Halaman
2.1
Representasi grafis dari Digraph
7
2.2
Digraph dengan path, walk, cycle dan loop
8
2.3
Representasi grafis dari 2-Digraph
10
2.4
2-Digraph dengan path, walk, cycle dan loop
11
2.5
Digraph dengan 4 vertex, 6 arc
12
2.6
2-Digraph dengan 4 vertex, 3 arc merah, dan 4 arc biru
13
2.7
(a) digraph terhubung kuat ;(b) digraph tidak terhubung kuat
15
2.8
digraph terhubung kuat
16
2.9
(a) 2-digraph terhubung kuat ;(b) 2-digraph tidak terhubung kuat
17
2.10 2-digraph primitif
19
2.11 Representasi digraph 3 vertex dan 7 arc
21
2.12 Representasi 2-digraph dengan 3 vertex, 3 arc biru dan 3 arc merah
23
4.1
Representasi 2-digraph dengan 2-eksponen 2n
35
4.2
Representasi 2-digraph dengan 2-eksponen 2n-1
35
viii Universitas Sumatera Utara
