BAB I PENDAHULUAN
1.1 Latar Belakang Dalam
kehidupan di dunia,
manusia tidak lepas
dari berbagai permasalahan.
Permasalahan-permasalahan tersebut
menyangkut berbagai aspek,
dimana dalam penyelesaiannya diperlukan
sebuah pemahaman melalui suatu
metode dan ilmu
bantu tertentu. Salah
satunya adalah ilmu
matematika. Matematika merupakan
alat untuk menyederhanakan penyajian dan pemahaman
masalah. Dalam bahasan matematika, suatu masalah
dapat menjadi lebih
sederhana untuk disajikan,
dipahami, dianalisis, dan dipecahkan. Untuk
keperluan tersebut, pertama
dicari pokok masalahnya,
kemudian dibuat rumusan
atau model matematikanya
(Purwanto, 1998: 1).
Matematika adalah ratunya
ilmu pengetahuan, sehingga
matematika tidak dapat dilepaskan
dari berbagai ilmu yang ada dan matematika juga membantu
dalam kehidupan sehari-hari (Falaqiyah, 2004:
1).
Salah satu cabang ilmu
matematika yang bermanfaat dalam
kehidupan sehari-hari adalah Teori Graf.
Pada Teori Graf diberikan model
matematika untuk setiap himpunan dari sejumlah
obyek diskrit, dimana
beberapa pasangan unsur
dari himpunan tersebut terikat
menurut suatu aturan
tertentu. Obyek diskrit
dari dari suatu
himpunan misalnya dapat
berupa orang-orang dengan
aturan kenal, atau
juga himpunan nama
kota dengan aturan jalan yang menghubungkan antara kota
satu kekota yang lain.
Secara umum
beberapa konsep dari
disiplin ilmu telah
dijelaskan dalam AlQuran. Salah konsep dari disiplin ilmu
matematika yang terdapat dalam Al-Qur’an adalah masalah
teori graf. Teori
graf merupakan salah
satu cabang dari matematika
yang didefinisikan sebagai
himpunan tidak kosong yang memuat elemen-elemen yang disebut titik, dan pasangan tidak terurut dari elemen-elemen
itu disebut sisi.
Saat ini teori graf semakin
berkembang dan menarik.Hal ini disebabkan teori graf merupakan teori yang unik dan memiliki banyak
penerapan. Keunikan teori graf adalah kesederhanaan pokok
bahasan yang dipelajarinya, karena dapat
disajikan sebagai titik (vertex)dan
sisi (edge).
Menurut sejarah teori graf lahir
pada tahun 1736 melalui tulisan L.Euler, seorang matematikawan
Swiss, yang berisi
tentang upaya pemecahan
masalah jembatan Konigsberg yang sangat terkenal di Eropa
(Sutarno, 2001: 65). Di Konigsberg
(sebelah timur Prussia,
Jerman) sekarang bernama
Kaliningrad terdapat sungai Pregal
yang mengitari pulau
Kneiphof lalu bercabang
menjadi dua buah anak
sungai tesebut. Ada tujuh buah
jembatan yang menghubungkan
daratan yang dibelah oleh
sungai tersebut.
Masalahnya adalah “Apakah mungkin
melalui ketujuh jembatan itu masing-masing tepat satu kali, dan kembali ke tempat semula?.
Euler membuat model masalah tersebut dalam bentuk
graf. Daratan dinyatakannya
sebagai sebagai titik
atau (vertex); dan
jembatan dinyatakannya sebagai
garis yang disebut
sisi (edge). Jawaban
yang dikemukakannya adalah
tidak mungkin orang
melalui ketujuh jembatan itu
masing-masing satu kali
dan kembali lagi ke tempat asal
keberangkatan jika derajat setiap titik tidak seluruhnya genap, yaitu banyaknya garis yang terkait langsung
dengantitik.
Berikut ini adalah firman Allah
yang menyatakan tentang keterkaitan antara titik sebagai
awal penciptaan manusia
dan garis sebagai
proses perjalanan manusia
yang terdapat dalam surat
Al-Mukminun ayat 12-16 yang berbunyiKemudian kami jadikan saripati itu air mani
(yang disimpan) dalam tempat yang kokoh
(rahim).
Kemudian air
mani itu kami
jadikan segumpal darah,
lalu segumpal darah
itu kami jadikan
segumpal daging, dan
segumpal daging itu
kami jadikan tulang belulang, lalu tulang belulang itu kami
bungkus dengan daging. Kemudian kami jadikan
dia makhluk yang (berbentuk) lain. Maka Maha sucilah Allah, Pencipta yang paling baik.
Kemudian, sesudah itu,
Sesungguhnya kamu sekalian benar-benar akan mati.
Kemudian, Sesungguhnya
kamu sekalian akan
dibangkitkan (dari kuburmu)
di hari kiamat.
Ayat tersebut menyatakan bahwa
manusia diciptakan dari suatu titik atau saripati, air
mani, segumpal darah,
dan lain sebagainya
yang telah disebutkan
dalam surat AlMukminun tersebut. Kemudian beberapa garis
dalam suatu graf adalah proses perjalanan manusia dari awal diciptakan hingga kemudian
mati dan dibangkitkan kembali.
Ayat Al-Qur’an
tentang penciptaan manusia
tersebut jika digambarkan
dengan pasangan titik dan garis
pada teori graf adalah sebagai berikut: Dalam proses
perjalanan kehidupannya, manusia
memiliki karakter yang bermacam-macam ada
yang baik dan
ada yang buruk,
sehingga semua manusia
pasti memiliki dosa. Dosa yang ada pada diri manusia dimisalkan sebagai
warna pada suatu graf, sehingga
diharapkan manusia memiliki warna yang minimum atau dosa yang sedikit sekali.
Hal tersebut dapat
dilakukan dengan cara
tidak selalu mengikuti
hawa nafsu, karena nafsu itulah manusia yang hidup di muka bumiini ada yang sempurna dan ada yang
tidak sempurna. Dalam
teori graf manusia
yang sempurna dan
tidak sempurna dimisalkan sebagai graf perfect dan graf tidak
perfect.
Graf perfect adalah graf yang
ditemukan oleh ClaudeBerge pada tahun 1960an.
Ia memperkenalkan graf perfect
sebagai graf yang memiliki bilangan clique dan bilangan khromatik
yang sama. Bilangan
clique didefinisikan sebagai
order maksimum dari subgraf komplit
pada graf G
(Marthin, 1980:51). Sedangkan
bilangan khromatik didefinisikan sebagai banyaknya warna terkecil
yangdiberikan pada titik-titik di graf G
sedemikian hingga untuk setiap dua titik
yang terhubung langsung mendapatkan warna yang berbeda (Rosen dalam Khotimah, 2006:3).
Kajian tentang
graf perfect saat
ini masih belum
begitu banyak dikenal
oleh orang. Berdasarkan
hal tersebut, maka
penulis mengambil judul
skripsi ini, yaitu: “Kajian tentang Graf Perfect ”.
1.2 Rumusan Masalah Berdasarkan latar belakang masalah di atas
dapat ditarik rumusan permasalahan yang
akan dibahas, yaitu
bagaimana langkah-langkah menentukan
suatu graf menjadi graf perfect.
1.3 Tujuan Penulisan Adapun
tujuan dari penulisan
ini adalah untuk
mengetahui langkah-langkah menentukan suatu graf menjadi graf perfect.
1.4 Batasan Masalah Untuk
tetap menjaga kedalaman
pembahasan materi, penulisan tugas
akhir ini dibatasi
pada Obyek kajian
graf kosong, graf
komplit, graf bipartisi
komplit, graf lintasan,
dan graf sikel
genap. Penulis hanya
membatasi pada beberapa
graf tersebut karena merupakan graf perfect.
Dalam teori graf, istilah yang dipakai belum
baku sepenuhnya. Untuk itu setiap pilihan istilah
dapat diterima asal
digunakan secara konsisten.
Istilah-istilah tersebut antara lain: 1.
Titik = titik = noktah = node = vertex 2. Sisi
= garis = edge.
1.5 Manfaat Penulisan Penulisan
karya ilmiah ini
pada dasarnya diharapkan dapat memberikan
manfaat terhadap beberapa pihak,
diantaranya: 1. Bagi Penulis -
Menambah wawasan dan ilmu pengetahuan tentang teori graf perfect.
2. Bagi Jurusan Matematika -
Sebagai bahan pustaka tentang kajian graf perfect.
1.6 Metode Penelitian 1.6.1
Pendekatan dan jenis penelitian Jenis dari
penelitian ini adalah
deskriptif kualitatif. Pendekatan
yang digunakan adalah pendekatan kualitatif dengan metode
kepustakaan.
Dalam
pendekatan deskriptif kualitatif
ini maka penulis
menggunakan metode penelitian
kepustakaan (Library Research).
Metode penelitian kepustakaan
yaitu penelitian yang
dilakukan di dalam
perpustakaan untuk mengumpulkan
data dan informasi.
Pengumpulan data dan
informasi tersebut dapat
dilakukan dengan bantuan bermacam material yang terdapat di ruang
perpustakaan seperti buku-buku dan dokumen yang ada.
1.6.2 Data dan sumber data Data
yang digunakan penulis
dalam rangka penyusunan skripsi ini
adalah datadata yang meliputi
bilangan-bilangan clique, bilangan khromatik, dan data-data lain yang sesuai.
Sumber data dalam penulisan
skripsi ini diperoleh melalui buku-buku antara lain Gary Chartrand dan Linda Lesniak (Graphs and
digraphs second edition) Robin J. Wilson dan
John J. Watkins
(Graph an Introductiory
Approach) dan sumber-sumber
lain yang relevan.
1.6.3 Tehnik Analisis data Dalam
menganalisis data, penulis
melakukan persiapan dengan
menghitung bilangan clique
dan bilangan khromatik
dari beberapa graf
yang diteliti. Beberapa
graf tersebut antara lain graf
kosong, graf komplit, graf bipartisi komplit, graf lintasan, dan graf
sikel genap. Selanjutnya
menyimpulkan apakah graf-graf
tersebut merupakan graf perfect
.
1.7 Sistematika Pembahasan Agar
penulisan skripsi ini
lebih terarah, mudah
ditelaah dan dipahami,
maka digunakan sistematika
pembahasan yeng terdiri
dari empat bab.
Masing-masing bab dibagi ke dalam beberapa subbab dengan rumusan
sebagai berikut: BAB I PENDAHULUAN Pendahuluan meliputi: latar belakang
permasalahan,rumusan masalah, tujuan penelitian, batasan
masalah, manfaat penelitian,
metode penelitian, dan sistematika
penulisan.
BAB II KAJIAN PUSTAKA Bagian
ini terdiri atas
konsep-konsep (teori-teori) yang
mendukung bagian pembahasan.
Konsep-konsep tersebut antara
lain berisi tentang
dasar-dasar teori sebagai
acuan dalam penulisan
skripsi ini, antara
lain teori mengenai graf perfect dan teori keagamaan berserta
relevansiantara keduanya.
BAB III PEMBAHASAN Pembahasan
berisi tentang analisis
graf kosong, graf
komplit, graf bipartisi komplit, graf lintasan, dan graf sikel genap
denganbeberapa pembuktian dari teorema-teorema
yang diperoleh dari pola suatu graf.
0 komentar:
Posting Komentar