Vol.  9, No. 2 (2023) E-ISSN : 2685- 5585 Hal :  163 - 171 DOI: https://doi.org/10.36987/jpms.v9i1.4313

## PENERAPAN PEWARNAAN GRAF DALAM PENENTUAN JADWAL PERKULIAHAN (STUDI KASUS: STMIK PRIMAKARA)

## IMPLEMENTATION OF GRAPH COLORING IN DETERMINING A LECTURE SCHEDULE (CASE STUDY: STMIK PRIMAKARA)

## KETUT QUEENA FREDLINA
Program Teknik Informatika, STMIK Primakara Jalan Tukad Badung No 135 Renon, Denpasar, Bali, email: queena@primakara.ac.id

## Abstrak
Penjadwalan  perkuliahan  merupakan  salah  satu  permasalahan  yang  dihadapi  oleh  perguruan  tinggi. Permasalahan tersebut didefinisikan sebagai pengalokasian sumber daya  seperti dosen, mahasiswa, dan  ruang  kelas  ke  matakuliah  yang  tersedia.  Proses  penjadwalan  dilakukan  dengan  cara  manual yang  cukup  menyulitkan  dan  perlu  dilakukan  perbaikan  berulang  kali.  Optimalisasi  permasalah penjadwalan  matakuliah  perlu  dilakukan  untuk  dapat  meminimalisir  selisih  antara  kapasitas  ruangan kelas  dengan  jumlah  mahasiswa  yang  mengambil  mata  kuliah  di  suatu  ruangan.  Salah  satu  cabang teori  graf  yang  dapat  digunakan  dalam  mengatasi  permasalah  adalah  dengan  pewarnaan  graf. Pewarnaan  graf  berarti  memberikan  warna  pada  elemen  graf  yang  dijadikan  subjek  dalam permasalahan.  Hal  ini  diharapkan  dapat  mengoptimalkan  fasilitas  yang  tersedia  di  perguruan  tinggi serta dapat memenuhi semua kendala yang terjadi.
Kata kunci : graf, penjadwalan, pewarnaan graf

## Abstract
Scheduling  lectures  is  one  of  the  problems  faced  by  universities.  The  problem  is  defined  as  the allocation  of  resources  such  as  professors,  students,  and  classrooms  to  available  courses.  The scheduling process is done manually, which is quite challenging and requires repeated improvements. Optimization  of  the  course  scheduling  problem  needs  to  be  carried  out  in  order  to  minimize  the difference between the classroom capacity and the number of students taking a course in a particular room. One branch of graph theory that can be used to address this problem is graph coloring. Graph coloring means assigning colors to the elements of a graph that are the subject of the problem. This is expected to optimize the available facilities in universities and meet all the constraints that arise. Key Words : graph, scheduling, graph coloring

