## PEWARNAAN GRAF PADA PENYUSUNAN JADWAL PERKULIAHAN DI POLITEKNIK AKAMIGAS PALEMBANG

## Maryana. 1
1) Program Studi Teknik Pertambangan Batubara, Politeknik Akamigas Palembang

## Abstrak
Awal  semester  akademik  merupakan  permasalahan  yang  cukup  rumit  karena  selalu disibukkan  dengan  rutinitas  yang  seharusnya  sudah  mendapatkan  solusi.  Jadwal  yang sering bentrok antara satu mata kuliah dengan mata kuliah yang lain merupakan satu dari beberapa  permasalahan  yang  terjadi.  Jika  dilihat  secara  individu,  penyusunan  jadwal secara  manual  bukanlah  hal  yang  sulit  karena  adanya  toleransi  waktu  dan  jadwal perseorangan  yang  berbeda-beda.  Akan  menjadi  hal  yang  rumit  jika  masalah  tersebut melibatkan  banyak  orang  dengan  berbagai  kesibukan  masing-masing.  Salah  satu  solusi dari  permasalahan  tersebut  adalah  dengan  teknik  pewarnaan  graf  (Graph  Coloring), dimana teknik ini akan membahas mengenai solusi dari permasalahan dalam penyusunan jadwal  kuliah  dengan  memanfaatkan  algoritma  Welch-Powell  sehingga  diperoleh  solusi yang optimal.
Kata kunci: Graf, Jadwal dan Pewarnaan Graf

## Abstract
Early academic semester is a problem that is quite complicated because it is always busy with a routine that should have been a solution. Schedules frequent clashes between subject  with  the  other  subject  is  one  of  several  problems  that  occur.  When  viewed individually, preparation of schedules manually is not a difficult thing for their tolerance and timeline different. It will be a tricky thing if the issue involves a lot of people with a variety  of  activities.  One  of  the  solutions  to  these  problems  is  with  a  graph  coloring technique, where this technique will discuss the solution of problems in the preparation of class schedules by using Welch-Powell algorithm in order to obtain an optimal solution.
Keyword: Graph, Schedule and Graph Coloring
I. Pendahuluan

## 1.1  Latar Belakang
Teori  graf  merupakan  salah  satu  cabang ilmu  matematika  yang  menarik  untuk  dibahas karena  berkaitan  dengan  kehidupan  sehari-hari. Saat  ini  teori  graf  berkembang  pesat  karena keunikan  dan  banyak  sekali  aplikasinya. Keunikan  teori  graf  adalah  kesederhanaan pokok bahasan yang dipelajarinya, karena dapat disajikan  sebagai  simpul  ( vertex )  dan  busur ( edge ).
Salah  satu  cabang  teori  graf  yang  biasa digunakan  dalam  memodelkan  permasalahan adalah  pewarnaan  graf (graph  coloring) . Pewarnaan  graf,  yaitu  dengan  memberikan warna  pada  elemen  graf  yang  akan  dijadikan subjek dalam memahami constraint
permasalahan.  Ada  tiga  macam  persoalan pewarnaan  graf    yaitu  pewarnaan  simpul (vertex) , pewarnaan busur (edge) , dan
pewarnaan wilayah (region) . Pewarnaan simpul adalah  teknik  pemberian  warna  untuk  setiap simpul pada graf sehingga tidak ada dua simpul yang  berhubungan  langsung  yang  berwarna sama.  Aplikasi  dari  teknik  ini  telah  banyak diterapkan dalam berbagai bidang, salah satunya adalah  penyusunan  jadwal  perkuliahan.Pada setiap  awal  semester  bagian  akademik  di Politeknik Akamigas Palembang selalu disibukkan  dengan  permasalahan  penyusunan jadwal  perkuliahan  yang  kadang  merupakan persoalan  yang  rumit  karena  masih  sering terjadi  permasalahan,  misalnya  jadwal  yang bertabrakan. Hal ini disebabkan karena keterbatasan ruang kuliah, dosen mengajar lebih dari satu mata kuliah, dan juga mahasiswa yang mengambil  beberapa  mata  kuliah  sekaligus dalam satu semester. Untuk mengatasi permasalahan  tersebut  maka  dibuat  teknik penjadwalan  dengan  pewarnaan  simpul  graf.
Pertemuan  kuliah  yang  meliputi  mata  kuliah, dosen,  dan  ruang  kuliah  diidentifikasikan sebagai  sebuah  simpul.  Setiap  simpul  dimana mata kuliahnya diajarkan oleh dosen yang sama atau diberikan pada ruang yang sama dihubungkan  dengan  sebuah  busur  yang  berarti mata  kuliah  tersebut  tidak  dapat  dilakukan secara  bersamaan.  Fungsi  objektif  dalam pewarnaan simpul graf  meminimumkan konflik pewarnaan, yaitu simpul-simpul yang bertetangga yang berwarna sama. Hasil pewarnaan  graf  merupakan  solusi  penyusunan jadwal  perkuliahan  dimana  simpul-simpul  yang berwarna  sama  merepresentasikan  mata  kuliah dapat dilaksanakan dalam waktu yang bersamaan  dan  jumlah  warna  yang  didapat merupakan jumlah sesi perkuliahan.
1.2 Perumusan Masalah
Permasalahan yang dibahas pada penelitian  ini  adalah  bagaimana  mengatasi masalah  penyusunan  jadwal  perkuliahan  di Politeknik  Akamigas  Palembang,  khususnya  di Program  Studi  Teknik  Pertambangan  Batubara dengan  menggunakan  teknik  pewarnaan  simpul graf.

