## EULER: Jurnal Ilmiah Matematika, Sains dan Teknologi

## Efisiensi Pengaturan Jadwal Perkuliahan Menggunakan Pendekatan Pewarnaan Graf
Syamsyida Rozi 1 *, Niken Rarasati 2 , Rosda Syelly 3
1,2 Prodi Matematika, Fakultas Sains dan Teknologi Universitas Jambi, Mendalo Indah 36361, Indonesia
3 Teknik Komputer, Sekolah Tinggi Teknologi Payakumbuh, Payakumbuh, 26227, Indonesia
*Email: syamsyida.rozi@gmail.com

## Abstrak
Jadwal perkuliahan untuk setiap mata kuliah harus diatur sedemikian rupa sehingga mata kuliah- mata kuliah yang  diikuti oleh mahasiswa yang  sama ataupun melibatkan  dosen yang sama tidak dilakukan pada hari  dan jam yang sama. Hal ini dilakukan untuk menghindari terjadinya jadwal perkuliahan yang bentrok bagi mahasiswa ataupun dosen pengampunya. Pada semester ganjil T.A. 2021/2022,  terdapat  23  mata  kuliah  yang  dijadwalkan  di  prodi  Matematika  Universitas  Jambi. Mahasiswa semester 1 dan semester 5 masing-masingnya dibagi menjadi 2 kelas karena banyaknya mahasiswa yang berada pada semester itu. Oleh karena itu, pengaturan jadwal perkuliahan semakin rumit.  Tujuan  dari  penelitian  ini  adalah  untuk  menata  jadwal  perkuliahan  supaya  tidak  terjadi bentrok  dengan  pendekatan  pewarnaan  graf.  Penelitian  ini  tergolong  penelitian  studi  kasus  dan menerapkan metode deskriptif. Pengaturan jadwal perkuliahan dimulai dengan pemodelan masalah dalam  bentuk  graf  dan  selanjutnya  dilakukan  algoritma Welch  Powell untuk  mewarnai  verteks dalam  graf.  Dalam  model  graf  pada  penelitian  ini,  terdapat  36  verteks  dan  215  sisi.  Dengan menerapkan  algoritma  Welch-Powell  diperoleh  bilangan  kromatik  bernilai  10,  yang  artinya terdapat 10 sesi optimum atau 10 sesi minimal yang dibutuhkan untuk menjadwalkan perkuliahan semester  ganjil  di  prodi  Matematika  Universitas  Jambi.  Berdasarkan  hasil  ini  dapat  dibuat pengelompokan mata kuliah yang dapat dijadwalkan pada hari dan jam yang sama.
Kata Kunci: Jadwal; Graf; Pewarnaan Graf; Algoritma Welch-Powell

## Abstract
The schedule for each course should be arranged such that the course taken by the same student or  involving  the  same  lecturer  are  not  scheduled  on  the  same  day  and  time.  This  is  to  avoid conflicting  schedules  for  students  and  lecturers.  In  the  odd  semester academic  year  2021/2022, there  were  23  courses  scheduled  at  the  study  program  of  Mathematics,  Universitas  Jambi.  The students in semesters 1 and 5 were divided into 2 classes, respectively, due to a large number of students  in  that  semester.  Therefore,  the  arrangement  of  the  course  schedule  was  getting  more complicated. This research aimed to arrange the course schedule so that there is no clash by using the graph coloring approach. This research was classified as case study research and applied the descriptive method. The arrangement of the course schedule began with modeling the problem in the form of a graph and then using the Welch Powell algorithm to color the vertices in the graph. The  graph  consists  of  36  vertices  and  215  edges.  By  applying  the  Welch-Powell  algorithm,  the chromatic number obtained was 10, which means there are 10 optimum sessions or 10 minimum sessions of the course schedule in the odd semester in the Mathematics study program Universitas Jambi. Based on this result, the grouping of courses can be obtained that can be scheduled on the same day and at the same time.
Keywords: Schedule; Graph; Graph Coloring; Welch-Powell Algorithm