## Pendahuluan
Teori  graf  merupakan  salah  satu  cabang  ilmu  matematika  yang  dapat  diterapkan  dalam kehidupan  sehari-hari.  Graf  dapat  digunakan  untuk  menyelesaikan  berbagai  masalah  tertentu.  Teori graf berkembang sangat pesat karena dapat diaplikas dalam berbagai bidang ilmu.
Salah  satu  cabang  teori  graf  yang  dapat  digunakan  dalam  mengatasi  permasalah  adalah dengan pewarnaan graf. Pewarnaan graf berarti memberikan warna pada elemen graf yang dijadikan subjek  dalam  permasalahan.  Terdapat  3  macam  pewarnaan  graf,  yaitu  pewarnaan  titik  ( vertex ), pewarnaan  sisi  ( edge ),  dan  pewarnaan  wilayah  ( region ).  Pewarnaan  titik  berarti  pemberian  warna pada  himpunan  titik  graf
dengan  ketentuan  setiap  titik  yang  bertetangga  diberikan  warna  yang berbeda.  Pewarnaan  sisi  berarti  pemberian  warna  pada  himpunan  sisi  graf
dengan  ketentuan setiap sisi yang bertetanagga diberikan warna  yang berbeda. Pewarnaan wilayah berarti memetakan warna-warna  ke  wilayah-wilayah  graf    dengan  ketentuan  setiap  wilayah  yang  bertetangga  memiliki warna yang berbeda. Salah satu contoh penerapan pewarnaan graf adalah dalam penyusunan jadwal perkuliah di perguruan tinggi.
Penjadwalan  perkuliahan  merupakan  salah  satu  permasalahan  yang  dihadapi  oleh  perguruan tinggi.  Permasalahan  tersebut  didefinisikan  sebagai  pengalokasian  sumber  daya  seperti  dosen, mahasiswa, dan ruang kelas ke matakuliah  yang tersedia. Hal ini  diharapkan dapat mengoptimalkan fasilitas  yang  tersedia  di  perguruan  tinggi  serta  dapat  memenuhi  semua  kendala  yang  terjadi. Penjadwalan  mata  kuliah  akan  melibatkan  ratusan  mahasiswa,  sehingga  penyelesaian  secara
Vol.  9, No. 2 (2023) E-ISSN : 2685- 5585 Hal :  163 - 171 DOI: https://doi.org/10.36987/jpms.v9i1.4313
konvensional  (secara  manual)  memerlukan  resiko  adanya  bentrok  jadwal  serta  membutuhkan  waktu yang  lama.  Adanya  bentrok  dalam  peerkuliahan  biasanya  disebabkan  karena  adanya  kesamaan ruang  dari  minimal  2  mata  kuliah  yang  berbeda,  kesamaan  dosen  pengampu  atau  kesamaan mahasiswa peserta perkuliahan dari mata kuliah yang berbeda,
Di  STMIK  Primakara,  penyusunan  jadwal  perkuliahan  masih  memiliki  kendala-kendala  seperti yang  disebutkan  diatas.  Hal  ini  terjadi  karena  adanya  keterbatasan  pada  ruang  kelas  yang  tersedia. Selain  itu  penyusunan  jadwal  perkuliahan  belum  memperhatikan  slot  waktu  tertentu  agar  dapat dikosongkan  sesuai  permintaan  dosen.  Proses  penjadwalan  dilakukan  dengan  cara  manual  yang cukup menyulitkan dan perlu dilakukan perbaikan berulang kali. Optimalisasi permasalah penjadwalan matakuliah perlu dilakukan untuk dapat meminimalisir selisih antara kapasitas ruangan kelas dengan jumlah mahasiswa yang mengambil mata kuliah di suatu ruangan.
Dari  berbagai  solusi  yang  dapat  ditawarkan  dalam  menyelesaikan  masalah  penjadwalan matakuliah,  pewarnaan  graf  merupakan  pendekatan  yang  cukup  banyak  digunakan.  Untuk penjadwalan perkuliahan, metode pewarnaan graf yang cocok adalah metode Welsh-Powell. Metode ini  memiliki  kelebihan  dalam  mengelompokkan  kelas  yang  tidak  terjadwal  pada  waktu  yang  sama sehingga  dapat  meminimalkan  bentrok  jadwal.  Selain  itu,  metode  Welsh-Powell  juga  memiliki kelebihan  dalam  mencoba  untuk  memberikan  warna  yang  berbeda  ke  setiap  simpul  dengan  urutan yang logis, sehingga memudahkan dalam proses penjadwalan.
Berdasarkan hal itu, peneliti tertarik untuk untuk menerapkan pewarnaan graf dalam penentuan jadwal  perkuliahan  di  STMIK  Primakara.  Harapannya  dengan  adanya  system  penjadwalan perkuliahan, pembelajaran di kampus dapat dilakukan secara efisien dan lebih maksimal.

## Metode Penelitian
Sumber  data  yang  digunakan  dalam  penelitian  ini  adalah  sumber  data  primer  dan  sekunder. Data  primer  merupakan  data  yang  diperoleh  secara  langsung  dari  sumbernya.  Dalam  penelitian  ini data primer yang digunakan adalah hasil wawancara dengan bagian BAAK, observasi langsung, serta domumentasi  dari  pelaksanaan  perkuliahan  yang  telah  dijalankan.  Data  sekunder  merupakan  data yang diperoleh tidak secara langung, yaitu dari jurnal dan buku terkait permasalah dalam penelitian.
Jenis data yang digunakan dalam penelitian ini adalah data kualitatif dan  data kuantitatif. Data kualitatif  yang  digunakan  dalam  penelitian  ini  berupa  daftar  nama  dosen,  ruangan,  serta  nama mata kuliah. Data kuantitatif yang digunakan dalam penelitian ini berupa jumlah sks tiap mata kuliah, waktu pelaksaan perkuliahan dan jumlah kelas yang dibuka untuk setiap mata kuliah.
Langkah-langkah yang dilakukan dalam penelitian ini dapat dilihat pada alur penelitian berikut:
Vol.  9, No. 2 (2023) E-ISSN : 2685- 5585 Hal :  163 - 171 DOI: https://doi.org/10.36987/jpms.v9i1.4313