## II. Dasar Teori
2.1   Definisi Graf
Graf adalah  pasangan  himpunan
dengan adalah  himpunan  tidak  kosong  dari simpul dan   adalah himpunan dari busur yang menghubungkan  sepasang  simpul  dalam  graf tersebut.

## 2.2 Jenis-Jenis Graf
Graf memiliki  busur  ganda ( multiple edges )  apabila  terdapat  beberapa  busur  yang menghubungkan  pasangan  simpul  yang  sama. Busur  yang  menghubungkan  simpul  yang  sama disebut gelung ( loop ). Graf yang tidak memiliki gelung  atau  busur  ganda    disebut  graf sederhana,  sedangkan  graf  yang  memiliki gelung  atau  busur  ganda  disebut  graf  tidak sederhana (Watkins and Wilson, 1990).
Graf  lengkap  dengan simpul  yang dinotasikan adalah  graf  sederhana  yang memuat  tepat  satu  busur  antara  tiap  pasang simpul yang berbeda pada graf.
Pada  Gambar  1  diberikan  contoh  graf lengkap .
v 1 v 2 v 3 v 4
Gambar 1. Contoh graf lengkap
Graf bipartit adalah graf sederhana   yang himpunan simpulnya dapat dipisah menjadi dua himpunan dan yang  saling  lepas sedemikian  sehingga  setiap  busur  pada menghubungkan  satu  simpul  pada dengan
satu  simpul  pada .  Pada  Gambar  2  diberikan contoh graf bipartit.
Gambar 2. Contoh graf  bipartit

## 2. 3.  Pewarnaan Graf
Dalam  teori  graf,  pewarnaan  graf  adalah memberikan warna pada elemen graf yang akan dijadikan  subjek  dalam  memahami constraint permasalahan.  Ada  tiga  macam  persoalan pewarnaan graf (graph coloring) , yaitu pewarnaan  simpul (vertex) ,  pewarnaan  busur (edge) ,  dan  pewarnaan  wilayah (region) .
Pewarnaan  simpul  maupun  pewarnaan  busur pada  graf  merupakan  salah  satu  topik  dalam teori graf yang kaya dengan aplikasi (Budayasa, 2007).  Selanjutnya  akan  dibahas  pewarnaan simpul.
Pewarnaan  simpul  adalah  memberikan warna pada simpul-simpul pada graf sedemikian  sehingga  setiap  dua  simpul  yang bertetangga (berhubungan langsung) mempunyai  warna  yang  berbeda.  Dua  simpul yang  bertetangga  (berhubungan  langsung) adalah  dua  simpul  yang  dihubungkan  oleh sebuah busur. Pada Gambar 3 akan ditunjukkan dua simpu yang bertetangga.
v 1 v 3 v 5 v 2 v 4
v ₁ •                                           • v ₂
v 4 •                                        • v 3
Gambar 3. Dua Simpul Bertetangga
Simpul  v 1 bertetangga  dengan  simpul  v 2 dan v 4 dan tidak bertetangga dengan simpul v 3 , berarti  simpul  v 1 tidak  boleh  berwarna  sama dengan  simpul  v 2 dan  v 4 tetapi  boleh  berwarna sama dengan simpul v 3 .
Dalam  pewarnaan  graf,  tidak  hanya sekedar mewarnai  simpul-simpul dengan warna yang  berbeda  dari  warna  simpul  yang bertetangga  saja,  tetapi  kita  juga  menginginkan jumlah macam warna yang digunakan seminimum mungkin. Dan pewarnaan simpul di busur  dibatasi  pada  graf  sederhana  atau  graf yang tidak mempunyai sisi rangkap atau gelung. Hal  ini  akan  ditunjukkan  pada  Gambar  4  di bawah ini.
Gambar 4. Bilangan Kromatik Graf G
Jumlah  warna  minimum  yang  dapat digunakan  untuk  mewarnai  simpul  pada    suatu graf  G  disebut  bilangan  kromatik  graf  G,  yang dilambangkan       dengan χ(G). Suatu graf yang mempunyai bilangan   kromatis k dilambangkan dengan  χ(G) =  k.  Berarti  graf  G  pada  contoh  2 di  atas  mempunyai  bilangan  kromatik  =  3  atau χ(G) = 3.