## 1. Pendahuluan
Mengatur jadwal perkuliahan setiap semester di Prodi Matematika Fakultas Sains dan Teknologi (FST) Universitas Jambi yang selama ini dilakukan dirasa tidak mudah dan kurang sistematis. Faktor- faktor yang perlu dipertimbangkan ketika menyusun jadwal perkuliahan  di Prodi matematika FST adalah nama mahasiswa yang mengikuti perkuliahan, tim dosen yang akan mengampu mata kuliah tersebut  dan  ketersediaan  ruangan.  Sering  kali  setelah  menyusun jadwal  perkuliahan,  ternyata  ada saja kejadian beberapa mata kuliah yang jadwalnya bentrok, dalam artian terdapat dua mata kuliah yang diikuti oleh mahasiswa  yang sama secara tidak sengaja dijadwalkan pada hari dan jam yang sama. Tentunya hal ini tidak bisa dibiarkan, sehingga salah satu mata kuliah perlu dijadwalkan ulang.
Langkah yang selama ini dilakukan untuk mengatur jadwal perkuliahan di prodi Matematika FST adalah  dengan  mendaftarkan nama-nama  mata kuliah  yang  akan  diadakan,  kemudian  dicoba-coba menyusun jadwal perkuliahan sedemikian sehingga tidak ada mata kuliah yang jadwalnya bentrok, baik bagi mahasiswa, ataupun bagi dosen pengampu. Proses tersebut memakan waktu yang lumayan lama dan dirasa kurang efektif.
Dalam Matematika, terdapat suatu cabang ilmu yang disebut dengan Matematika Diskrit, dimana dalam  Matematika  Diskrit,  yang  dibahas  adalah  objek-objek  diskrit.  Dan  salah  satu  topik  dalam Matematika  Diskrit  adalah  Teori  Graf.  Teori  graf  sangat  banyak  membantu  untuk  mengatasi permasalahan sehari-hari terkait penyusunan atau pengaturan objek-objek. Langkah yang dilakukan dalam memecahkan masalah menggunakan teori graf adalah dengan memodelkan masalah tersebut dalam  bentuk  graf,  kemudian  gunakan  atau  jalankan  algoritma  yang  tersedia  dan  cocok  untuk menemukan solusi atas permasalahan yang dimiliki.
Masalah mengatur atau menyusun jadwal perkuliahan merupakan salah satu masalah yang bisa diselesaikan dengan menggunakan teori graf, lebih khusus lagi menggunakan algoritma pewarnaan verteks  dalam  graf.  Melalui  pemodelan  ke  dalam  graf,  dan  kemudian  menjalankan  algoritma pewarnaan  graf,  maka  penyelesaian  masalah  pengaturan  jadwal  perkuliahan  tidak  hanya  lebih sistematis, melainkan juga dapat menghindari munculnya masalah jadwal yang bentrok. Selain itu, melalui  pemodelan  ke  dalam  graf  dan  menyelesaikan  masalah  penjadwalan  dengan  algoritma pewarnaan  graf,  dapat  diperoleh  solusi  optimal  yaitu  dalam  bentuk  banyaknya time  slot yang minimum untuk menjadwalkan perkuliahan.
Diantara penggunaan pewarnaan graf untuk menyelesaikan permasalahan telah dilakukan oleh Danang  dkk  [1]  dan  Cahyo  dkk  [2]  yang  menggunaan  algoritma  pewarnaan  graf  untuk mengoptimalkan pengaturan lampu lintas. Sedangkan, penelitian yang berkaitan dengan penyusunan jadwal telah dilakukan oleh Komijan dkk [3] yang menggunakan binary programming dan Daskalaki [4]  yang  menggunakan  integer  programming  untuk  mengatur  jadwal  ujian  pada  perguruan  tinggi. Penelitian  lainnya  adalah  oleh  Ana  dkk  yang  menerapkan  metode random  non  ascendant  method (RNA) dan beberapa algoritma genetik jadwal pelajaran di sekolah [5]. Penelitian lainnya yang juga berkaitan dengan strategi pengaturan  jadwal khususnya jadwal perkuliahan dilakukan oleh Marisa dkk  [6]  yang  menggunakan  metode  Hungarian  yang  merupakan  salah  satu  metode  yang  bisa digunakan  untuk  memecahkan  masalah  penugasan.  Selanjutnya  Winda  dkk  [7]  meneliti  optimasi penjadwalan waktu kerja dengan integer programming , Burke dkk [8] menggunakan metode hyper- heuristic untuk  mengkonstruksi  jadwal  ujian  dan  jadwal  perkuliahan.  Penelitian  lain  terkait pengaturan  jadwal  perkuliahan  dilakukan  oleh  Perera  yang  menggunakan  pemodelan  graf  dan pewarnaan graf serta dilanjutkan dengan integer linear programming (ILP) [9].
Permasalahan  dalam  penelitian  tersebut  adalah  ingin  mengatur  jadwal  perkuliahan  di  fakultas Applied  Sciences ,  yang  terdiri  dari  9  departemen  dan  hampir  200 mata  kuliah  yang  berbeda, sedangkan  jumlah  ruang  kelas  sangat  terbatas,  mata  kuliahnya  bervariasi  serta  mahasiswa  yang mendaftarkan diri untuk kuliah di fakultas tersebut semakin banyak. Oleh karena ruang lingkup dari penelitiannya yang luas, maka Perera menerapkan metode pewarnaan graf dan dilanjutkan dengan ILP dalam penyelesaian permasalahannya. Adapun dalam penelitian ini, masalah pengaturan jadwal perkuliahan diselesaikan cukup melalui pemodelan graf dan menerapkan algoritma pewarnaan graf, khususnya pewarnaan verteks pada graf. Hal ini dikarenakan masalah yang dihadapi dalam penelitian
ini  adalah  penyusunan  jadwal  perkuliahan  untuk  1  prodi,  yang  ruang  lingkupnya  jauh  lebih  kecil dibandingkan 9 departemen atau sebuah fakultas. Hal ini dikarenakan, jadwal perkuliahan di prodi- prodi  di  Universitas  Jambi  diatur  oleh  prodi  masing-masing,  bukan  oleh  fakultas.  Melalui pemanfaatan  algoritma  Welch  Powell,  sudah  mampu  menyelesaikan  masalah  pengaturan  jadwal perkuliahan di prodi Matematika Universitas Jambi.