## 1. Identifikasi Masalah
Pada  tahap  identifikasi  masalah  dilakukan  untuk  mengetahui  permasalahan  yang  dialami  oleh Bagian  Administrasi  Akademik  dan  Kemahasiswaan  (BAAK)  STMIK  Primakara  dalam penyusunan jadwal perkuliahan. Permasalahan yang sering dihadapi adalah proses penentuan jadwal  yang  memakan  waktu lama karena perlu  adanya  pengecekan  berulang-ulang  terhadap jadwal yang disusun dan memastikan tidak ada jadwal yang bentrok.
2. Studi Pustaka
Pada  tahapan  ini  dilakukan  studi  Pustaka  dengan  mencari  literatur  untuk  mendapatkan  solusi terhadap  permasalah  yang  dihadapi.  Hasil  dari  studi  literatur  adalah  proses  penjadwalan dengan menerapkan pewarnaan graf.
3. Pengumpulan Data
Pada tahapan ini dilakukan pengumpulan data di BAAK STMIK Primakara berupa daftar dosen pengampu mata kuliah, daftar ruangan, jumlah kelas yang dibuka, kelompok mahasiswa, serta slot waktu.
4. Analisis Data
Pada  tahapan  ini  dilakukan  analisis  data  agar  data-data  yang  terkumpul  dapat  ditransformasi menjadi  bentuk  graf.  Langkah  selanjutnya  merepresentasikan  graf  menjadi  bentuk  matriks ketetanggan.
5. Pewarnaan Graf
Tahapan  ini  adalah  penerapan  algoritma Welsh  Powell  dalam  proses  pewarnaan  graf.  Proses pewarnaan  graf  dilakukan  mulai  dari  titik  yang  memiliki  derajat  paling  banyak  hingga  titik dengan derajat paling sedikit.
6. Kesimpulan
Pada  tahapan  terakhir,  akan  dilakukan  penarikan  kesimpulan  terhadap  hasil  pewarnaan  graf. Dari  sini  akan  diperoleh  jadwal  perkuliahan  yang  paling  efektif  dan  juga  efisien  dalam pemanfaatan ruangan, waktu, serta sumber daya yang tersedia.