## 2.4 Algoritma Pewarnaan Simpul pada Graf
Pewarnaan  simpul  pada  graf  dapat dilakukan  dengan  menggunakan  Algoritma
Welch-Powell ,  dengan  langkah  –  langkah sebagai berikut :
1. Urutkan  simpul-simpul  dari  graf  G  dalam derajat menurun, d(V ₁ )    d(V ₂ )    d(V ₃ )    .    .    .      d(Vn) (boleh memakai tabel)
2.   Gunakan warna pertama (I) untuk mewarnai simpul  pertama  (yang  mempunyai  derajat
tertinggi  (v ₁ ))  dan  simpul  yang  tidak bertetangga dengan v ₁
3.   Gunakan warna ke dua (II) untuk  mewarnai simpul dengan derajat tertinggi berikutnya.
4.    Ulangi  penambahan  warna  –  warna  sampai semua simpul terwarnai.

## 2.5  Penjadwalan Perkuliahan
Menurut  Kamus  Besar  Bahasa  Indonesia
(1991),  jadwal  adalah  pembagian  waktu berdasarkan rencana pengaturan kerja.
Sedangkan  penjadwalan  adalah  proses,  cara, perbuatan  menjadwalkan  atau  memasukkan  di jadwal.  Salah  satu  tingkatan  pendidikan  yang mengalami  permasalahan  penjadwalan  adalah perguruan  tinggi  dalam  hal  ini  penjadwalan perkuliahan.
Komponen dari masalah penjadwalan perkuliahan (Syadid, 2007) adalah:
1) Kelompok dari mahasiswa
2) Kelompok dari pengajar
3) Kelompok dari mata kuliah
4) Kelompok dari ruangan 5) Kelompok  dari  slot  waktu  yang  telah ditentukan. Aktivitas perkuliahan merupakan gabungan dari kelompok  mahasiswa,  dosen  yang  mengajar,
dan  mata  kuliah  yang  diajarkan.  Permasalahan yang  sebenarnya  dihadapi  dalam  kasus  ini adalah  permasalahan  penempatan  beberapa aktivitas  perkuliahan  yang  ada  ke  dalam dimensi  slot  waktu  dan  ruangan  yang  telah ditentukan  sehingga  diperoleh  solusi  yang paling optimal.