## 2. Metode Penelitian
Metode penelitian yang dilakukan pada penelitian ini adalah metode deskriptif, khususnya lebih ke penelitian studi kasus. Tahapan yang dilakukan dalam penelitian studi kasus ini dimulai dengan merumuskan masalah yang akan diteliti. Permasalahan yang dipecahkan melalui penelitian ini adalah tentang  bagaimana  proses  penyusunan  jadwal  perkuliahan  yang  efisien,  khususnya  untuk  jadwal perkuliahan semester ganjil di prodi Matematika Universitas Jambi. Kemudian dilanjutkan dengan pengumpulan data, yaitu terkait mata kuliah yang dibuka pada semester ganjil di prodi Matematika, himpunan  mahasiswa  yang  mengikuti  perkuliahan  tersebut  serta  dosen  pengampu  untuk  masing- masing  mata  kuliah.  Tahapan  berikutnya  adalah  pemodelan  matematika.  Dalam  penelitian  ini, permasalahan akan dipecahkan dengan memodelkan permasalahan dalam bentuk graf.
Graf  merupakan  struktur  diskrit  yang  mengandung  verteks  dan  sisi  yang  menghubungkan verteks-verteks  tersebut.  Suatu  graf    mengandung  himpunan  tak  kosong = { , , … } yang disebut dengan verteks/ titik/ node, dan himpunan lainnya = { , , … } yang disebut dengan edges / sisi. Graf dinotasikan dengan = ( , ) . Sisi pada graf biasanya dinotasikan dengan = yang artinya sisi   menghubungkan verteks   dan   [10]. Sisi yang menghubungkan   dan   kadang dituliskan dengan ( , ) dimana sisi   dikatakan bersisian dengan verteks   dan  , dan sebaliknya verteks    dan    dikatakan  bersisian  dengan  sisi  .  Selain  itu, = ( , ) juga  menyatakan  bahwa verteks   dan verteks   bertetangga [11]. Diantara klasifikasi dari graf adalah adanya graf berbobot, yaitu graf yang sisinya diberi bobot, dan ada pula graf tidak berbobot, yaitu graf yang sisinya tidak diberi bobot, kemudian graf berarah dan graf tak berarah [10].
Tahapan  selanjutnya  setelah  pemodelan  masalah  ke  dalam  bentuk  graf  adalah  menerapkan algoritma  Welch-Powell  untuk  mewarnai  verteks-verteks  pada  graf.  Tujuan  pewarnaan  ini  adalah untuk mengetahui mata kuliah yang tidak dapat dijadwalkan penyelenggaraannya pada waktu yang sama. Pewarnaaan dari suatu graf sederhana berarti memberi warna pada setiap verteks dalam graf tersebut  sedemikian  sehingga  verteks  yang  bertetangga  tidak  memiliki  warna  yang  sama  [12]. Banyaknya  warna  paling  sedikit  yang  dibutuhkan  untuk  mewarnai  graf  disebut  dengan  bilangan kromatik dari graf. Algoritma yang terkenal untuk mewarnai graf adalah algoritma Welch Powel [13], yaitu sebagai berikut:
1) Verteks dalam graf   diurutkan dari yang derajatnya paling tinggi hingga ke yang derajatnya paling rendah
2) Mulai dari verteks yang derajatnya paling tinggi, berikan sebuah warna untuk verteks tersebut, dilanjutkan  dengan  memberikan  warna  yang  sama  pada  verteks  lainnya  (dengan  derajat menurun) yang tidak bertetangga dengan verteks yang telah diberi warna tadi
3) Mulai lagi dengan warna baru untuk verteks derajat tertinggi berikutnya yang belum diwarnai serta verteks-verteks lainnya yang belum diwarnai dan tidak bertetangga dengan verteks yang diwarnai pada tahapan ini.
4) Ulangi lagi penambahan warna sehingga semua verteks sudah diwarnai.
Tahapan terakhir adalah menginterpretasi hasil yang diperoleh dari algoritma Welch Powell dan menarik kesimpulan atas hasil yang diperoleh.