## Hasil Penelitian dan Pembahasan Hasil Penelitian
1. Sebaran Mata Kuliah
Pada  penelitian  ini,  digunakan  sebaran  mata  kuliah  pada  Program  Studi  Teknik Informatika  STMIK  Primakara  pada  semester  Ganjil  Tahun  2022/2023.  Prodi  Teknik  Infromatika memiliki  24  Mata  Kuliah  yang  diampu  oleh  15  dosen.  Saat  ini  mahasiswa  Prodi  Teknik Informatika terdiri dari mahasiswa  semester I, III, V, dan VII. Adapun table sebaran matakuliah, dapat dilihat pada Tabel 1:
Tabel 1. Sebaran Mata Kuliah Prodi IF Semester Ganjil 2022/2023
No Kode MK Matakuliah SKS Nama Dosen Semester 1 IF20U0104  Agama Hindu 2 Anak Agung Gede Adi Mega Putra, S.Sos.H.,M.Pd. 1 2 IF20S0203  Aljabar Linier 3 Ketut Queena Fredlina, S.Si.,M.Si. 3 3 IF20U0105  Bahasa Inggris 2 Eka Grana Aristyana Dewi, M.Pd. 5 4 IF20S0301 Dasar-dasar Pemrograman 4 Putu Irvan Arya Purwadana, M.Kom. 1 5 IF20P0401 Data Mining & Warehouse 3 Nengah Widya Utami, S.Pd. , M.Kom. 7 6 IF20P0302 Desain dan Analisis Algoritma 3 Putu Irvan Arya Purwadana, M.Kom. 5 7 IF20P0801  Grafika Komputer 3 Ida Bagus Kresna Sudiatmika, S.Kom., M.T 7 8 IF20P0601  IT Forensic 3 Made Raka Dwija Wiradiputra, S.Pd., M.Kom. 7
Vol.  9, No. 2 (2023) E-ISSN : 2685- 5585 Hal :  163 - 171 DOI: https://doi.org/10.36987/jpms.v9i1.4313
9 IF20S0701 Jaringan Komputer Dasar 4 I Gede Juliana Eka Putra, S.T., M.T. 3 10 IF20S0201  Kalkulus 3 Ketut Queena Fredlina, S.Si.,M.Si. 1 11 IF20P0703 Keamanan Jaringan 3 I Nyoman Purnama, S.T., M.T. 5 12 IF20P0402 Kecerdasan Buatan 3 I Nyoman Purnama, S.T., M.T. 5 13 IF20C0702  Komunikasi data 3 Anak Agung Ayu Putri Ardyanti, S.T.,M.T. 1 14 IF20P0405  Machine Learning 3 Ida Bagus Kresna Sudiatmika, S.Kom., M.T 7 15 IF20S0904  Metode Penelitian 3 Eka Grana Aristyana Dewi, M.Pd. 5 16 IF20U0101  Pancasila 2 Anak Agung Gede Adi Mega Putra, S.Sos.H.,M.Pd. 1 17 IF20S0303 Pemrograman Berorientasi Objek 4 I Nyoman Purnama, S.T., M.T. 3 18 IF20P0301 Pemrograman Web 4 Ida Bagus Gede Purwania, S.TI., M.T. 5 19 IF20U0102 Pendidikan Kewarganegaraan 2 Helmy Syah Alam, M.Pd. 1 20 IF20C0601 Pengantar Keamanan Sistem Informasi 3 I Gede Putu Krisna Juliharta, S.T., M.T. 3 21 IF20S0601 Pengantar Sistem Digital 3 A A Istri Ita Paramitha, S.Pd.,M.Kom. 1 22 IF20S0501 Rekayasa Perangkat Lunak 3 I Nyoman Yudi Anggara Wijaya, S.Kom., M.T. 3 23 IF20S0901  Technopreneurship 3 I Gede Juliana Eka Putra, S.T., M.T. 5 24 IF20C0301 Teori Bahasa dan Otomata 3 Anak Agung Ayu Putri Ardyanti, S.T.,M.T. 3

