BAB I PENDAHULUAN
1.1 Latar Belakang Al Qur’an
sebagai wahyu Allah yang dijadikan panduan utama didalam menjalankan ajaran
Islam tidak hanya
memuat aturan-aturan peribadatan
bagi umat-Nya, tetapi juga memuat pengetahuan baik dimasa yang lalu
maupun masa akan datang, termasuk didalamnya adalah tentang Ilmu pengetahun.
Kewajiban menuntut ilmu/
mempelajari ilmu pengetahuan dalam Islam telah
jelas diperintahkan dalam
Al Qur’an maupun
sunnah. Karena dengan mempelajari ilmu pengetahuan
diharapkan seorang muslim akan lebih meyakini kekuasaan Allah sehingga bisa
mempertebal keimanan kepada-Nya, dimana ilmu pengetahuan itu tidak hanya digali
dari ayat-ayat qouliyah yang tertulis di dalam Al Qur’an, tetapi juga ayat-ayat
kauniyah yang terhampar di alam semesta.
Matematika sebagai salah satu
disiplin Ilmu sering disebut sebagai Ibu sekaligus pelayan ilmu pengetahuan,
hal itu karena matematika merupakan salah satu
ilmu pengetahuan dasar
yang merupakan sumber
dari ilmu pengetahuan terapan. Sedangkan
dikatakan sebagai pelayan
karena matematika juga
sering dipakai untuk membantu mempermudah penyelesaian permasalahan yang
ada di dalam ilmu-ilmu lainnya.
Teori graf merupakan salah satu
cabang matematika yang masih menarik untuk dibahas karena teori-teorinya masih
aplikatif sampai saat ini dan dapat diterapkan
untuk memecahkan masalah
dalam kehidupan sehari-hari.
Dengan mengkaji dan menganalisis model atau rumusan, teori graf dapat
diperlihatkan peranan dan kegunaannya
dalam memecahkan berbagai
permasalahan.
Permasalahan yang dirumuskan
dengan teori graf dibuat sederhana, yaitu diambil aspek-aspek yang
diperlukan dan dibuang
aspek-aspek lainnya (Purwanto, 1998:1).
Salah satu cabang dari teori graf
adalah tentang pohon. Konsep pohon merupakan konsep yang paling penting karena
konsep ini mampu mendukung penerapan
graf dalam berbagai
bidang ilmu. Kirchoff
(1824-1887) mengembangkan teori pohon untuk diterapkan dalam jaringan
listrik. Selanjutnya Arthur Cayley
(1821-1895) mengembangkan graf
jenis ini sewaktu mencacah isomer hoidrokarbon
jenuh CnH2n+2. Sekarang
pohon digunakan luas
dalam linguistik dan ilmu komputer (Heri Sutarno, 2005:104).
Pohon adalah graf terhubung yang
asiklik (tidak memuat sikel). Sebuah pohon selalu terdiri dari ntitik dan
n-1sisi. Pohon yang merupakan subgraf dari e e e suatu
graf terhubung G,
yang memuat seluruh
titik dari G
disebut pohon rentangan (spanning
tree) (Rasyid, 2006:18).
Menentukan banyaknya
pohon rentangan dari
suatu graf merupakan masalah tersendiri
dalam teori graf.
Selama ini dikenal
dua algoritma atau algoritma solin (metode memotong) dan
algoritma kruskal (motode membangun).
Namun kedua
algoritma tersebut biasa
digunakan untuk mendapatkan
pohon rentangan minimal yaitu pohon rentangan dari suatu graf yang
memiliki bobot, dimana pohon rentangan
minimal dari graf
tersebut adalah pohon
rentangan dengan jumlah bobot terkecil.
Untuk menentukan pohon rentangan
dari suatu graf terhubung, biasanya dilakukan dengan cara memotong/ memutus
sisi-sisi sehingga graf tersebut tidak lagi
mengandung sikel. Misal
graf G dengan
} , , , { ) ( d c b a G V = dan }
, , , { ) ( 4 3 2 e e e e G E = Maka
untuk membentuk spanning tree dari graf G tersebut adalah dengan cara menghapus
salah satu atau lebih sisi sehingga graf G
tidak lagi memuat sikel, e a b c
d Gambar 1.1 Graf G e e e e e e e e e Gambar
1.2 banyaknya Pohon Rentangandari Graf G Pada Gambar 1.2 T1 dibentuk dengan
menghapus sisi e1, T2 dibentuk dengan menghapus sisi e2, T3
dibentuk dengan menghapus sisi e3, T4 dibentuk dengan menghapus sisi e Dari contoh
tersebut, dapat dilihat
bahwa banyaknya pohon
rentangan (spanning tree) yang dibentuk dari graf terhubung G adalah
sebanyak 4 pohon rentangan.
Menururt penulis, penghitungan
dengan cara tersebut untuk menentukan banyaknya
pohon rentangan dari
suatu graf memerlukan
waktu yang lama, misalnya untuk meentukan banyaknya
pohon rentangan dari graf komplit dengan K10,
K20, atau bahkan K100, sehingga
perlu digunakan cara atau rumusan baku untuk menentukan banyaknya pohon
rentangan dari suatu graf.
a b c d T1: e a b c d T2:
e a b c d T3: e a b c d T4: Ada
beberapa masalah dalam teori graf yang bisa lebih mudah diselesaikan apabila
graf yang dihadapi direpresentasikan dalam bentuk matriks. Bentuk graf yang dinyatakan
dalam suatu matriks
kemudian diselesaikan dengan
metodemetode yang berlaku pada matriks.
Maka berdasarkan
uraian tersebut penulis
bermaksud mengajukan penelitian untuk
skripsi ini dengan
judul ”Aplikasi Matriks-Pohon untuk menentukan banyaknya Pohon Rentangan
pada Graf Komplit ( )” 1.2 Rumusan Masalah Berdasarkan latar
belakang tersebut, maka
rumusan masalah dalam penulisan skripsi ini adalah: bagaimana
menentukan banyaknya pohon rentangan pada graf komplit ( )dengan aplikasi
Matriks-Pohon .
1.3 Batasan Masalah Agar pembahasan
dalam skripsi ini
tidak meluas, maka
penulis membatasi penelitian ini hanya pada masalah banyaknya pohon rentangan pada graf komplit (
) dengan n ≥ 2 dan n Ν ∈ .
1.4 Manfaat Penelitian Adapun
manfaat dari penulisan skripsi ini adalah: 1. Bagi peneliti,
sebagai tambahan informasi
dan wawasan pengetahuan mengenai teori graf khusunya
Aplikasi Matriks-Pohon untuk menentukan banyaknya
pohon rentangan pada Graf Komplit ( ).
2. Bagi pemerhati
matematika, sebagai tambahan
pengetahuan bidang matematika,
khususnya Teori Graf mengenai Aplikasi Matriks-Pohon untuk menentukan banyaknya
pohon rentangan pada graf komplit ( ) 3. Bagi lembaga UIN Malang, untuk bahan
kepustakaan yang dijadikan sarana pengembangan wawasan keilmuan khususnya di
jurusan matematika untuk mata kuliah Teori Graf.
1.5 Metode Penelitian Dalam penelitian
ini penulis menggunakan
jenis penelitian deskriptif kualitatif dengan metode
penelitian kepustakaan (library research) atau kajian pustaka, yakni melakukan
penelitian untuk memperoleh data-data dan informasiinformasi serta objek yang
digunakan dalam pembahasan masalah tersebut.
0 komentar:
Posting Komentar