## 3. Hasil dan Pembahasan
Untuk  mengatur  jadwal  perkuliahan,  maka  permasalahan  dimodelkan  dalam  bentuk  graf. Himpunan  mahasiswa,  nama  mata  kuliah  dan  dosen  pengampu  mata  kuliah  tersebut  diasumsikan sebagai satu kesatuan untuk menjadi suatu verteks pada graf. Penamaan verteks dan interpretasi dari masing-masing verteks  disajikan pada Tabel 1. Salah satu contoh adalah verteks  11A menyatakan
mata kuliah Teori Bilangan yang diikuti oleh himpunan mahasiswa semester 1 yang berada di kelas R001  dengan  dosen  pengampunya  adalah  Syamsyida  Rozi,  Gusmanely  dan  Cut  Multahadah. Selanjutnya dua buah verteks (matakuliah) pada graf dikatakan bertetangga jika terdapat mahasiswa yang  mengikuti  kedua  matakuliah  tersebut  sekaligus  ataupun  jika  terdapat  dosen  yang mengampu kedua  matakuliah  tersebut  sekaligus.  Hubungan  ketetanggaan  antara  dua  verteks  ini  dinyatakan sebagai sisi pada graf.
Dalam pemodelan melalui graf pada penelitian ini diasumsikan matakuliah Agama I, dan mata kuliah pilihan tidak diikutsertakan dalam permasalahan atau pemodelan.  Hal ini dikarenakan mata kuliah-mata kuliah tersebut diikuti oleh mahasiswa yang berasal dari kelas yang bervariasi. Namun penjadwalan  untuk  mata  kuliah-mata  kuliah  ini  akan  diatur  setelah  pengaturan  jadwal  untuk mata kuliah wajib diselesaikan.
Tabel 1. Verteks-Verteks Dalam Pemodelan Graf
Label Verteks pada Graf
Himpunan Mahasiswa
Nama MK Dosen Pengampu Seme ster Kelas Dosen 1 Dosen 2 Dosen 3 Dosen 4 11A 1 R001 Teori Bilangan Syamsyida Rozi, S.Si., M.Si. Gusmanely Z, S.Pd., M.Si. Cut Multahadah, S.Pd.,M.Pd. 11B 1 R001 Bahasa Indonesia R Imam Suwardi W, Drs. M.Pd. Priyanto, S.Pd., M.Pd. 11C 1 R001 Bahasa Inggris Duti Volya, S.Pd., M.Pd. 11D 1 R001 Kimia Dasar
Nelson, Drs.
M.Si. Nindita Clourisa
S.Si., M.Sc.
11E 1 R001 Pancasila Aulia Farida, S.P, M.Si. 11F 1 R001 Kalkulus I Sufri, Drs. M.Si. 11G 1 R001 Fisika Dasar Samsidar, S.Si.,M.Si. Nurhidayah, S.Pd., M.Sc 11H 1 R001 Biologi Umum Tia Wulandari, S.Pd., M.Si. Anggit Prima Nugraha, S.Si., M.Sc. Hasna Ul Maritsa, S.Si., M.Sc. Fitratul Aini, M.Si. 12A 1 R002 Teori Bilangan Syamsyida Rozi, S.Si., M.Si. Gusmanely Z, S.Pd., M.Si. Cut Multahadah, S.Pd.,M.Pd. 12B 1 R002 Bahasa Indonesia R Imam Suwardi W, Drs. M.Pd. Priyanto, S.Pd., M.Pd.
12C
1 R002 Bahasa Inggris Duti Volya, S.Pd., M.Pd. 12D 1 R002 Kimia Dasar Nelson, Drs. M.Si. Nindita Clourisa, S.Si., M.Sc.
12E
1 R002 Pancasila Mulawarman, Ir. M.Si. 12F 1 R002 Kalkulus I Gusmi Kholijah,
S.Si., M.Si.
Syamsyida Rozi, S.Si., M.Si. Gusmanely Z, S.Pd., M.Si.
12G
1 R002 Fisika Dasar Mardian Peslinof, S.Si., M.Si. Yoza Fendriani, S.Pd., M.Si. 12H 1 R002 Biologi Umum Tia Wulandari, S.Pd., M.Si. Anggit Prima Nugraha, S.Si., M.Sc. Hasna Ul Maritsa, S.Si., M.Sc. Fitratul Aini, M.Si.
Label Verteks pada Graf Himpunan Mahasiswa
Nama MK Dosen Pengampu Seme ster Kelas Dosen 1 Dosen 2 Dosen 3 Dosen 4 3A 3 R001 Aljabar Linier Elementer Wardi Syafmen, Drs. M.Si. Niken Rarasati, S.Si., M.Si. Sherli Yurinanda, S.Pd., M.Si. 3B 3 R001 Teori Bilangan Syamsyida Rozi, S.Si., M.Si. Cut Multahadah, S.Pd., M.Pd. Gusmanely Z, S.Pd., M.Si. 3C 3 R001 Pemrograman Komputer Niken Rarasati, S.Si., M.Si. Gusmi Kholijah, S.Si., M.Si. Corry Sormin, S.Si., M.Sc. 3D 3 R001 Statistika Matematika I Bunga Mardhotillah,
S.Si., M.Stat.
Gusmi Kholijah, S.Si., M.Si. Corry Sormin, S.Si., M.Sc. 3E 3 R001 Kalkulus Lanjut Wardi Syafmen,
Drs. M.Si. Gusmanely Z,
S.Pd., M.Si. Sherli Yurinanda, S.Pd., M.Si. 3F 3 R001 Matematika Diskrit
Sherli Yurinanda, S.Pd., M.Si. Syamsyida Rozi, S.Si., M.Si. 3G 3 R001 Geometri Yelli Ramalisa,
S.Pd., M.Sc.
Bunga Mardhotillah, S.Si., M.Stat.
Cut Multahadah, S.Pd.,M.Pd. 3H 3 R001 Agroindustri Dan Green Teknologi Madyawati Latief, Dr. S.P., M.Si. Indra Lasmana Tarigan,M.Sc. 51A 5 R001 Kewirausahaan Dede Martino, Ir. M.P. Gusmi Kholijah, S.Si., M.Si.
51B 5 R001 Metode Numerik Niken Rarasati, S.Si., M.Si. Syamsyida Rozi, S.Si., M.Si. 51C 5 R001 Persamaan Diferensial Parsial Yelli Ramalisa, S.Pd., M.Sc. Corry Sormin, S.Si., M.Sc.
Syamsyida Rozi, S.Si.,
M.Si.
51D 5 R001 Penulisan Karya Ilmiah Bunga Mardhotillah, S.Si., M.Stat.
Gusmi Kholijah, S.Si., M.Si.
51E 5 R001 Analisis Real II Wardi Syafmen,
Drs. M.Si. Cut Multahadah,
S.Pd., M.Pd. Sherli Yurinanda, S.Pd., M.Si. 51F 5 R001 Geometri Yelli Ramalisa,
S.Pd., M.Sc.
Bunga Mardhotillah,
S.Si., M.Stat. Cut Multahadah, S.Pd.,M.Pd. 52A 5 R002 Kewirausahaan Gusmi Kholijah, S.Si., M.Si. Linda Handayani, S.Pd., M.Si.
52B
5 R002 Metode Numerik Niken Rarasati, S.Si., M.Si. Syamsyida Rozi, S.Si., M.Si. 52C 5 R002 Persamaan Diferensial Parsial Yelli Ramalisa, S.Pd., M.Sc. Corry Sormin,
S.Si., M.Sc. Syamsyida Rozi, S.Si., M.Si. 52D 5 R002 Penulisan Karya Ilmiah Bunga
Mardhotillah, S.Si., M.Stat.
Gusmi Kholijah,
S.Si., M.Si.
Label Verteks pada Graf Himpunan Mahasiswa
Nama MK Dosen Pengampu Seme ster Kelas Dosen 1 Dosen 2 Dosen 3 Dosen 4 52E 5 R002 Analisis Real II Wardi Syafmen, Drs. M.Si. Cut Multahadah, S.Pd., M.Pd. Sherli Yurinanda, S.Pd., M.Si. 52F 5 R002 Geometri Yelli Ramalisa, S.Pd., M.Sc. Bunga Mardhotillah, S.Si., M.Stat. Cut Multahadah, S.Pd.,M.Pd.
Dengan demikian sebagaimana yang terlihat pada Tabel 1, terdapat 36 buah verteks dalam graf . Dan sebelum membuat graf  , dapat pula diamati bahwa terdapat lima buah subgraf dari graf  , yaitu didefinisikan sebagai berikut:
a) Subgraf yang  berisi  verteks-verteks  yang  menyatakan  mata  kuliah  yang  diikuti  oleh mahasiswa semester 1 kelas R001,
b) Subgraf yang  berisi  verteks-verteks  yang  menyatakan  mata  kuliah  yang  diikuti  oleh mahasiswa semester 1 kelas R002,
c) Subgraf yang  berisi  verteks-verteks  yang  menyatakna  mata  kuliah  yang  diikuti  oleh mahasiswa semester 3,
d) Subgraf yang  berisi  verteks-verteks  yang  menyatakan  mata  kuliah  yang  diikuti  oleh mahasiswa semester 5 kelas R001,
e) Subgraf yang  berisi  verteks-verteks  yang  menyatakan  mata  kuliah  yang  diikuti  oleh mahasiswa semester 5 kelas R002.
sehingga
( ∪ ∪ ∪ ∪ ) ⊂ .
Setiap  verteks  pada  masing-masing  subgraf  saling  bertetangga  dikarenakan  mata  kuliah  pada masing-masing subgraf diikuti oleh himpunan mahasiswa yang sama. Oleh karena setiap verteks pada subgraf  saling  bertetangga,  maka  masing-masing  subgraf , , , dan merupakan  graf lengkap,  yaitu  graf  yang  setiap  pasangan  verktesnya  saling  bertetangga  [14].  Subgraf , , ,
dan disajikan pada Gambar 1.
a) b) c)
d) e)
Gambar 1 . Subgraf dari graf  . a) Subgraf
, b) Subgraf , c) Subgraf , d) Subgraf , e) Subgraf
Oleh karena , , , dan merupakan graf lengkap, maka bilangan kromatik dari masing- masing subgraf tersebut adalah sebanyak verteks yang ada salam subgraf tersebut, sebagaimana yang sampaikan dalam [15], bahwa graf lengkap yang mengandung   buah verteks memiliki bilangan kromatik sebesar  . Oleh karena itu, subgraf , dan merupakan graf lengkap yang masing- masingnya mengandung 8 buah verteks sehingga bilangan kromatik untuk masing-masing subgraf tersebut adalah 8 atau secara matematis ditulis
( ) = ( ) = ( ) = ( ) = 8.
Ini  berarti  jadwal  mata  kuliah  untuk  mahasiswa  semester  1  harus  dibagi  menjadi  8  sesi  yang berbeda,  baik  untuk  mahasiswa  semester  1  kelas  R001,  ataupun  dari  kelas  R002.  Begitu  pula perkuliahan  yang  diikuti  oleh  mahasiswa  semester  3  harus  dibagi  menjadi  8  sesi  yang  berbeda. Sedangkan subgraf dan merupakan graf lengkap yang masing-masingnya mengandung 6 buah  verteks,  sehingga  bilangan  kromatik  untuk  masing-masing  subgraf  ini  adalah  6  atau  secara matematis ditulis
( ) = ( ) = ( ) = 6.
Hal ini berarti bahwa jadwal perkuliahan untuk mahasiswa semester 5 harus diadakan pada 6 sesi yang berbeda. Dengan demikian, batas minimum sesi penjadwalan yang bisa diselenggarakan di prodi Matematika Universitas Jambi secara umum adalah