## 2. Pembentukan Graf
Komponen yang digunakan dalam penjadwalan mata kuliah, antara lain:
a. Kelompok mata kuliah
b. Kelompok dosen pengampu
c. Kelompok mahasiswa
d. Kelompok ruangan
e. Kelompok slot waktu
Sebelum melanjutkan ke proses transformasi graf, diberikan batasan-batasan antara lain:
a. Program studi yang digunakkan hanya prodi Teknik Infromatika (IF)
b. Kelas yang digunakan hanya kelas pagi.
c. Setiap mata kuliah hanya dibuka 1 kelas.
Setelah menentukan komponen  yang  digunakan dalam penjadwala serta batasan-batasan  yang diberikan, makan tahapan dalam pembentukan graf dapat dilakukan dengan mengikuti langkah- langkah berikut:
Vol.  9, No. 2 (2023) E-ISSN : 2685- 5585 Hal :  163 - 171 DOI: https://doi.org/10.36987/jpms.v9i1.4313
a. Identifikasi  simpul-simpul:  Identifikasikan  semua  simpul  yang  akan  digunakan  dalam  graf. Dalam  hal  ini,  yang  digunakan  adalah  kelompok  mata  kuliah  yang  ada  di  Program  Studi Teknik Informatika pada Semester Ganjil 2022/2023.
b. Identifikasi keterkaitan: Identifikasikan keterkaitan antar simpul. Keterkaitan dapat ditentukan berdasarkan  kondisi  yang  telah  ditentukan,  yaitu  menghubungkan  simpul  mata  kuliah  yang diambil  oleh  mahasiswa  pada  semester  yang  sama,  serta  menghubungkan  simpul  mata kuliah yang diampu oleh dosen yang sama.
c. Pembuatan  graf:  Setelah  mengetahui  simpul-simpul  dan  keterkaitan  antar  simpul,  Langkah selanjutnya  membuat  graf  dengan  menghubungkan  simpul-simpul  yang  sesuai  dengan keterkaitan  yang  telah  ditentukan.  Pembuatan  graf  dilakukan  dengan  aplikasi  khusus  yaitu Geogebra agar lebih interaktif.
d. Validasi  graf:  Setelah  graf  dibuat,  pastikan  untuk  melakukan  validasi  untuk  memastikan bahwa  graf  yang  dibuat  sesuai  dengan  kondisi  yang  ditentukan.  Hal  ini  dapat  dilakukan dengan mengecek konsistensi keterkaitan antar simpul dan jumlah simpul yang digunakan.
e. Optimisasi  Graf:  Setelah  graf  terbuat  dan  valid,  dilakukan  optimisasi  graf  seperti penambahan  atau  pengurangan  jumlah  simpul  dan  keterkaitan  yang  diperlukan  sesuai dengan  kondisi  yang  ditentukan,  ini  berguna  agar  proses  pewarnaan  dapat  dilakukan dengan  lebih  efisien  dan  efektif.  Selain  itu,  dapat  dilakukan  penambahan  atribut  atau informasi tambahan pada simpul dan keterkaitan untuk memudahkan proses pewarnaan dan analisis selanjutnya.
Dengan  menentukan  tahapan  diatas,  transformasi  sebaran  matakuliah  kedalam  bentuk  dapat dilihat pada Gambar 1:
Gambar 1. Hasil Transformasi Graf
3. Representasi Matriks Ketetanggan
Sebaran  mata  kuliah  yang  telah  di  transformasi  kedalam  bentuk  graf  selanjutnya  akan direpresentasikan dalam bentuk matriks ketetanggaan. Dalam penyusunan matriks ketetanggan,
Vol.  9, No. 2 (2023) E-ISSN : 2685- 5585 Hal :  163 - 171 DOI: https://doi.org/10.36987/jpms.v9i1.4313
elemen matriks akan diberi nilai  1 apabila  diantar 2 simpul saling  bertetangga, sedangkan akan diberi  0  apabila  2  simpul  tidak  bertetangga.  Berdasarkan  transformasi  graf  diatas,  hasil representasi matriks dapat dilihat pada Gambar 2 berikut:

## Gambar 2. Hasil Representasi Matriks Ketetanggan
Selanjutnya  adalah  penentuan  derajat  untuk  masing-masing  simpul.  Berdasarkan  matrik ketetanggan  diatas,  akan  ditentukan  derajat  dari  masing-masing  simpul.  Perhitungan  derajat digunakan  untuk  mengetahui  simpul  dengan  derajat  tertinggi  agar  dapat  dilakukan  proses pewarnaan  graf  dengan  metode Welsh  Powell.  Derajar  dari  masing-masing  simpul  dapat  dilihat pada Tabel 2 berikut:
Tabel 2. Derajat Simpul Simpul Derajat Simpul Derajat Simpul Derajat 1 6 9 6 17 7 2 6 10 7 18 6 3 6 11 7 19 6 4 7 12 7 20 5 5 3 13 7 21 6 6 7 14 3 22 5 7 3 15 6 23 7 8 3 16 6 24 6
Vol.  9, No. 2 (2023) E-ISSN : 2685- 5585 Hal :  163 - 171 DOI: https://doi.org/10.36987/jpms.v9i1.4313

