BAB I PENDAHULUAN 1.1 Latar Belakang Alam semesta
memuat bentuk-bentuk dan
konsep matematika, meskipun alam
semesta tercipta sebelum matematika itu ada. Alam semesta serta segala
isinya diciptakan Allah dengan
ukuran-ukuran yang cermat dan teliti, dengan perhitunganperhitungan yang mapan,
dan dengan rumus-rumus serta persamaan
yang seimbang dan rapi
(Abdusysyakir, 2007:79).
Menurut Shihab (2003:482) dari
segi bahasa kata tersebut dapat berarti
kadar tertentu yang tidak bertambah atau berkurang, atau
berarti kuasa. Tetapi karena ayat tersebut
berbicara tentang segala
sesuatu yang berada
dalam kuasa Allah,
maka adalah lebih
tepat memahaminya dalam
arti ketentuan dan
sistem yang telah ditetapkan
terhadap segala sesuatu. Tidak hanya terbatas pada salah satu aspeknya saja. Manusia misalnya, telah ada kadar yang
ditetapkan Allah baginya.
Ayat di
atas menjelaskan bahwa
segala sesuatu yang
ada di alam
ini ada ukurannya,
ada hitungan-hitungannya, ada
rumusnya, atau ada
persamaannya. Ahli matematika
atau fisika tidak
membuat suatu rumus
sedikitpun. Mereka hanya menemukan
rumus atau persamaan, sehingga rumus-rumus yang ada sekarang bukan diciptakan manusia sendiri, tetapi sudah
disediakan. Manusia hanya menemukan dan menyimbolkan dalam bahasa matematika
(Abdusysyakir, 1997:80).
Dewasa ini semakin banyak muncul
penggunaan model matematika maupun penalaran matematika
sebagai alat bantu
dalam menyelesaikan permasalahan
yang dihadapi dalam
berbagai disiplin ilmu.
Teori graf merupakan
salah satu cabang matematika
yang penting dan
banyak manfaatnya karena
teori-teorinya dapat diterapkan
untuk memecahkan masalah
dalam kehidupan sehari-hari.
Dengan mengkaji dan menganalisa
model atau rumusan teori graf dapat diperlihatkan peranan dan kegunaannya dalam memecahkan
permasalahan. Permasalahan yang
dirumuskan 2 dengan
teori graf dibuat
sederhana, yaitu diambil
aspek-aspek yang diperlukan
dan dibuang aspek-aspek lainnya
(Purwanto, 1998:1).
Salah satu
materi dalam teori
graf adalah pohon
(tree). Pohon (tree) didefinisikan sebagai graf tak-berarah
terhubung yang tidak memuat
sirkuit. Menurut definisi tersebut, ada dua sifat penting pada
pohon (tree) yaitu terhubung dan tidak memuat sirkuit (Chartrand dan Lesniak,
1986:67).
Konsep pohon
(tree) merupakan konsep
yang paling penting
karena konsep ini mampu mendukung penerapan graf dalam
berbagai bidang ilmu. Kirchoff (1824 – 1887) mengembangkan
teori-teori pohon untuk
diterapkan dalam jaringan
listrik.
Selanjutnya Arthur
Cayley (1821-1895) mengembangkan
graf jenis ini
sewaktu mencacah isomer
hoidrokarbon jenuh CnH2n+ . Sekarang pohon (tree) digunakan luas dalam linguistik dan ilmu komputer (Sutarno,
2005:104).
Misalkan G graf dan H subgraf
dari G. H disebut subgraf rentangan (spanning subgraph) dari graf G jika
order H
sama dengan order G, atau dengan kata lain jika V(H) = V(G). Subgraf rentangan H dari graf G
dapat dengan mudah diperoleh dengan cara menghapus
satu atau lebih
dari sisi di
G. Dengan demikian,
jika F adalah himpunan bagian dari E(G), maka graf G – F
pasti merupakan subgraf rentangan dari G
(Chartrand dan Lesniak, 1986:8).
Berkaitan dengan subgraf
rentangan, maka permasalahan yang
menarik untuk dikaji adalah
menentukan banyaknya subgraf
rentangan yang berbentuk
pohon dari suatu graf, yang dikenal dengan sebutan
banyaknya pohon rentangan (spanning tree number).
3 Misalkan
G graf dengan
order p (p
1) dan ukuran
q serta himpunan
titik 12 , ,..., p V G v v v . Matriks
keterhubungan titik (atau
matriks keterhubungan) dari
graf G ,
dinotasikan dengan A(G),
adalah matriks (p
x p) dengan
unsur pada baris ke-i
dan kolom ke-j bernilai 1 jika
titik i v terhubung langsung dengan
titik j v serta bernilai 0 jika titik i v tidak terhubung langsung dengan titik j v . Dengan kata lain, matriks adjacency dapat ditulis ,1 , ij A G a i j p , dengan ij a ij v v E G ij v v E G Matriks keterhubungan
suatu graf G
adalah matriks simetri
dengan unsur 0 dan
1 dan memuat nilai 0 pada diagonal utamanya (Chartrand dan Lesniak, 1986: 4).
Matriks derajat
dari matriks G,
dinotasikan dengan D(G),
adalah matriks diagonal yang
elemen baris ke-i dan kolom ke-i adalah derajat dari i v , 1,2,3,...,
ip Jika ,1 , ij D G d i j p , maka deg ii i dv dan ij d untuk ij . Matriks T(G) =
D(G) - A(G), disebut matriks Laplacian dan sebarang kofaktor dari T(G) sama dengan
banyaknya pohon rentangan
(spanning tree number)
pada G, yaitu
τ(G) (Agnarsson dan Greenlaw,
2007:112).
Untuk menentukan
pohon rentangan dari
suatu graf terhubung,
biasanya dilakukan dengan
cara menghapus sisi-sisi
sehingga graf tersebut
tidak lagi mengandung
sikel. Akan tetapi,
cara ini memerlukan
waktu yang lama,
sehingga diperlukan suatu
cara atau rumusan
baku untuk menentukan
banyaknya pohon 4 rentangan
dari suatu graf, yaitu dengan cara direpresentasikan dalam bentuk matriks.
Bentuk graf
yang dinyatakan dalam
suatu matriks kemudian
diselesaikan dengan metode-metode yang berlaku pada matriks.
Penelitian mengenai
banyaknya pohon rentangan
yang sudah atau
sedang dilakukan adalah
menentukan banyaknya pohon
rentangan pada graf
komplit. Oleh sebab
itu, dalam penelitian
ini penulis tertarik
untuk meneliti mengenai
banyaknya pohon rentangan
pada graf bipartisi
komplit yang dikemas
dalam judul penelitian
“Aplikasi Teorema Matriks-Pohon
untuk Menentukan Banyaknya Pohon Rentangan pada Graf Bipartisi
Komplit ” 1.2 Rumusan Masalah Berdasarkan latar belakang
tersebut, maka rumusan masalah dalam penulisan skripsi ini antara lain: 1. Bagaimana cara menentukan banyaknya pohon
rentangan pada graf bipartisi komplit dengan aplikasi teorema matriks-pohon? 2. Bagaimanakah
bentuk umum banyaknya
pohon rentangan graf
bipartisi komplit dengan aplikasi teorema matriks-pohon? 5 1.3
Tujuan Penelitian Beujuanrdasarkan rumusan masalah di atas, maka Tujuan
penulisan skripsi ini antara lain: 1. Menjelaskan
cara menentukan banyaknya
pohon rentangan pada
graf bipartisi komplit dengan aplikasi teorema matriks-pohon.
2. Menentukan
bentuk umum banyaknya
pohon rentangan pada
graf bipartisi komplit
dengan aplikasi teorema matriks-pohon.
1.4 Manfaat Penelitian Adapun manfaat dari penulisan skripsi ini
adalah: 1. Bagi peneliti,
untuk memperdalam dan
mengembangkan wawasan disiplin
ilmu yang telah
dipelajari untuk mengkaji
permasalahan tentang aplikasi
teorema matriks-pohon untuk
menentukan banyaknya pohon rentangan pada graf bipartisi komplit .
2. Bagi pemerhati matematika, sebagai tambahan
pengetahuan bidang matematika, khususnya
teori graf mengenai aplikasi teorema matriks-pohon untuk menentukan banyaknya pohon rentangan pada graf bipartisi
komplit .
3. Bagi
lembaga UIN Malang,
untuk bahan kepustakaan
yang dijadikan sarana pengembangan wawasan keilmuan khususnya di
jurusan matematika untuk mata kuliah
teori graf.
6 1.5
Metode Penelitian Metode
yang digunakan dalam
skripsi ini adalah
metode penelitian pustaka (Library
research), yaitu dengan
mengumpulkan data dan
informasi dari berbagai sumber
seperti buku, jurnal,
atau makalah-makalah. Penelitian
dilakukan dengan melakukan
kajian terhadap buku-buku
teori graf dan
jurnal-jurnal atau makalahmakalah yang
memuat topik tentang
banyaknya pohon rentangan
pada suatu graf.
Langkah selanjutnya adalah menentukan banyaknya pohon rentangan
dari beberapa contoh graf bipartisi komplit .
Adapun langkah-langkah yang
digunakan oleh peneliti
dalam membahas penelitian ini
adalah sebagai berikut: 1. Mencari literatur utama yang dijadikan acuan dalam
pembahasan ini.
2. Mengumpulkan berbagai
literatur pendukung, baik yang bersumber dari buku, jurnal, artikel,
diktat kuliah, internet,
dan lainnya yang
berhubungan dengan permasalahan
yang akan dibahas dalam penelitian ini.
3. Memahami dan mempelajari
konsep banyaknya pohon rentangan.
4. Menerapkan konsep tersebut,
yaitu: a) Menentukan matriks
adjacency dan matriks
derajat dari graf
bipartisi komplit .
b) Mencari
nilai selisih dari
matriks derajat dan
matriks adjacency (matriks laplacian) dan nilai kofaktor matriks
laplacian dari graf bipartisi komplit(Km,n ) c) Membuat dugaan (konjektur) berdasarkan pola
yang ditentukan.
0 komentar:
Posting Komentar