## max{ ( ), ( )} = max{8, 6} = 8.
Namun dikarenakan masih terbatasnya banyak dosen di prodi Matematika, dan terdapat dosen yang mengampu mata kuliah untuk mahasiswa di semester yang berbeda (misal, seorang dosen tidak hanya  mengampu  mata  kuliah  untuk  mahasiswa  semester  3  saja,  melainkan  juga  mengampu  mata kuliah untuk mahasiswa semester 5). Oleh karena itu, terdapat hubungan ketetanggaan antara verteks pada  subgraf  yang  satu  dengan  verteks  pada  subgraf  lainnya.  Berdasarkan  Tabel  1, mempertimbangkan total verteks dalam pemodelan graf dan banyaknya hubungan ketetanggaan yang terjalin  antar  verteks,  maka  graf  disajikan  dalam  bentuk  matriks,  yaitu  matriks  ketetanggaan ( adjacency matrix ), sebagaimana yang terlihat pada Gambar 2.
Gambar 2 . Representasi graf   dalam bentuk matriks
Pada  Gambar  2,  terdapat  36  verteks  dan  215  sisi.  Angka  0  dalam  matriks  ketetanggaan menunjukkan  bahwa  antara  dua  buah  verteks  tidak  bertetangga,  yang  artinya,  kedua  mata  kuliah tersebut tidak diikuti oleh himpunan mahasiswa yang sama dan tidak pula diampu oleh dosen yang sama. Sedangkan angka 1 dalam matriks ketetanggaan tersebut menyatakan antara dua buah verteks bertetangga yang artinya kedua mata kuliah tersebut diikuti oleh himpunan mahasiswa  yang sama atau diampu oleh dosen yang sama.
Selanjutnya  dilakukan  algoritma  Welch  Powell  untuk  mewarnai  verteks  dalam  graf.  Untuk memulai  menjalankan  algoritma  Welch  Powell,  dihitung terlebih  dulu  derajat  dari  masing-masing verteks  dan  selanjutnya  verteks-verteks  dituliskan  secara  berurutan  berdasarkan  derajatnya,  mulai dari verteks  dengan derajat tertinggi hingga derajat terendah, yaitu sebagaimana yang ditampilkan pada Tabel 2.
Tabel 2 . Urutan Verteks Berdasarkan Derajatnya Label Verteks Derajat Verteks Label Verteks Derajat Verteks Label Verteks Derajat Verteks 11A 21 51F 14 11D 8 12F 21 52B 14 11H 8 12A 20 52E 14 12B 8 3B 18 52F 14 12C 8 3C 16 3E 12 12D 8 3D 16 3A 11 12H 8
11A 11B 11C 11D 11E 11F 11G 11H 12A 12B 12C 12D 12E 12F 12G 12H 3A
3B 3C 3D 3E 3F 3G 3H 51A 51B 51C 51D 51E 51F 52A 52B 52C 52D 52E 52F
11A 0 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 11B 1 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11C 1 1 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11D 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11E 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11F 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11G 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11H 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12A 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 12B 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12C 0 0 1 0 0 0 0 0 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12D 0 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12E 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12F 1 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 12G 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12H 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3A 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 0 0 1 0 0 1 0 0 1 0
3B 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1
3C 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0
3D 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1
3E 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 0
3F 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 1 0
3G 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 1 1
3H 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
51A 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 1 0 0
51B 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 1 1 1 0 1 1 0 0 0
51C 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 0 1
51D 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 1 1 1 0 0 1 0 1
51E 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 0 1 0 0 0 0 1 1
51F 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1
52A 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 1
52B 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 1
52C 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1
52D 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 0 1 1
52E 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 1
52F 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0
Label Verteks Derajat Verteks Label Verteks Derajat Verteks Label Verteks Derajat Verteks 3F 16 51D 11 11E 7 51C 16 52D 11 11F 7 52C 16 51A 10 11G 7 3G 15 52A 10 12E 7 51B 14 11B 8 12G 7 51E 14 11C 8 3H 7
Kemudian  verteks-verteks  diberi  warna  mulai  dari  verteks  berderajat  tertinggi.  Prinsip pentingnya adalah bahwa dua buah verteks  yang bertetangga tidak boleh diberi warna yang sama. Sehingga akhirnya diperoleh pewarnaan verteks sebagaimana pada Tabel 3.
Tabel 3. Pengelompokan pewarnaan verteks berdasarkan algoritma Welch-Powell
Merah Hijau Biru Kuning Ungu Cream PINK Oren Abu- Abu Biru Muda 11A 12F 12A 3B 3F 52B 51C 3A 52C 51B 3C 3G 3D 51D 51F 51A 52E 52D 51E 52F 12B 11B 11C 11D 52A 12E 12H 12G 11F 3E 12C 11H 3H 11E 11G
12D
Tabel 3 memberikan interpretasi bahwa mata kuliah yang direpresentasikan oleh verteks yang warnanya sama boleh dijadwalkan kegiatannya pada waktu yang sama, yaitu pada hari dan jam yang sama.  Misalnya  mata  kuliah  yang  dilabeli  dengan  verteks  11A,  verteks  3C  dan  verteks  12B  bisa dilakukan pada jadwal yang sama. Pengelompokan verteks sesungguhnya tidak unik, dalam artian, pengelompokan verteks yang terlihat pada Tabel 3 bukan merupakan satu-satunya pengelompokan verteks  yang  bisa  dibuat  melalui  algoritma  Welch  Powell.  Hal  ini  dikarenakan  terdapat  banyak verteks berderajat sama sebagaimana yang terlihat pada Tabel 2. Namun demikian, dapat dipastikan bahwa  bilangan  kromatik  dari  graf  yang  direpresentasikan  pada  Gambar  2  adalah  10  berdasarkan pengelompokan  warna  secara  optimum  yang  diperoleh  dari  algoritma  Welch-Powell.  Dan  dengan demikian pula, berdasarkan algoritma Welch Powell ada 10 periode/sesi jadwal kuliah per minggu, yang  artinya  kelompok  matakuliah  dengan  warna  yang  sama  pada  Tabel  3,  maka  kegiatan perkuliahannya  dapat  dilakukan  pada  hari  dan  jam  yang  sama.  Interpretasi  dari  pengelompokan verteks yang diperoleh pada Tabel 3 disajikan pada Tabel 4.
Tabel 4. Pengelompokan mata kuliah yang bisi dijadwalkan pada hari dan jam yang sama
Periode Pilihan MK yang bisa dijadwalkan bersamaan
Periode
1 Teori Bilangan/ R001 Pemrograman Komputer Bahasa Indonesia/ R002 Periode 2 Kalkulus I/ R002 Geometri Bahasa Indonesia/ R001 Periode 3 Teori Bilangan/ R002 Statistika Matematika I
Bahasa Inggris/
R001 Periode 4
Teori Bilangan Penulisan Karya
Ilmiah/ R001
Kimia Dasar/ R001 Bahasa Inggris/
R002
Periode Pilihan MK yang bisa dijadwalkan bersamaan Periode 5 Matematika Diskrit Geometri/ R001 Kewirausahaan/ R002 Biologi Umum/ R001 Kimia Dasar/ R002 Periode 6 Metode Numerik/ R002 Kewirausahaan/ R001 Pancasila/ R002 Agroindustri Dan Green Teknologi Periode 7 Persamaan Diferensial Parsial/ R001 Analisis Real II/ R002 Biologi Umum/ R002 Pancasila/ R001 Periode 8 Aljabar Linier Elementer Penulisan Karya Ilmiah/ R002 Fisika Dasar/ R002 Periode 9 Persamaan Diferensial Parsial/ R002 Analisis Real II/ R001 Kalkulus I/ R001
Periode 10
Metode Numerik/ R001 Geometri/ R002 Kalkulus Lanjut Fisika Dasar/ R001
Untuk  mata  kuliah  Agama  I  (yaitu  Agama  Islam,  Agama  Katolik,  Agama  Protestan,  Agama Hindu  dan  Agama  Budha),  dan  mata  kuliah  pilihan  yang  tidak  dilibatkan  dalam  pemodelan  graf selanjutnya dapat diatur sedemikian sehingga tidak dilakukan pada jadwal yang bersamaan dengan mata kuliah lain yang diikuti oleh himpunan mahasiswa yang sama ataupun diampu oleh dosen yang sama.