## Pembahasan
1.  Pewarnaan Graf
Berdasarkan  graf  serta  derajat  simpul  dari  graf  yang  telah  ditentukan,  Adapun  tahapan  dari pewarnaan graf menggunakan metode Welsh Powell adalah sebagai berikut:
a. Tentukan  jumlah  warna  yang  akan  digunakan.  Jumlah  warna  yang  digunakan  harus  lebih  sedikit dari jumlah simpul dalam graf.
b. Tentukan warna yang sama dapat digunakan berapa kali. Dalam penelitian ini, diberikan batasan ruangan yang digunakan oleh Prodi Teknik Informatika yaitu sebanyak dua kelas, oleh karena itu warna yang sama hanya dapat digunakan maksimal dua kali saja.
c. Urutkan semua simpul dalam graf berdasarkan derajat simpul (jumlah tetangga dari suatu simpul).
d. Mulai dari simpul dengan derajat tertinggi, beri warna pada simpul tersebut.
e. Kemudian  beri  warna  pada  simpul  berikutnya  sesuai  dengan  kondisi  yang  ditentukan,  seperti simpul tetangga tidak boleh memiliki warna yang sama.
f. Lanjutkan proses pewarnaan pada simpul-simpul berikutnya sampai semua simpul telah terwarna.
g. Jika tidak dapat memberi warna  pada simpul tertentu karena keterbatasan  warna, backtrack dan ganti warna pada simpul sebelumnya.
h. Lanjutkan  proses  pewarnaan  sampai  semua  simpul  terwarna  tanpa  ada  simpul  yang  berdekatan yang memiliki warna yang sama.
Hasil pewarnaan graf menggunakan metode Welsh Powell dapat dilihat pada Gambar 3 berikut:
Gambar 3. Hasil Pewarnaan Graf dengan Metode Welsh Powell
Vol.  9, No. 2 (2023) E-ISSN : 2685- 5585 Hal :  163 - 171 DOI: https://doi.org/10.36987/jpms.v9i1.4313

## 2.  Penetapan Jadwal Perkuliahan
Berdasarkan hasil pewarnaan graf pada Gambar 4.2 di atas, adapun hasil penjadwalan yang diperoleh dapat dilihat pada Tabel 3 berikut:

## Tabel 3. Penjadwalan Matakuliah Program Studi Teknik Informatika
Hari Jam (Wita) Matakuliah SKS Nama Dosen Ruangan Senin 08.00 - 09.40 Agama Hindu 2 Anak Agung Gede Adi Mega Putra, S.Sos.H.,M.Pd. R.01 08.00 - 10.30 Aljabar Linier 3 Ketut Queena Fredlina, S.Si.,M.Si. R.02 09.41 - 13.00 Jaringan Komputer Dasar 4 I Gede Juliana Eka Putra, S.T., M.T. R.01 10.30 - 12.10 Bahasa Inggris 2 Eka Grana Aristyana Dewi, M.Pd. R.02 13.01 - 16.20 Dasar-dasar Pemrograman 4 Putu Irvan Arya Purwadana, M.Kom. R.01 13.01 - 15.30 Keamanan Jaringan 3 I Nyoman Purnama, S.T., M.T. R.02 Selasa 08.00 - 10.30 Data Mining & Warehouse 3 Nengah Widya Utami, S.Pd. , M.Kom. R.01 08.00 - 10.30 Pengantar Sistem Digital 3 A A Istri Ita Paramitha, S.Pd.,M.Kom. R.02 13.01 - 15.30 Desain dan Analisis Algoritma 3 Putu Irvan Arya Purwadana, M.Kom. R.01 13.01 - 15.30 Kalkulus 3 Ketut Queena Fredlina, S.Si.,M.Si. R.02 15.31 - 18.00 Grafika Komputer 3 Ida Bagus Kresna Sudiatmika, S.Kom., M.T R.01 15.31 - 18.00 Rekayasa Perangkat Lunak 3 I Nyoman Yudi Anggara Wijaya, S.Kom., M.T. R.02 Rabu 08.00 - 10.30 IT Forensic 3 Made Raka Dwija Wiradiputra, S.Pd., M.Kom. R.01 08.00 - 10.30 Teori Bahasa dan Otomata 3 Anak Agung Ayu Putri Ardyanti, S.T.,M.T. R.02 13.01 - 15.30 Kecerdasan Buatan 3 I Nyoman Purnama, S.T., M.T. R.01 13.01 - 15.30 Komunikasi data 3 Anak Agung Ayu Putri Ardyanti, S.T.,M.T. R.02 15.31 - 18.00 Machine Learning 3 Ida Bagus Kresna Sudiatmika, S.Kom., M.T R.01 15.31 - 18.00 Pengantar Keamanan Sistem Informasi 3 I Gede Putu Krisna Juliharta, S.T., M.T. R.02 Kamis 08.00 - 10.30 Metode Penelitian 3 Eka Grana Aristyana Dewi, M.Pd. R.01
Vol.  9, No. 2 (2023) E-ISSN : 2685- 5585 Hal :  163 - 171 DOI: https://doi.org/10.36987/jpms.v9i1.4313
08.00 - 09.40 Pancasila 2 Anak Agung Gede Adi Mega Putra, S.Sos.H.,M.Pd. R.02 10.31 - 13.00 Technopreneurship 3 I Gede Juliana Eka Putra, S.T., M.T. R.01 09.41 - 13.00 Pemrograman Berorientasi Objek 4 I Nyoman Purnama, S.T., M.T. R.02 13.01 - 16.20 Pemrograman Web 4 Ida Bagus Gede Purwania, S.TI., M.T. R.01 13.01 - 14.40 Pendidikan Kewarganegaraan 2 Helmy Syah Alam, M.Pd. R.02
Dengan  susunan  seperti  diatas,  penjadwalan  perkuliahan  menjadi  lebih  optimal  karena  dapat memaksimalkan penggunakan 2 ruangan pada hari Senin hingga Kamis. Pada hari Jumat dapat digunakan apabila  terdapat  kelas  tambahan  atau reschedule dari  suatu  matakuliah.  Hal  ini  memudahkan  dosen maupun mahasiswa dalam membuat kesepakatan.

