PENDAHULUAN
1.1 Latar Belakang
Teori graph merupakan salah satu studi terhadap bidang matematika yang diperkenalkan pertama kali oleh seorang ahli matematika asal Swiss, Leonhard Euler 1736 (Deo,1974). Ide besarnya muncul sebagai upaya penyelesaian masalah jembatan Konigsberg. Dari permasalahan itu, akhirnya Euler mengembangkan beberapa konsep mengenai teori graph. Materi-materi yang terdapat dalam teori graph itu sendiri adalah ilmu yang mempelajari mengenai logika dari persoalan yang berhubungan dengan himpunan dan relasi binary (Hariyanto, 2003).
Graph merupakan salah satu model matematika yang kompleks dan cukup sulit, akan tetapi bisa juga menjadi solusi yang sangat bagus untuk masalah tertentu. Maka dari itu representasi dari suatu graph bergantung dari sifat data dan operasi yang dilakukan terhadap data dari sebuah kasus tertentu. Dalam kehidupan sehari-hari banyak sekali persoalan yang diimplementasikan dengan graph. Bidang-bidang yang menggunakan penerapan graph antara lain switchig network, coding theory, electric analysis, operation research, aljabar, computer science dan kimia (Deo, 1974).
Keunikan teori graph adalah kesederhanaan pokok bahasan yang dipelajarinya, karena dapat disajikan dengan titik (simpul atau vertex) dan garis (sisi atau edge). Meskipun pokok bahasan dari topik-topik teori graph sangat sederhana tetapi isi di dalamnya belumlah tentu sesederhana itu.
1.2 Tujuan Penulisan
Untuk memecahkan masalah penjadwalan kuliah, meminimalkan banyaknya warna yang digunakan untuk mewarnai setiap simpul, memaksimumkan fasilitas perkuliahan yang telah disediakan kampus dan mencegah terjadinya bentrokan waktu kuliah antara fakultas yang satu dengan yang lainnya
PEMBAHASAN
Graf
- Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.
- Gambar di bawah ini sebuah graf yang menyatakan peta jaringan jalan raya yang menghubungkan sejumlah kota di Provinsi Jawa Tengah.
 |
- Sejarah Graf: masalah jembatan Königsberg (tahun 1736)
 |  | ||
Gambar 1. Masalah Jembatan Königsberg
- Graf yang merepresentasikan jembatan Königsberg:
Simpul (vertex) à menyatakan daratan
Sisi (edge) à menyatakan jembatan
· Bisakah melalui setiap jembatan tepat sekali dan kembali lagi ke tempat semula?
Definisi Graf
Graf G = (V, E), yang dalam hal ini:
V = himpunan tidak-kosong dari simpul-simpul (vertices)
= { v1 , v2 , ... , vn }
E = himpunan sisi (edges) yang menghubungkan sepasang
simpul
= {e1 , e2 , ... , en }
 |
G1 G2 G3
Gambar 2. (a) graf sederhana, (b) graf ganda, dan (c) graf semu
Contoh 1. Pada Gambar 2, G1 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) }
G2 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) } = { e1, e2, e3, e4, e5, e6, e7}
G3 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) }
= { e1, e2, e3, e4, e5, e6, e7, e8}
- Pada G2, sisi e3 = (1, 3) dan sisi e4 = (1, 3) dinamakan sisi-ganda (multiple edges atau paralel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3.
- Pada G3, sisi e8 = (3, 3) dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama.
Jenis-Jenis Graf
· Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:
1. Graf sederhana (simple graph).
Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. G1 pada Gambar 2 adalah contoh graf sederhana
2. Graf tak-sederhana (unsimple-graph).
Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph). G2 dan G3 pada Gambar 2 adalah contoh graf tak-sederhana
· Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:
1. Graf berhingga (limited graph)
Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.
2. Graf tak-berhingga (unlimited graph)
Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga.
- Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:
1. Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Tiga buah graf pada Gambar 2 adalah graf tak-berarah.
2. Graf berarah (directed graph atau digraph)
 |
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Dua buah graf pada Gambar 3 adalah graf berarah.
(a) G4 (b) G5
Gambar 3 (a) graf berarah, (b) graf-ganda berarah
Tabel 1 Jenis-jenis graf [ROS99]
| Jenis | sisi | Sisi ganda dibolehkan? | Sisi gelang dibolehkan? |
| Graf sederhana Graf ganda Graf semu Graf berarah Graf-ganda berarah | Tak-berarah Tak-berarah Tak-berarah Bearah Bearah | Tidak Ya Ya Tidak Ya | Tidak Tidak Ya Ya Ya |
1. Contoh Terapan Graf
1. Rangkaian listrik.
 |