## 4. Kesimpulan
Permasalahan penyusunan jadwal dapat diselesaikan secara matematis melalui pemodelan graf. Pada  penelitian  ini,  himpunan  mahasiswa,  nama  mata  kuliah  dan  dosen  pengampu  mata  kuliah tersebut diasumsikan sebagai satu kesatuan untuk menjadi suatu verteks pada graf. Sedangkan dua verteks (dua mata kuliah) yang diikuti oleh himpunan mahasiswa yang sama ataupun diampu oleh dosen  yang  sama  dalam  pemodelan  graf  pada  penelitian  ini  akan  dihubungkan  dengan  suatu  sisi sehingga  kedua  verteks  menjadi  bertetangga.  Hubungan  ketetanggaan  antara  dua  verteks  ini dinyatakan  sebagai  sisi  pada  graf.  Banyak  verteks  dalam  pemodelan  pada  penelitian  ini  adalah sebanyak 36 verteks dengan 215 sisi. Dengan menggunakan algoritma Welch Powell, maka diperoleh pengelompokan  mata  kuliah  yang  bisa  dijadwalkan  pada  waktu  yang  sama,  hingga  diperoleh kesimpulan pada setiap minggu, 36 mata kuliah dapat dijadwalkan minimal dalam 10 sesi atau 10 periode. Dengan adanya pengelompokan mata kuliah yang dapat dijadwalkan pada waktu yang sama ataupun  mata  kuliah  yang  tidak  dapat  dijadwalkan pada  waktu  yang  sama,  maka kegiatan  menata jadwal perkuliahan terasa lebih ringan dan lebih efisien.

