Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th
PENERAPAN PEWARNAAN GRAF MENGGUNAKAN ALGORITMA WELCH-POWELL UNTUK MENENTUKAN JADWAL BIMBINGAN MAHASISWA

## (Implementation of Graph Colouring Using Welch-Powell Algorithm to Determine Student Mentoring Schedule)
Ariestha Widyastuty Bustan 1 , M Rais Salim 2*
1 Program Studi Matematika,  Fakultas MIPA, Universitas Pasifik Morotai, Jl Siswa Darame, Kec Morotai Selatan, Kabupaten Pulau Morotai, Maluku Utara, 97771, Indonesia
2 Program Studi Pendidikan Guru Sekolah Dasar,  Fakultas KIP, Universitas Pasifik Morotai, Jl Siswa Darame, Kec Morotai Selatan, Kabupaten Pulau Morotai, Maluku Utara, 97771, Indonesia
* E - mail : mraissalim@yahoo.com

## ABSTRAK
Program  Studi  Pendidikan  Sekolah  Dasar  adalah  salah  satu  program  studi  yang  tak  jarang memiliki  masalah  dalam  proses  penjadwalan,  terutama  jadwal  bimbingan  mahasiswa  karena jumlah  mahasiswa  yang  banyak  dalam  satu  periode  bimbingan.  Untuk  mengatasi  kendala tersebut,  diperlukan  proses  persiapan  jadwal  alternatif  untuk  mengefektifkan    waktu bimbingan siswa. Salah satu cara untuk mempersiapkan jadwal yang dapat digunakan adalah dengan  menerapkan  konsep  pewarnaan  titik  pada  grafik  menggunakan  algoritma  Welch Powell. Pewarnaan graf dengan menggunakan algoritma welch powell merupakan salah satu teknik  dalam  penyusunan  jadwal.  Khusunya  pada  saat  menyusun  jadwal  bimbingan mahasiswa di suatu program studi. Titik-titik pada graf direpresentasikan sebagai mahasiswa yang akan melakukan bimbingan, sedangkan sisi yang menghubungkan dua titik menyatakan jika  dua  titik  tersebut  atau  dua  mahasiswa    memiliki  satu  dan/atau  dua  dosen  pembimbing yang sama. Metode penelitian yang digunakan adalah metode penelitian studi literatur.  Hasil dari  penelitian  ini  menunjukkan  bahwa  pewarnaan    graf  dengan  menggunakan  algoritma welch  powell  dapat  diterapkan  untuk  penyusunan  jadwal  bimbingan  mahasiswa  PGSD  di Universitas pasifik Morotai.
Kata kunci: algoritma welch-powell, graf, pewarnaan titik graf, penjadwalan

