BAB I PENDAHULUAN
1.1 Latar Belakang Masalah yang sering kali
muncul di tengah-tengah kehidupan masyarakat terkadang
seringkali membutuhkan selesaian
dari disiplin ilmu,
dengan bantuan bahasa
lambang pada matematika
permasalahan tersebut lebih
mudah untuk dipahami, lebih mudah dipecahkan, atau bahkan dapat ditunjukkan
bahwa suatu persoalan tidak mempunyai
penyelesaian.
Oleh karena
itu suatu permasalahan
perlu dikaji dan
dianalisis dan kemudian dicari model matematikanya.
Menurut Abdul
Aziz (2006:v) matematika
adalah salah satu
ilmu pasti yang
mengkaji abstraksi ruang,
waktu, dan angka.
Matematika juga mendeskripsikan realitas
alam semesta dalam
bahasa lambang, sehingga
suatu permasalahan dalam
realitas alam akan
lebih mudah dipahami.
Alam semesta sendiri
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).
Salah satu
cabang matematika yang
banyak digunakan untuk menyelesaikan permasalahan
dalam kehidupan sehari-hari
adalah teori graf, karena teori-teorinya mudah
untuk diaplikasikan dalam
kehidupan sehari-hari, seperti
mencari jarak terpendek
untuk tukang pos
dalam menyampaikan surat, masalah penjadwalan, jaringan telekomunikasi,
ilmu komputer dan lain-lain.
Sejak masalah jembatan Konigsberg
direpresentasikan dengan graf Euler, teori graf
berkembang dengan pesat
sebagai cabang ilmu
matematika. Masalah jembatan Konigsberg adalah mengkinkah melewati
tujuh buah jembatan tepat satu kali dan
kembali lagi ke
titik asal keberangkatan
? Kemudian pada
tahun 1736 seorang
matematikawan Swiss, L.Euler,
adalah orang yang
pertama kali menemukan jawaban masalah itu, hingga akhirnya
Euler memodelkannya dalam bentuk graf
sederhana. Untuk menghormatinya, model graf tersebut diberi nama sirkuit Euler (cycle Euler).
(http://planetmath.org/encyclopedia/graphTheory.
diakses: 28 Desember 2007).
Gambar 1.1 sirkuit Euler 2 Graph G didefinisikan sebagai pasangan (V, E)
dengan V adalah himpunan tidak kosong
dan berhingga dari
objek-objek yang disebut
titik, dan E
adalah himpunan (mungkin
kosong) pasangan takberurutan
dari titik-titik berbeda
di V yang disebut sisi
(Miller, 2000:165). Banyaknya
unsur di V disebut
order dari G dan dilambangkan dengan p(G), dan banyaknya unsur di E
disebut ukuran dari G dan dilambangkan
dengan q(G). Jika
graph yang dibicarakan
hanya graph G, maka
order dan ukuran dari G
cukup masing-masing ditulis
p dan q
(Chartrand dan Leniak, 1986:4).
Secara global,
graf berfungsi sebagai
sarana pemodelan.
Pemodelan yang
dimaksud adalah membuat
suatu penyederhanaan terhadap masalah dengan cara mempresentasikan objek-
objek tersebut.
(http//en.wikipedia.org/wiki/Graph_theory.
diakses: 22 April 2009).
Teori graf
merupakan pokok bahasan
yang sudah tua
usianya namun memiliki
banyak terapan sampai
saat ini. Graf
digunakan untuk merepresentasikan objek- objek diskrit dan hubungan antara objek-objek
tersebut.
Representasi visual
dari graf adalah
dengan menyatakan objek
dengan simpul, noktah,
bulatan, titik, atau
vertex, sedangkan hubungan
antara objek dinyatakan dengan garis atau edge.
Salah satu
aplikasi yang berkaitan
dengan graf adalah
pewarnaan graf (graf colouring ) yang terdiri dari pewarnaan titik, sisi dan peta. pewarnaan pada graf
erat kaitannya dengan
penentuan bilangan kromatik
yaitu masalah menentukan banyaknya warna minimum
yang diperlukan untuk mewarnai suatu graf
. Bilangan kromatik
(chromatic number) dari
graf G, dinyatakan
dengan 3 (), adalah
bilangan n terkecil
sehingga G dapat
diwarnai dengan n
warna.
Biasanya warna –
warna yang digunakan untuk mewarnai suatu graf dinyatakan dengan 1, 2 , 3...,n. Jelas bahwa ()
≤ () ,
(Purwanto,1998 : 73).
Dalam pewarnaan
graf juga terdapat
rumusan atau aturan-aturan, Dimana rumusan
atau aturan –aturan
yang dimaksud adalah
bagaimana menentukan bilangan kromatik pada pewarnaan graf .
Bahasan mengenai pewarnaan graf dapat diaplikasikan
pada kehidupan sehari- hari yang dapat membantu dan memudahkan kita.
Diantaranya pada pemasangan
kabel telefon, pada
masalah penjadwalan, pewarnaan peta dan lain sebagainya.
Beberapa kajian
terdahulu tentang pewarnaan
pada graf tertentu
telah dibahas pada
karya tulis yang
lain, namun sebagian
besar hanya membahas tentang pewarnaan titik atau pewarnaan sisi
saja. seperti yang telah ki ta ketahui bahwa ada tiga macam pewarnaan pada graf yaitu
pewarnaan titik, pewarnaan sisi, 4 dan pewarnaan peta. karya tulis yang membahas
tentang ketiga macam pewarnaan juga telah
dibahas sebelumnya seperti
” Pewarnaan pada
graf buku dan
graf tangga” oleh kokok imam
wahyudi wijaya. Dari karya tulisnya tersebut diperoleh hasil ketiga macam pewarnaan graf tersebut.
Untuk selanjutnya
penulis tertarik untuk melanjutkan
meneliti tentang pewarnaan
pada graf dengan
menggunakan graf yang
berbeda dimana nantinya juga akan ditentukan bilangan kromatik pada
pewarnaan titik, sisi , dan peta pada graf Bipartisi
Komplit dan graf
tripartisi. Graf bipartisi
komplit (complete bipartite graph) adalah graf bipartisi dengan
himpunan partisi X dan
Y sehingga masing-masing titik di X dihubungkan dengan
masing-masing titik di Y oleh tepat satu
sisi. Jika |X| = m dan
|Y| = n,
maka graf bipartisi tersebut dinyatakan dengan Km,n .
(Purwanto, 1998:22). Oleh
karena itu penulis
merumuskan judul untuk skripsi ini
, yakni ”
Pewarnaan pada Graf
Bipartisi Komplit Km,n dan Graf Tripartisi
T2, n-1, n dengan m, n adalah bilangan asli
” .
1.2 Rumusan Masalah Berdasarkan latar
balakang tersebut, maka
rumusan masalah dalam penulisan
ini antara lain : 1. Bagaimana menentukan
bilangan kromatik pewarnaan
titik pada graf bipartisi
komplit Km,n dan graf tripartisi T2, n-1,
n . ? 2.
Bagaimana menentukan bilangan
kromatik pewarnaan sisi
pada graf bipartisi komplit Km,n dan graf tripartisi T2, n-1, n . ? 5 3. Bagaimana
menentukan bilangan kromatik
pewarnaan peta pada
graf bipartisi komplit Km,n dan tripartisi T2, n-1, n . ? 1.3
Tujuan Penelitian Berdasarkan
rumusan masalah diatas,
maka tujuan penulisan
skripsi ini antara lain : 1. Menjelaskan
cara menentukan bilangan
kromatik perwarnaan titik
pada graf bipartisi komplit Km,n dan graf tripartisi T2, n-1, n .
2. Menjelaskan
cara menentukan bilangan
kromatik perwarnaan sisi
pada graf bipartisi komplit Km,n dan graf tripartisi T2, n-1, n .
3. Menjelaskan
cara menentukan bilangan
kromatik perwarnaan peta
pada graf bipartisi komplit Km,n dan graf tripartisi T2, n-1, n .
1.4 Batasan Masalah Pembahasan mengenai
pewarnaan pada graf
bipartisi komplit K(m,n) dan graf
tripartisi T2, n-1, n
.
dalam penulisan ini
dibatasi pada m,
n ≥ 2. Hal ini dilakukan karena
berdasarkan hasil percobaan
penulis, ternyata untuk
m, n = 1 memiliki pola yang berbeda dengan pola untuk
m, n bilangan asli lainnya.
1.5 Manfaat Penulisan 1. Bagi
penulis Penelitian ini
digunakan sebagai tambahan
informasi dan wawasan
pengetahuan tentang teori
graf, khususnya tentang
pewarnaan pada graf bipartisi
komplit.
6 2. Bagi
lembaga Hasil penelitian ini dapat digunakan sebagai tambahan kepustakaan
yang dijadikan sarana
pengembangan wawasan keilmuan khususnya
di jurusan matematika untuk mata kuliah
Teori Graf.
0 komentar:
Posting Komentar