## Referensi
[1] C. H. Meiliana and D. Maryono, “Aplikasi Pewarnaan Graf Untuk Optimalisasi Pengaturan Traffic  Light  Di  Sukoharjo,” J.  Ilm.  Pendidik.  Tek.  dan  Kejuru. ,  vol.  10,  no.  1,  2017,  doi: 10.20961/jiptek.v7i1.12662.
[2] D. A. Setiawan, A. Suyitno, and I. Artikel, “Penerapan Graf Pada Persimpangan Menggunakan Algoritma Welsh-Powel Untuk Optimalisasi Pengaturan Traffic Light,” Unnes J. Math. , vol. 5, no. 2, pp. 144–152, 2016.
[3] A.  R.  Komijan  and  M.  N.  Koupaei,  “A  new  binary  model  for  university  examination timetabling: a case study,” J. Ind. Eng. Int. , vol. 8, no. 1, pp. 1–7, 2012, doi: 10.1186/2251- 712X-8-28.
[4] S. Daskalaki, T. Birbas, and E. Housos, “An integer programming formulation for a case study in  university  timetabling,” Eur.  J.  Oper.  Res. ,  vol.  153,  no.  1,  pp.  117–135,  2004,  doi: 10.1016/S0377-2217(03)00103-6.
[5] A.  Cerdeira-Pena,  L.  Carpente,  A.  Fariña,  and  D.  Seco,  “New  approaches  for  the  school timetabling problem,” 7th Mex.  Int. Conf. Artif. Intell. - Proc. Spec. Sess. MICAI 2008 , no. December, pp. 261–267, 2008, doi: 10.1109/MICAI.2008.19.
[6] M. Yulistiana, D. Chaerani, and E. Lesmana, “Penerapan Metode Hungarian dalam Penentuan Penjadwalan  Matakuliah  Optimal  (Studi  Kasus:  Departemen  Matematika  Universitas Padjadjaran Semester Ganjil 2013-2014),” J. Mat. Integr. , vol. 11, no. 1, pp. 45–64, 2015, doi: 10.24198/jmi.v11i1.9391.
[7] W.  Tahir,  D.  Wungguli,  and  M.  R.  F.  Payu,  “Optimasi  Penjadwalan  Waktu  Kerja Menggunakan Integer Programming,” Euler  J. Ilm. Mat. Sains dan Teknol. , vol. 7, no. 2, pp. 51–55, 2019, doi: 10.34312/euler.v7i2.10343.
[8] E. K. Burke, B. McCollum, A. Meisels, S. Petrovic, and R. Qu, “A graph-based hyper-heuristic for educational timetabling problems,” Eur. J. Oper. Res. , vol. 176, no. 1, pp. 177–192, 2007, doi: 10.1016/j.ejor.2005.08.012.
[9] M. T. M. Perera and G. H. J. Lanel, “A Model to Optimize University Course Timetable Using Graph Coloring and Integer Linear Programming,” IOSR J. Math. , vol. 12, no. 05, pp. 13–18, 2016, doi: 10.9790/5728-1205031318.
[10]  K.  H.  Rosen, Discrete  Mathematics  and  Its  Aplications ,  7th  ed.  New  York:  McGraw-Hill, 2012.
[11]  E. Kreyszig, Advanced Engineering Mathematics , 10th ed. Wiley, 2011.
[12]  C. Vasudev, Graph Theory with Applications . New Delhi: New Age International (P) Limited, 2006.
[13]  R. Munir, Matematika Diskrit , Rev ke 5. Bandung: Informatika Bandung, 2016.
[14]  R. J. Wilson, Introduction to Graph Theory , 4th ed. Longman, 1996.
[15]  N.  Deo, Graph  Theory  with  Applications  Engineering  and  Computer  Science .  New  York: Prentice-Hall, 1974.