(a) (b)
2. Isomer senyawa kimia karbon
 |
metana (CH4) etana (C2H6) propana (C3H8)
3. Transaksi konkuren pada basis data terpusat
Transaksi T0 menunggu transaksi T1 dan T2
Transaksi T2 menunggu transaksi T1
Transaksi T1 menunggu transaksi T3
Transaksi T3 menunggu transaksi T2
 |
4. Pengujian program
read(x);
while x <> 9999 do
begin
if x < 0 then
writeln(‘Masukan tidak boleh negatif’)
else
x:=x+10;
read(x);
end;
 |
writeln(x);
Keterangan: 1 : read(x) 5 : x := x + 10
2 : x <> 9999 6 : read(x)
3 : x < 0 7 : writeln(x)
4 : writeln(‘Masukan tidak boleh negatif’);
 |
5. Terapan graf pada teori otomata [LIU85].
Mesin jaja (vending machine)
Keterangan:
a : 0 sen dimasukkan
b : 5 sen dimasukkan
c : 10 sen dimasukkan
d : 15 sen atau lebih dimasukkan
2. Persoalan Tukang Pos Cina
Persoalan tentang tukang pos Cina pertama kali dikemukakan oleh Mei Ko Kwan, seorang Matematikawan Cina, pada tahun 1962 [2]. Persoalan ini adalah persoalan yang banyak dihadapi para tukang pos, yaitu tentang bagaimana seorang tukang pos akan mengantarkan sura-surat yang dibawanya ke alamat-alamat sepanjang jalan di suatu daerah. Ia harus merencanakan rute perjalanannya agar ia hanya melewati setiap ruas jalan tepat sekali dan kembali lagi ke tempat keberangkatannya.
Dalam menyelesaikan persoalan tukang pos ini, teori-teori graf sangatlah berguna. Dalam graf ada yang disebut simpul dan ada yang disebut sisi. Dalam persoalan tukang pos, setiap ruas jalan yang ada dinyatakan dengan sisi, sedangkan setiap persimpangan dinyatakan dengan simpul. Selain itu, menyelesaikan persoalan tukang pos Cina mau tidak mau juga akan memakai metode Euler, yaitu dalam menentukan apakah jalan yang harus dilewati tukang pos merupakan lintasan Euler, sirkuit Euler, atau bukan kedua-duanya.
Pembuatan jalur angkutan kota tidak jauh berbeda dengan persoalan tukang pos Cina. Persoalan tukang pos Cina adalah bagaimana mengantarkan surat-surat yang dibawa ke alamat-alamat sepanjang jalan, sedangkan persoalan jalur angkutan umum adalah bagaimana sang supir angkot mengantarkan para penumpang yang alamatnya tersebar di sepanjang jalan. Persamaan lainnya, sang tukang pos harus merencanakan rute perjalanan agar ia hanya melewati setiap ruas jalan tepat sekali, begitu juga dengan supir angkot. Ia juga harus melewati setiap ruas jalan tepat sekali agar tidak boros bensin dan agar para penumpang bisa lebih cepat tiba di tujuannya.Tetapi ada sedikit perbedaan antara permasalahan jalur angkutan kota dengan persoalan tukang pos Cina. Pada persoalan tukang pos Cina, tukang pos harus kembali ke tempat semula ketika ia sudah selesai mengantarkan semua surat-suratnya sehingga akan membentuk suatu sirkuit Euler. Sedangkan pada pembuatan jalur angkutan kota, supir angkot tidak kembali lagi ke tempat asalnya, tetapi ia menuju ke terminal atau pemberhentian yang lain sehingga akan membentuk suatu lintasan Euler.
3. Pewarnaan Graf
Pewarnaan graph tidak hanya sekedar mewarnai simpul-simpul dengan warna yang berbeda saja, namun juga menginginkan jumlah macam warna
yang digunakan sesedikit mungkin. Dalam hal ini jenis graph yang digunakan adalah graph sederhana. Persoalan yang mempunyai karakteristik seperti
pewarnaan graph ialah menentukan jadwal kuliah. Dengan menggunakan prosedur backtraking seperti pada gambar 3. Data yang digunakan sebagai contoh sampel adalah data 22 ruangan perkuliahan pada blok IV Universitas Nasional. Dimana ruangan tersebut masing-masing akan digunakan secara optimal, agar setiap matakuliah dapat berlangsung tanpa mengalami bentrok. Pada Tabel 1 memperlihatkan bahwa terdapat 22 ruangan yang akan digunakan untuk setiap hari terhadap ship yang ada. Angka 1 pada elemen (i,j) berarti bahwa ruangan i sudah terisi, sedangkan 0 menyatakan ruangan i
kosong. Prosedur perwarnaan graph dapat di lihat pada gambar 2.
Ruang Kuliah dan Hari Penyelesaian persoalan dalam menentukan jadwal kuliah sama dengan menentukan bilangan kromatis. Dari data tabel 1. ruangan dan waktu di atas dibuat matrik adjacency seperti terlihat pada gambar 4 yaitu matriks simetris yang menyatakan keterhubungan antara ruangan dengan waktu. Dari matriks adjacency tersebut dapat digambarkan sebuah graph yang telah disesuaikan dengan keterhubungannnya. Simpul-simpul pada graph menyatakan ruangan, sisi yang menghubung kan dua buah simpul menyatakan adanya matakuliah yang sedang berlangsung di ruangan tersebut. Berdasarkan gambar 4 dapat dilihat bahwa apabila terdapat dua buah simpul dihubungkan oleh sisi, maka kedua ruangan tersebut tidak dapat digunakan untuk tempat perkuliahan pada waktu yang sama. Warna-warna yang berbeda dapat diberikan pada simpul graph yang menunjukan bahwa waktu perkuliahan berbeda. Penulis menginginkan jadwal kuliah sesedikit mungkin untuk memudahkan pelaksanaannya.
Untuk itu penulis harus menentukan banyak bilangan kromatis yang digunakan untuk memiliki warna yang sama, sehingga masing-masing matakuliah tersebut dapat dilakukan tanpa mengalami bentrok. Banyak warna yang dipakai untuk mewarnai setiap simpul pada suatu graph ditentukan dari matrik adjacency. Pada gambar 5 berikut adalah graph yang sudah diwarnai. Graph yang sudah di warnai dari penjelasan mengenai banyak warna yang digunakan dalam mewarnai simpul pada graph dapat dikatakan bahwa tidak semua simpul memiliki warna yang sama. Hal itu juga dapat dijelaskan bahwa untuk simpul-simpul yang memiliki warna yang sama berarti ruangan-ruangan tersebut dapat digunakan untuk perkuliahan pada waktu yang bersamaan.
KESIMPULAN
Jadwal kuliah yang direpresentasikan dengan menggunakan graph seperti diatas dengan banyak warna yang digunakan untuk mewarnai simpul yang saling bertetangga. Hal itu juga menjelaskan bahwa jika data semakin banyak maka bilangan kromatis akan semakin besar. Masalah penjadwalan yang digunakan berhubungan dengan ruangan dan waktu perkuliahan sebagai constrain yang ada. Ide dasarnya membentuk sebuah graph dari banyak
constrain yang ada sedemikian hingga banyaknya warna yang digunakan untuk mewarnai setiap simpul yang berhubungan seminimum mungkin.
Dengan adanya pewarnaan graph dapat mencegah terjadinya bentrok pemakain ruang kuliah. Pewarnaan graph tersebut di buat dengan meminimalkan warna yang akan digunakan.
DAFTAR PUSTAKA
Kenny Enrich – NIM : 13506111
Program Studi Teknik Informatika, Institut Teknologi Bandung
Jl. Ganesha 10, Bandung
E-mail : if16111@students.if.itb.ac.id
Heni Jusuf
Teknik Informatika, Fakultas Teknologi Komunikasi dan Informatika, Universitas Nasional
Jl. Sawo Manila, Pejaten Pasar Minggu, Jakarta Selatan 12520
Telp. (021) 7806700, Faks. (021) 7891753
E-mail: henijusuf@yahoo.com
Tidak ada komentar:
Posting Komentar