## ABSTRACT
The Primary School Education Study Program is one of the study programs that has problems in  the  schedule  preparation  process,  especially  the  student  guidance  schedule  because  of  the large  number  of  students  in  the  guidance  period.  To  overcome  the  obstacles  in  the  schedule preparation  process,  an  alternative  schedule  preparation  process  is  needed  to  streamline  the time  of  student  guidance.  One  way  to  prepare  a  schedule  that  can  be  used  is  to  apply  the concept  of  point  coloring  on  the  graph  using  the  Welch  Powell  algorithm.  Graph  colouring using the Welch-Powell algorithm is one of the schedule preparation techniques. Especially for arrangi ng student guidance schedules in a study program. The vertex on a graph is represented as a student who will conduct guidance, while the side that connects two vertex states if the two vertex  or  two  students  have  one  and/or  two  of  the  same  supervisors.  This  study  uses  the literature study method. The results of this research indicate that the coloring of graphs using the Welch Powell algorithm can be applied to compile the guidance schedule of PGSD students at the Pacific University of Morotai.
Keywords : graph, graph point coloring, scheduling, welch-Powell algorithm
Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th
1. PENDAHULUAN
a. Latar Belakang
Proses  Penyusunan  jadwal  secara manual  membutuhkan  ketelitian  yang cukup  tinggi  agar  tidak  ada  unsur dalam  susunan  jadwal  yang  saling tumpang  tindih.  Di  universitas  pasifik misalnya,  proses  penyusunan  jadwal yang  dilakukan  semua  program  studi semuanya  masih  bersifat  manual  bak itu penjadwalan mata kuliah, penjadwalan seminar, maupun penjadwalan  bimbingan  mahasiswa.
Program  Studi  Pendidikan  Sekolah Dasar  (PGSD)  merupakan  salah  satu program  studi  yang  tak  jarang mengalami  kendala  dalam  proses penyusunan  jadwal,  khususnya  jadwal bimbingan  mahasiswa.  Hal  tersebut dikarenakan  jumlah  mahasiswa  dalam suatu  periode  bimbingan  yang  banyak dan beriirisannya dosen-dosen pembimbing antar mahasiswa- mahasiswa tersebut. Untuk  mengatasi  kendala  dalam proses  penyusunan  jadwal,  maka dibutuhkan  suatu  alternatif  proses penyusunan  jadwal  yang  berguna untuk mengefektifkan waktu bimbingan  mahasiswa.  Salah  satu  cara penyusunan jadwal yang dapat digunakan  adalah  menerapkan  konsep pewarnaan  titik  pada  graf  dengan menggunakan algoritma welch powell.
Pewarnaan  titik  pada  graf  dengan menggunakan  algoritma  welch  powell merupakan  salah  satu  teknik  yang dapat  digunakan  untuk  menyusun jadwal.  Setiap  mahasiswa  yang  akan melakukan  pembimbingan  dibimbing oleh  dua  orang  dosen  pembimbing. Titik-titik  pada  graf  direpresentasikan sebagai mahasiswa yang akan melakukan proses bimbingan, sedangkan  sisi  yang  menghubungkan dua  titik  menyatakan  jika  dua  titik tersebut atau dua mahasiswa  memiliki
satu  dan/atau  dua  dosen  pembimbing yang sama.
Astuti  [1]  dan  Muktyas  [2]  dalam penelitian mereka memberikan kesimpulan  jika  algoritma  Pewarnaan Graph  Welch  Powell  dapat  digunakan untuk  menentukan  jadwal  ujian semester pada sistem informasi akademik Perguruan Tinggi  agar tidak terjadi bentrokan  jadwal  untuk  semua mahasiswa. Sejalan dengan hal tersebut Harianto  dkk  [3]  juga  menggunakan teknik  pewarnaan  titik  pada  graf menggunakan  algoritma  welch  powell untuk menentukan jadwal ujian skripsi. Penggunaan  graf  dalam  menentukan jadwal  juga  dilakukan  oleh    Dewi  [4] dalam  pembangunan  perangkat  lunak pembangkit  jadwa  kuliah    dan  jadwal ujian.  Oleh  karena  itu  peneliti  tertarik untuk    menerapkan  pewarnaan  titik pada  graf  untuk  menentukan  jadwal bimbingan  mahasiswa  PGSD  UNIPAS Morotai.
b. Graf dan Pewarnaan Titik pada Graf
Graf  G adalah  pasangan  terurut yang  terdiri  dari himpunan  titik dan  himpunan sisi yang  saling  lepas  dari [5].  Dalam  hal  ini [     ] , dengan [     ] . Titik dikatakan terkait dengan sisi e jika .  Suatu  sisi seringkali  dinotasikan  dengan atau .  Sebarang  dua  titik dan pada graf dinyatakan  bertetangga  jika adalah  suatu  sisi  pada  graf    .  Derajat titik adalah  banyaknya  titik  yang bertetangga  dengan  titik .  Misalkan graf  hingga  dan terhubung tak trivial, maka didefinisikan suatu pewarnaan titik dari ,    yaitu untuk suatu bilangan bulat sedemikian  hingga  untuk  setiap  dua titik  yang  bertetangga  memiliki  warna yang berbeda.
Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th
c. Algoritma Welch-Powell
Berikut  adalah  langkah-langkah pada algoritma welch-powel [6] 1) Urutkan  simpul-simpul  dari dalam derajat yang menurun 2) Gunakan  satu  warna  untuk mewarnai simpul pertama yang memiliki  derajat  tertinggi  dan simpul-simpul lain dalam urutan yang berurut yang tidak bertetangga  dengan  simpul yang pertama ini. 3) Mulai  lagi  dengan  simpul berderajat  tinggi  berikutnya  di dalam  daftar  terurut    yang belum  diwarnai  dan  ulangi proses pewarnaan simpul dengan  menggunakan  warna yang kedua. 4) Ulangi  penambahan  warna- warna  sampai  semua  simpul telah diwarnai.