## Kesimpulan
Penentuan  jadwal  perkuliahan  telah  berhasil  dilakukan  menggunakan  pewarnaan  graf  dengan metode  Welsh  Powell. Metode  ini  memiliki  kelebihan  dalam  mengelompokkan  kelas  yang  tidak  terjadwal pada  waktu  yang  sama  sehingga  dapat  meminimalkan  bentrok  jadwal.  Selain  itu,  metode  Welsh-Powell juga  memiliki kelebihan  dalam mencoba  untuk memberikan  warna  yang  berbeda  ke  setiap  simpul  dengan urutan  yang  logis.  Dalam  penelitian  ini digunakan  sebaran  mata  kuliah  pada  Program  Studi  Teknik Informatika STMIK Primakara pada semester Ganjil Tahun 2022/2023. Yaitu sebanyak 24 Mata Kuliah yang diampu oleh 15 dosen. Adapun jumlah warna yang dihasilkan sebanyak 12 warna yang berarti akan dibuat 12 slot waktu untuk penentuan jadwal perkuliahan dari hari Senin hingga Kamis dengan memaksimalkan 2 (dua) ruangan.

## Daftar  Pustaka
[1] Diestel, Reinhard. (2000). Graph Theory Electronic Edition 2000 . New York: Springer-Verlag.
[2] Munir, Renaldi. (2005). Matematika Diskrit . Edisi Ketiga. Bandung: Informatika.
[3] Siang,  Jong  Jek.  (2009). Matematika  Diskrit  dan  Aplikasinya  pada  Ilmu  Komputer .  Yogyakarta:  Andi Offset.
[4] Mahmudah,  M.,  &  Irawati,  T.  N.  (2018).  Aplikasi  Pewarnaan  Graf  Terhadap  Pembuatan  Jadwal  Ujian Semester  Di  Jurusan  Pendidikan  Matematika  Universitas  Islam  Jember.  KadikmA,  9(2),  12 –21. https://doi.org/10.19184/KDMA.V9I2.8530
[5] Sagala, V., & Mekar Sari, F. (2018). Optimasi Pengaturan Lalulintas Raya Gedangan dengan Penerapan Algoritma  Welch-Powel  dan  Bilangan  Khromatik.  In  J.  Math.  and  Its  Appl.  E-ISSN  (Vol.  15,  Issue  1). https://doi.org/10.12962/LIMITS.V15I1.3370
[6] Astuti, Setia. (2011).  Penyusunan Jadwal  Ujian  Mata Kuliah  dengan Algoritma Pewarnaan Graf Welch- Powell. Jurnal Dian Vol.11 No.1 Januari 2011.
[7] Abidin, W. (2014). Pewarnaan Sisi Pada Graf Yang Berhubung Dengan Sikel . Jurnal MSA Vol. 2 No. 1 : 69 – 75.
[8] Tasari.  (2012). Aplikasi  pewarnaan  graf  pada  penjadwalan  perkuliahan  di  program  studi  pendidikan matematika unwidha klaten . Magistra No. 82 Th. XXIV desember 2012. ISSN 0215-9511