BAB I
PENDAHULUAN 1.1
Latar Belakang Ada banyak
tuntutan yang harus
dilaksanakan o leh set i ap
muslim dala m kehidupan
di dunia ini ,
salah satunya adalah
keharusan menjalin hubungan
yang baik kepada
Allah (hablum minAllah),
hubungan yang baik
dengan manusia (hablum
minannas) dan hubungan
yang baik dengan
alam (hablum minal’alam).
Dal am keterkai tan
hubungan manusia dengan
Tuhan, manusia dengan manusia
dari gambaran tersebut
tersimpan fil o sofi bahwa
manusia t i dak dapat hidup sendi r i.
Manusia adalah Makhluk
sosi al yang artinya
ada keterhubunga n atau
gari s sebuah t imbal
balik ant ara satu
dengan l ainya. Hubungan
ant ara t i t i k satu
dengan t i t i k lain
yang dihubungkan dengan
sebuah garis (sisi)
i tulah arti dari sebuah
keterhubungan.
Matemat i ka merupakan
salah satu ilmu
yang erat kai tannya
dengan kehidupan. Secara
garis besar matemat i ka
bisa dibagi dalam
dua kategori yai t u matemat i ka
diskri t dan kont inu.
Salah satu bagian
dari matemat i ka diskri t
yang menarik adalah
teori graf . Disadari
atau t i dak, banyak
aplikasi teori graf
dalam kehidupan. Teori graf merupakan salah satu cabang matemat i ka yang mempelajari mengenai hubungan
himpunan t i dak kosong
y ang memuat elemenelemen
yang di sebut t i t i k dan suatu
daf t ar pasangan t i dak terurut elemen
i t u yang disebut sisi .
Banyak sekali
struktur y ang dapat
di representasi kan dengan graf
dan banyak masalah
yang dapat diselesaikan
dengan bantuan graf .
Jika t i t i kt i t i k tersebut
di asums ikan sebagai suatu
elemen dal am islam
yakni Allah dan ci
ptaanNya (Manusia dan
alam), maka suatu
si si dal am graf
dapat di asums ikan sebagai
hubungan ant ara t i t i kt i t i k tersebut.
Jadi dapat di pelajari
bagaimana hubungan ant ara
manusia dengan Allah,
manusia dengan sesamanya
dan j uga manusia
dengan alam secara
l ebih sederhana. Tak
kal ah menari knya jika
manusia mempelajari mengenai
masalah pewarnaan pada graf .
Banyak persoal an
yang mempunyai karakteri st i k sepert i
pewarnaan graf sehingga
membuat pewarnaan pada
graf ini menarik
unt uk di kaji lebih
dalam.
Misalnya dalam
mengatur sej umlah saluran
f rekuensi ke beberapa
pemancar sehingga interf erensi
dapat dijaga pada
level yang dapat
di t erima. Contoh y ang mungkin dapat
dilihat l angsung misalnya
menentukan j adwal ujian
sedemikian sehingga semua
mahasiswa dapat mengi kut i
ujian set i ap mata
kuliah yang di ambilnya
dengan waktu ujian
yang t i dak bertabrakan
ant ara satu mata
kulia h dengan mata kuliah yang
lain.
Masalah pewarnaan
di dalam graf
memiliki banyak variasi
dengan t i pe yang
berbeda. Ada bilangan
kromat i k dan pewarnaan
dengan teorem a Ramsey .
Ada t i ga
macam pewarnaan graf ,
yai tu pewarnaan t i t i k,
pewarnaan sisi , dan pewarnaan wilayah
(regi on). Dal am persoal an
pewarnaan graf , t i dak
hanya sekedar mewarnai
t i t i kt i t i k atau sisi
dengan warna berbeda
dari warna simpul atau
si si t etangganya saja,
namun juga dapat
menginginkan jumlah macam
warna yang digunakan sesediki
t mungkin.
Jumlah warna
minimum yang dibutuhkan
unt uk mewarnai graf
disebut bilangan kromat i k
( c ). Sebagai
contoh, bilangan kromat i k
dari graf lengkap m K dengan
m simpul (graf
sederhana yang set i ap
simpulnya memiliki sisi
ke semua simpul
lainnya), adal ah χ ( m K )
= m. Bilangan
kromat i k (chromatic number)
dari graf G,
dinyatakan dengan c
(G), adalah bilangan
m terkecil sehingga
G dapat di warnai
dengan m warna.
Biasanya warnawarna yang di
gunakan unt uk mewarnai
suatu graf dinyatakan
dengan 1, 2,
3, …, m. Jel
as bahwa c (G)
£ ( )
G V (Purwanto , 1998:73).
Pewarnaan t i t i k
pada graf G adal
ah pemberi an warna
unt uk seti ap t i t i k pada
graf sehingga t i dak
ada dua t i t i k
yang terhubung langsung
berwarna sama (Rosen
dalam Khot imah, 2006:3).
Pewarnaan sisi untuk
G adal ah pemberian warna
pada sisisisi G
sedemikian hingga set i ap
dua sisi yang
bertemu pada t i t i k yang sama mendapatkan warna berbeda (Wilson
dan Watkins, 1990:240).
Bahasan mengenai
pewarnaan pada graf
t i dak hanya dif okuskan
pada beberapa jenis
graf i t u sendir i ,
akan t etapi juga
dapat di aplikasikan pada kehidupan sehari hari yang
dapat membant u dan
memudahkan. Di ant aranya pada
pemasangan kabel tel ef o n,
pada masalah penjadwalan,
pewarnaan peta dan masih banyak lagi .
Beberapa kajian
terdahulu tentang pewarnaan
pada graf tertent u
t el ah dibahas pada
skripsi yang lain
sepert i Pewarnaan Ti t i k
dan Aplikasinya pada Penjadwalan Mata
Kuliah Jurusan Matemat i ka
o l eh Khot imah (2006),
Pewarnaan Ti t i k pada Graf
yang Berkai tan dengan
Si kel o l eh Gho f ur
(2008) dan Pewarnaa n pada
graf Buku &
graf Tangga tel ah
dikaji o l eh Wahyudi
(2008). Kajian ini dif
okuskan pada pencar i an
bilangan kromat i k dalam
pewarnaan t i t i k dan sisi pada graf
Pi ramida dan Berlian, serta membukti kannya.
0 komentar:
Posting Komentar