## 2. METODE PENELITIAN
Metode  penelitian  yang  digunakan dalam  penelitian  ini  adalah  metode penelitian  studi  literatur.  Awalnya peneliti mengumpulkan referensi melalui  artikel  ilmiah  dan  data mahasiswa  dan  dosen  pembimbing, kemudian selanjutnya melakukan penentuan titik-titik yang merepresentasikan mahasiswa- mahasiswa bimbingan dengan melabeli berdasarkan  inisial  nama,  setelah  itu dilakukan  pewarnaan  terhadap  titik- titik  tersebut  menggunakan  algoritma welch powell hingga akhirnya diperoleh  suatu  kesimpulan  dalam  hal ini jadwal bimbingan mahasiswa.

## 3. HASIL DAN PEMBAHASAN
Pewarnaan  titik  pada  graf  dengan menggunakan  algoritma  welch  powell diterapkan  pada  penelitian  ini  dengan merepresentasikan  terlebih  dahulu
mahasiswa  yang  akan  melakukan pembimbingan sebagai titik, sedangkan sisi  yang  menghubungkan  dua  titik menyatakan jika dua titik tersebut atau dua  mahasiswa    memiliki  satu dan/atau dua dosen pembimbing yang sama.

## Tabel 1. Data mahasiswa dan dosen
pembimbing No Mahasisw a Dosen Pembimbing 1 Sriyanti Posu (SP) Subhan Hayun, S.Pd.,M.Pd Nurhani Mahmud, S.Pd.,M.Pd 2 Bailam Luange (BL) Sulami Sibua, S.Pd.,M.Pd Subhan Hayun, S.Pd.,M.Pd 3 Susantri Lusude (SLU) Julia Ismail, S.Pd.,M.Pd Fahmi Jaguna, S.Pd.,M.Pd 4 Ariens Papadaka (AP) Julia Ismail, S.Pd.,M.Pd M Rais Salim, S.Pd.,M.Pd 5 Elya (E) Irawati Sabban, S.Pd.,M.Pd Fahmi Jaguna, S.Pd.,M.Pd 6 Andi Tenri Asyifah (ATA) Fahmi Jaguna, S.Pd.,M.Pd Subhan Hayun, S.Pd.,M.Pd 7 Janema Goorahe (JG) Nurhani Mahmud, S.Pd.,M.Pd Fahmi Jaguna, S.Pd.,M.Pd 8 Mayang Mudafar (MM) Sulami Sibua, S.Pd.,M.Pd Julia Ismail, S.Pd.,M.Pd 9 Fitria Abdullah (FA) Julia Ismail, S.Pd.,M.Pd M Rais Salim, S.Pd.,M.Pd 10 Kalsum Kopman (KK) Julia Ismail, S.Pd.,M.Pd M Rais Salim, S.Pd.,M.Pd 11 Warinta La Aha (WLA) Subhan Hayun, S.Pd.,M.Pd Nurhani Mahmud, S.Pd.,M.Pd
Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th
12 Otgandis Mala (OM) Julia Ismail, S.Pd.,M.Pd Nurhani Mahmud, S.Pd.,M.Pd 13 Nurain Bakari (NB) Fahmi Jaguna, S.Pd.,M.Pd M Rais Salim, S.Pd.,M.Pd 14 Erlina Feralita Hihika (EFH) Irawati Sabban, S.Pd.,M.Pd Fahmi Jaguna, S.Pd.,M.Pd 15 Sepdiana Lape (SLA) Nurhani Mahmud, S.Pd.,M.Pd Fahmi Jaguna, S.Pd.,M.Pd 16 Yoap Hakini (YH) Nurhani Mahmud, S.Pd.,M.Pd Fahmi Jaguna, S.Pd.,M.Pd 17 Apsari Zambrud (AZ) Subhan Hayun, S.Pd.,M.Pd Julia Ismail, S.Pd.,M.Pd

