PENERAPAN MATRIKS LAPLACIAN UNTUK MENENTUKAN BANYAKNYA POHON RENTANG PADA GRAF KINCIR, GRAF BUKU DAN GRAF MATAHARI
SKRIPSI diajukan guna melengkapi tugas akhir dan memenuhi salah satu syarat untuk menyelesaikan Program Studi Matematika (S1) dan mencapai gelar Sarjana Sains
Oleh Wahyu Yakin Subroto NIM 071810101110
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS JEMBER 2012
i
PENERAPAN MATRIKS LAPLACIAN UNTUK MENENTUKAN BANYAKNYA POHON RENTANG PADA GRAF KINCIR, GRAF BUKU DAN GRAF MATAHARI
SKRIPSI diajukan guna melengkapi tugas akhir dan memenuhi salah satu syarat untuk menyelesaikan Program Studi Matematika (S1) dan mencapai gelar Sarjana Sains
Oleh Wahyu Yakin Subroto NIM 071810101110
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS JEMBER 2012
i
PERSEMBAHAN
Skripsi ini saya persembahkan untuk: 1. Ibunda Nasihani dan Ayahanda Astamin yang tercinta, yang selalu memberikan do‟a dan semangat yang tiada terkira hingga penulis dapat menyelesaikan skripsi ini; 2. adik-adik yang tersayang, Makmur Wahana Sudrajat (Alm), Sri Astuti, Reni Puspita Ayu, David Saputra, dan Niken Wahyu Handayani yang selalu memberikan support, semangat, dan keceriaan dalam hidupku; 3. guru-guruku sejak taman kanak-kanak sampai dengan perguruan tinggi; 4. Almamater Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Jember.
ii
MOTO
“Orang-orang yang berhenti belajar akan menjadi pemilik masa lalu. Orang-orang yang masih terus belajar, akan menjadi pemilik masa depan. *)
*) Teguh, M. 2006. Becoming A Star. Jakarta: PT. Syaamil Cipta Media.
iii
PERNYATAAN
Saya yang bertanda tangan di bawah ini: nama : Wahyu Yakin Subroto NIM
: 071810101110
menyatakan dengan sesungguhnya bahwa karya ilmiah yang berjudul “Penerapan Matriks Laplacian untuk Menentukan Banyaknya Pohon Rentang pada Graf Kincir, Graf Buku dan Graf Matahari” adalah benar-benar hasil karya sendiri, kecuali kutipan yang sudah saya sebutkan sumbernya, belum pernah diajukan pada institusi manapun, dan bukan karya jiplakan. Saya bertanggung jawab atas keabsahan dan kebenaran isinya sesuai dengan sikap ilmiah yang harus dijunjung tinggi. Demikian pernyataan ini saya buat dengan sebenarnya, tanpa ada tekanan dan paksaan dari pihak mana pun serta bersedia mendapat sanksi akademik jika ternyata di kemudian hari pernyataan ini tidak benar.
Jember, ………… 2012 Yang menyatakan,
Wahyu Yakin Subroto NIM 071810101110
iv
SKRIPSI
PENERAPAN MATRIKS LAPLACIAN UNTUK MENENTUKAN BANYAKNYA POHON RENTANG PADA GRAF KINCIR, GRAF BUKU DAN GRAF MATAHARI
Oleh Wahyu Yakin Subroto 071810101110
Pembimbing
Dosen Pembimbing Utama
: Kristiana Wijaya, S.Si., M.Si.
Dosen Pembimbing Anggota : Kiswara Agung Santoso, M.Kom.
v
PENGESAHAN Skripsi yang berjudul “Penerapan Matriks Laplacian untuk Menentukan Banyaknya Pohon Rentang pada Graf Kincir, Graf Buku dan Graf Matahari” telah diuji dan disahkan pada: hari, tanggal : tempat
: Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Jember
Tim Penguji: Ketua,
Sekretaris,
Kristiana Wijaya, S.Si., M.Si. NIP 197408132000032004
Kiswara Agung Santoso, M.Kom NIP 197209071998031003
Penguji I,
Penguji II,
Kosala Dwidja Purnomo, S.Si., M.Si. NIP 196908281998021001
Dr. Alfian Futuhul Hadi, S.Si., MSi. NIP 19740719 2000121001
Mengesahkan Dekan,
Prof. Drs. Kusno, DEA, Ph.D. NIP 196101081986021001
vi
RINGKASAN
Penerapan Matriks Laplacian untuk Menentukan Banyaknya Pohon Rentang pada Graf Kincir, Graf Buku dan Graf Matahari; Wahyu Yakin Subroto, 071810101110; 2012: 38 halaman; Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Jember.
Graf berlabel pada titik adalah graf yang setiap titiknya diberi label. Untuk menentukan banyaknya unsur graf berlabel dapat dilakukan dengan membedakan mana graf yang tidak identik. Sehingga jumlah graf berlabel lebih banyak daripada jumlah graf yang tidak berlabel. Sebuah pohon yang terbentuk dari graf sederhana yang terhubung, dimana memuat semua titik pada graf tersebut dinamakan pohon rentang. Pohon rentang dari sebuah graf tidaklah tunggal. Dengan kata lain sebuah graf dapat mempunyai satu atau lebih pohon rentang. Untuk menentukan pohon rentang digunakan graf berlabel. Sedangkan untuk menentukan banyaknya pohon (𝑚 )
rentang pada graf kincir 𝐾𝑛
, graf buku Bn dan graf matahari Sn menggunakan
matriks laplacian. Dimana matriks laplacian didapat dari pengurangan matriks derajat dengan matriks adjacent. Tujuan penelitian adalah mengetahui cara mencari (𝑚 )
rumus umum untuk menentukan banyaknya pohon rentang pada graf kincir 𝐾𝑛
,
graf buku Bn dan graf matahari Sn dengan menggunakan matriks laplacian. Penelitian dilakukan dalam beberapa langkah. Langkah pertama adalah (𝑚 )
menentukan matriks laplacian dari graf kincir 𝐾𝑛
, graf buku Bn dan graf matahari
Sn dengan. Langkah kedua adalah menghapus baris pertama dan kolom pertama pada matriks laplacian. Langkah ketiga adalah menghitung determinan dari matriks yang telah dihapus baris pertama dan kolom pertama.
vii
Berdasarkan kajian yang telah dilakukan, didapatkan hasil bahwa dengan menghapus salah satu sisi pembuat sikel pada graf matahari maka akan didapatkan pohon rentang dari graf tersebut. Sedangkan dari perhitungan matriks laplacian didapatkan rumus umum untuk banyaknya pohon rentang pada graf kincir (𝑚 )
𝐾𝑛
adalah 𝑛𝑛𝑚 −2𝑚 . Untuk banyaknya pohon rentang pada graf buku Bn didapat
rumus umumnya adalah (3𝑛 −1 )(n+3). Sedangkan rumus umum untuk banyaknya pohon rentang pada graf matahari Sn adalah n.
viii
PRAKATA
Puji syukur ke hadirat Allah SWT atas segala rahmat dan karunia-Nya sehingga penulis dapat menyelesaikan skripsi yang berjudul “Penerapan Matriks Laplacian untuk Menentukan Banyaknya Pohon Rentang pada Graf Kincir, Graf Buku dan Graf Matahari”. Skripsi ini disusun untuk memenuhi salah satu syarat menyelesaikan pendidikan strata satu (S1) pada Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Jember. Penulisan skripsi ini tidak lepas dari bantuan berbagai pihak. Oleh karena itu, penulis menyampaikan terima kasih kepada: 1. Kristiana Wijaya, S.Si., M.Si., dan Kiswara Agung Santoso, M.Kom., selaku Dosen Pembimbing yang telah meluangkan waktu, pikiran, dan perhatian dalam penulisan skripsi ini; 2. Kosala Dwidja Purnomo, S.Si., M.Si., dan Dr. Alfian Futuhul Hadi, S.Si., MSi., selaku dosen penguji yang telah memberi masukan dalam skripsi ini; 3. ibu dan bapak serta keluarga di rumah yang telah memberikan doa; 4. teman-teman angkatan 2007, Riski, Silvi, Wasil, Yasin, Sinta, Khorirotus, Wiji, Hamid dan Risha serta teman-teman yang lainnya, terima kasih atas kebersamaan selama waktu kuliah dan telah memberikan semangat dan motivasi; 5. semua pihak yang tidak dapat disebutkan satu per satu. Penulis juga menerima segala kritik dan saran dari semua pihak demi kesempurnaan skripsi ini. Akhirnya penulis berharap, semoga skripsi ini dapat bermanfaat.
Jember, September 2012
Penulis
ix
DAFTAR ISI Halaman HALAMAN JUDUL .....................................................................................
i
HALAMAN PERSEMBAHAN ...................................................................
ii
HALAMAN MOTO ......................................................................................
iii
HALAMAN PERNYATAAN.......................................................................
iv
HALAMAN PEMBIMBINGAN ..................................................................
v
HALAMAN PENGESAHAN .......................................................................
vi
RINGKASAN ................................................................................................
vii
PRAKATA ....................................................................................................
ix
DAFTAR ISI..................................................................................................
x
DAFTAR TABEL .........................................................................................
xii
DAFTAR GAMBAR .....................................................................................
xiii
BAB 1. PENDAHULUAN ............................................................................
1
1.1
Latar Belakang ........................................................................
1
1.2
Rumusan Masalah ..................................................................
2
1.3
Tujuan ......................................................................................
3
1.4
Manfaat ....................................................................................
3
BAB 2. TINJAUAN PUSTAKA...................................................................
4
2.1
Definisi Graf ............................................................................
4
2.2
Operasi Hasil Kali Kartesius Dua Graf ................................
7
2.3
Penyajian Graf dalam Bentuk Matriks ..............................
8
2.3.1 Matriks Adjacent ..............................................................
8
2.3.2 Matriks Derajat ................................................................
8
2.3.3 Matriks Incident ...............................................................
9
Determinan Matriks ...............................................................
9
2.4.1 Mereduksi Baris ...............................................................
9
2.4.2 Ekspansi Kofaktor ............................................................
10
2.4
x
2.5
Matriks Elementer ..................................................................
11
2.6
Rank dan Kernel .....................................................................
13
2.7
Kelas-kelas Graf ......................................................................
14
2.8
Pohon Rentang ........................................................................
16
2.9
Matriks Laplacian ...................................................................
17
BAB 3. METODE PENELITIAN ................................................................
22
BAB 4. HASIL DAN PEMBAHASAN ........................................................
24
4.1
4.2
Hasil ..........................................................................................
24
4.1.1 Banyaknya Pohon Rentang pada Graf Kincir .................
24
4.1.2 Banyaknya Pohon Rentang pada Graf Buku Bn. .............
31
4.1.3 Banyaknya Pohon Rentang pada Graf Matahari Sn. .......
33
4.1.4 Menampilkan Pohon Rentang Graf Matahari Sn. ............
34
Pembahasan .............................................................................
35
BAB 5. KESIMPULAN
............................................................................
37
DAFTAR PUSTAKA ..................................................................................
38
LAMPIRAN ..................................................................................................
39
xi
DAFTAR TABEL
Halaman 4.1
Hasil determinan dari m=2 dan n=4,5,6 ...............................................
24
4.2
Hasil determinan dari m=3 dan n=4,5,6 ...............................................
26
4.3
Hasil determinan dari m=4 dan n=4,5,6 ...............................................
27
4.4
Hasil determinan untuk n=2,3,4,dan 5 ..................................................
31
4.5
Hasil determinan untuk n=3,4,5,6 dan 7 ...............................................
33
xii
DAFTAR GAMBAR
Halaman 2.1
Graf G dengan 4 titik dan 5 sisi ............................................................
4
2.2
Ilustrasi graf dengan loop dan sisi rangkap ...........................................
4
2.3
Graf yang memuat walk, trail, lintasan, dan sikel ................................
5
2.4
Graf identik dan graf isomorphic ..........................................................
6
2.5
(a) Graf terhubung dan (b) Graf tak terhubung .....................................
7
2.6
Hasil Perkalian Kartesius dua graf .......................................................
7
2.7
Graf lintasan P6 ....................................................................................
14
2.8
(a) Graf sikel C6 dan (b) Graf sikel C8 ..................................................
14
2.9
(a) Graf lengkap K5 dan (b) Graf kincir 𝐾4 ........................................
15
2.10 (a) Graf buku B3 dan (b) Graf matahari S4 ...........................................
16
2.11 Graf pohon T6 .......................................................................................
16
2.12 Pohon rentang pada G dengan 4 titik dan 5 sisi ...................................
17
4.1
(3)
Menentukan graf matahari dan spaning tree yang akan ditampilkan ..........................................................................
34
4.2
Hasil output program ............................................................................
34
4.3
Graf matahari S4 ...................................................................................
35
4.4
Bentuk pohon rentang dari graf matahari S4 ........................................
35
xiii