## III. Metode Penelitian
Metode  yang  digunakan  dalam  penelitian ini  adalah  studi  literatur  yaitu  mengumpul informasi  baik  dari  buku  atau  jurnal  yang berkaitan  dengan  metode  pewarnaan  graf.  Di samping  itu  juga  digunakan  data-data  dari Program  Studi  Teknik  Pertambangan  Batubara seperti  sebaran  mata  kuliah,  tingkatan  semester yang ada, ruang kuliah yang ada.
IV. Hasil dan Pembahasan
4.1 Pewarnaan Graf pada Semester Ganjil
Hasil  pewarnaan  graf  berdasarkan  mata kuliah dan dosen yang mengajar  pada semester ganjil  dapat  ditunjukkan  pada  Gambar  5  di bawah ini.
Vol 6. No.2 Desember 2015
Gambar  5. Pewarnaan  Graf  pada  Semester Ganjil
Gambar  5  dapat  dilihat  terdapat  4  warna, yaitu  merah,  biru,  kuning  dan  hijau  sehingga bilangan  kromatik  (G)  =  4.  Pada  gambar  diatas tidak  semua  dosen  dan  mata  kuliah  disajikan tapi hanya untuk dosen yang mangajar beberapa mata  kuliah  saja  karena  mata  kuliah  lain  dan dosen  yang  mengajarnya  tidak  akan  menimbul masalah  dalam  penjadwalan.  Dari  Gambar  5 dapat  ditarik  kesimpulan  bahwa  mata  kuliah yang diwakili oleh simpul, yang berwarna sama dapat dijadwalkan pada waktu yang sama yaitu
a. Warna  merah  yaitu  mata  kuliah  Tambang Bawah  Tanah  dan  Praktikum  Eksplorasi batubara.
b. Warna biru untuk mata kuliah Geologi dan Eksplorasi batubara
c. Warna kuning untuk mata kuliah Praktikum Geologi, Pengelolaan Lingkungan  Pertambangan  dan  Regulasi Tambang  serta  mata  kuliah  Praktikum Fisika
d. Warna  hijau  diwakili  oleh  mata  kuliah Menggambar  Teknik  dan  Manajemen Tambang.

## 4.2 Pewarnaan Graf pada Semester Genap
Hasil  pewarnaan  graf  berdasarkan  mata kuliah dan dosen yang mengajar  pada semester genap  dapat  ditunjukkan  pada  Gambar  5.4  di bawah ini.
Gambar  6. Pewarnaan  Graf  pada  Semester Genap
Dari  Gambar  6  bisa  dilihat  terdapat  5 warna,  yaitu  merah,  biru,  kuning,  hijau  dan hitam  sehingga  bilangan  kromatiknya  (G)  =  5.
Warna simpul-simpul yang berbeda menyatakan bahwa  waktu  kuliah  bisa  dilaksanakan  dihari yang sama, yaitu: a. Warna  merah  untuk  mata  kuliah  praktikum pemercontohan  dan  analisa  batubara,  dan mata kuliah teknik peledakan. b. Warna biru untuk mata kuliah pemercontohan dan analisa batubara c. Warna  kuning  untuk  mata  kuliah  teknologi pemanfaatan  dan  konversi  batubara,  dan mata kuliah drainase tambang.
d. Warna  hijau  untuk  mata  kuliah  praktikum teknologi pemanfaatan dan konversi batubara,  dan  mata  kuliah  praktek  tambang bawah tanah.
e. Warna  hitam  untuk  mata  kuliah  metode penulisan ilmiah.

## V. Kesimpulan
Dari  hasil  penelitian  dan  pembahasan yang  dilakukan,  maka  dapat  ditarik  kesimpulan bahwa :
1. Salah satu solusi untuk masalah penyusunan jadwal  adalah  dengan  metode  pewarnaan graf.
2. Langkah  awal  penyelesaian  adalah  dengan memetakan  suatu  jadwal  ke  dalam  graf  lalu menentukan bilangan kromatik graf tersebut.
3. Algoritma  Welch-Powell  dapat  membantu dalam proses pewarnaan graf

## DAFTAR PUSTAKA
Budayasa,  Ketut.  2007. Teori  Graph  dan Aplikasinya. Surabaya : UNESA. Depdikbud.  1991. Kamus  Besar  Bahasa Indonesia . Jakarta : Balai Pustaka. Jusuf,  Heni.  2009. Pewarnaan  Graph  Pada Simpul Untuk Mendeteksi Konflik Penjadwalan  Kuliah .  Seminar  Nasional Aplikasi Teknologi Informasi 2009. ISSN:1907-5022. Liang,  Z.  dan  Bai,  Z.  (2009).  On  the  odd harmonious graph with applications. Journal  Appl.  Math.  Comput .,  29,  105- 116. Munir,  Rinaldi.  2001. Matematika  Diskrit . Bandung : Informatika Bandung. Syadid,  M.  2005. Penjadwalan  Perkuliahan Menggunakan  Algoritme  Genetika .  Bogor
: Institut Pertanian Bogor.
Wibisono,  Samuel.  2008. Matematika  Diskrit Edisi  2 .  Yogyakarta  :  Graha  Ilmu