## Gambar 1. Representasi titik
(Mahasiswa) yang bertetangga
Tabel 2. Ketetanggaan Setiap Titik
Titik Titik-Titik yang Bertetangga Dera jat Titik SP BL, ATA, JG, WLA, OM, SLA, YH, AZ 8 BL SP, ATA, MM, WLA, AZ 5
SLU AP, E, ATA, JG, MM, FA, KK, NB, EFH, OM, SLA, YH, AZ 13 AP SLU, MM, FA, KK, OM, NB, AZ 7 E SLU, ATA, JG, NB, EFH, SLA, YH 7 ATA SP, BL, SLU, E, JG, WLA, NB, EFH, SLA, YH, AZ 11 JG SP, SLU, E, ATA, WLA, OM, NB, EFH, SLA, YH 10 MM BL, SLU, AP, FA, KK, OM, AZ 7 FA SLU, AP, MM, KK, OM, NB, AZ 7 KK SLU, AP, MM, FA, OM, NB, AZ 7 WLA SP, BL, ATA, JG, OM, SLA, YH, AZ 8 OM SP, SLU, AP, JG, MM, FA, KK, WLA, SLA, YH, AZ 11 NB SLU, AP, ATA, JG, EFH, SLA, YH 7 EFH SLU, E, ATA, JG, NB, SLA, YH 7 SLA SP, SLU, E, ATA, JG, WLA, OM, NB, EFH, YH 10 YH SP, SLU, E, ATA, JG, WLA, OM, NB, EFH, SLA 10 AZ SP, BL, SLU, AP, ATA, MM, FA, KK, WLA, OM 10 Gambar 2. Pemberian warna pertama
Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th
Berdasarkan langkah-langkah pada algoritma welch powell maka titik yang diberikan  warna  pertama  adalah  titik SLU  karena  memiliki  derajat  yang paling  besar.  Misalkan  warna  yang digunakan adalah warna biru. Selanjutnya  warnai  juga  titik lain  yang tidak  bertetangga  dengan  titik  SLU dengan  warna  biru.  Namun  setelah keempat  titik  diberi  warna  biru, terdapat titik yang bertetangga memiliki  warna  yang  sama.  Oleh karena  itu,  dua  titik  tidak  boleh diwarnai dengan warna biru, yaitu titik BL dan titik SP (Gambar 3)
Gambar 3. Menghilangkan warna pada titik SP dan BL
Gambar 4. Pemberian Warna Kedua
Selanjutnya warnai titik-titik dengan  warna  kedua  dalam  hal  ini warna  yang  dipakai  adalah  warna merah. Seperti pada langkah pewarnaan pertama, titik yang
diwarnai  selanjutnya  adalah  titik dengan  derajat  tertinggi  (selain  titik SLU),  yaitu  titik  ATA  atau  OM, misalkan  kita  memilih  titik  ATA. Selanjutnya  warnai  titik  yang  tidak bertetangga  dengan  titik  ATA  dengan warna yang sama (warna merah), yaitu titik  AP,  MM,  KK  dan  OM.  Sama seperti  pada  pewarnaan  pertama,
pemberian  warna  merah  pada  titik mengakibatkan  ada  titik-titik  yang bertetangga  memiliki  warna  yang sama.  Oleh  karena  itu  perlu  dilakukan penghapusan  warna  pada  tiga  titik, dalam hal ini titik MM, KK dan OM.

## Gambar 5. Menghilangkan warna pada titik MM, KK, dan OM
Selanjutnya  lakukan  cara  yang sama  pada  titik  lainnya  sedemikian sehingga  semua  titik  diberi  warna  dan tidak  ada  titik  yang  bertetangga memiliki warna yang sama.
Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th
Gambar 6. Hasil Pewarnaan Ketiga
Gambar 7. Hasil Pewarnaan Keempat
Gambar 8. Hasil Pewarnaan Kelima
Gambar 9. Hasil Pewarnaan Keenam
Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th
Gambar 10. Hasil Pewarnaan Ketujuh
Gambar 11. Hasil Pewarnaan Kedelapan Berdasarkan tahapan pewarnaan dengan menggunakan algoritma welch powell,  maka  diperoleh  delapan tahapan pewarnaan yang menunjukkan bahwa  warna  yang  digunakan  adalah sebanyak  delapan  warna.  Delapan warna tersebut menggambarkan delapan  kelompok  waktu  bimbingan yang  dapat  dijadwalkan  oleh  program studi  sehingga  waktu  bimbingan
menjadi  efektif  tanpa  ada  tumpeng tindih jadwal pembimbing.

## 4. KESIMPULAN
Berdasarkan  hasil  pemberian  warna titik-titik  pada  graf,  maka  diperoleh jumlah warna minimum yang dibutuhkan  untuk  mewarnai  titik-titik pada  graf  sedemikian  sehingga  tidak ada titik-titik yang bertetangga memiliki  warna  yang  sama  adalah sebanyak  8  warna.  Oleh  karena  itu dapat  dibuat  suatu  penjadwalan bimbingan  mahasiswa  dalam  delapan waktu kelompok Tabel 3. Pembagian Kelompok Waktu Bimingan Kelompok Warna Mahasiswa 1 Biru SLU, WLA 2 Merah APA, ATA 3 Kuning BL, E, OM 4 Hijau JG, AZ 5 Merah Muda MM, SLA 6 Ungu FA, YH 7 Cokelat KK, SP, EFH 8 Abu-abu NB 5. DAFTAR PUSTAKA [1]   Astuti,  S.  (2011).  Penyusunan Jadwal  Ujian  Mata  Kuliah  Dengan Algoritma  Pewarnaan  Graf  Welch
Powell. Jurnal Dian , 11 (1).
[2]  Muktyas,  I.  B.  (2010). Program Pewarnaan  Graf  untuk  Pemodelan Penjadwalan  Ujian  Semester  di Jurusan Matematika Unnes (Doctoral dissertation,  Universitas  Negeri Semarang). [3]  Harianto,  K.,  &  Fatdha,  T.  S.  E. (2016). Penerapan Pewarnaan Simpul  Graf  untuk  Menentukan Jadwal  Ujian  Skripsi  pada  STMIK Amik Riau Menggunakan Algoritma  Welch-Powell. SATIN-
Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th
Sains  dan  Teknologi  Informasi , 1 (2), 48-54.
[4] Dewi, F. K. S. (2010). Pembangunan Perangkat Lunak Pembangkit Jadwal  Kuliah  dan  Ujian  Dengan Metode  Pewarnaan  Graf. Jurnal Buana Informatika , 1 (1).
[5]  Diestel,  R.  (2010). Graph  Theory  4th edition . Springer.
[6]  Munir,  R.  (2012).  Matematika Diskrit  Revisi  Kelima. Indformatika, Bandung .