## EULER: Jurnal Ilmiah Matematika, Sains dan Teknologi
Penerapan Algoritma Welch-Powell Pada Penyusunan Jadwal Perkuliahan di Program Studi Pendidikan Matematika
Ririn Mufidatur Rohmawati 1 *, M. Ivan Ariful Fathoni 1 , Ismanto 1
1 Prodi Pendidikan Matematika, Universitas Nahdlatul Ulama Sunan Giri, Jl. Ahmad Yani No. 10 Bojonegoro, Indonesia
*Penulis Korespondensi. Email: mufidatur14@gmail.com

## Abstrak
Teori  graf  dapat  diterapkan  dalam  penjadwalan  mata  kuliah.  Permasalahan  yang  di  bahas  pada penelitian ini yaitu pengaturan penjadwalan mata kuliah di Program Studi Pendidikan Matematika UNUGIRI dengan menggunakan pewarnaan graf. Tujuan dari penelitian ini yaitu untuk mencegah terjadinya  tumpang  tindih  ( cross-over) dalam  penyusunan  mata  kuliah. Penjadwalan  yang  baik merupakan  sebuah penjadwalan yang  dapat dilakukan oleh  seluruh pihak terkait dalam kegiatan belajar-mengajar. Algoritma yang digunakan dalam penelitian ini yaitu algoritma Welch-Powell . Penelitian dilakukan menggunakan metode deduktif aksiomatik dengan menurunkan aksioma atau teorema yang telah ada, kemudian diterapkan dalam pewarnaan simpul pada representasi graf dari penjadwalan perkuliahan program studi pendidikan matematika UNUGIRI. Berdasarkan algoritma Welch-Powell diperoleh  matriks  kesiapan  mengajar  mata  kuliah  semester  ganjil  Th.  2022/2023 dengan  enam  warna  yang  berbeda.  Keenam  warna  tersebut  merepresentasikan  penjadwalan  26 matakuliah  Program Studi  Pendidikan Matematika  UNUGIRI ke  dalam  enam hari  tanpa adanya tumpang tindih ( cross-over) .
Kata Kunci: Graf; Algoritma Welch-Powell ; Simpul; Penjadwalan Mata Kuliah

## Abstract
Graph  theory  can  be  applied  in  course  scheduling.  The  problem  discussed  in  this  study  is scheduling courses in the UNUGIRI Mathematics Education Study Program using graph coloring. The purpose of this study is to prevent the occurrence of overlap (cross-over) in the preparation of courses. Good scheduling is a schedule that can be carried out by all related parties in teaching and  learning  activities.  The  algorithm  used  in  this  study  is  the  Welch-Powell  algorithm.  The research  was  conducted  using  an  axiomatic  deductive  method  by  deriving  existing  axioms  or theorems, then applied to vertex coloring on the graph representation of the lecture scheduling of the UNUGIRI mathematics education study program. The readiness matrix to teach odd-semester courses is obtained based on the Welch-Powell algorithm. 2022/2023 with six different colors. The six colors represent the scheduling of 26 UNUGIRI Mathematics Education Study Program courses into six days without any cross-over.
Keywords: Graph; Welch-Powell Algorithm; Vertex; Course Scheduling

## 1. Pendahuluan
Kemajuan ilmu pengetahuan mengambil bagian yang signifikan dalam menangani persoalan persoalan  di  kehidupan  sehari-hari.  yang  disebut  masalah  tidak  dapat  dipisahkan  dari  manusia. Permasalahan  yang  ada  sering  kali  menyangkut  –  pautkan  beberapa  aspek,  dalam  menyelesaikan masalah memerlukan suatu metode penalaran tertentu atau ilmu tertentu. Salah satu bidang ilmu yang dapat digunakan untuk menangani suatu permasalahan saat ini adalah aritmatika. Matematika adalah salah  satu  cabang  pengetahuan  yang  dapat  digunakan  untuk  mempermudah  penyajian  dan pemahaman  masalah.  Salah  satu  alat  yang  dapat  membantu  menyederhanakan  penyajian  masalah adalah model matematika. Pada pembahasan model matematika, suatu masalah dapat lebih sederhana untuk dipahami, disajikan dianalisis, dan diselesaikan, baik secara numerik maupun secara analitik.
Salah  satu  bidang  ilmu  matematika  yang  biasa  menyederhanakan  penyajian  masalah  dalam kehidupan sehari-hari adalah teori graf [1].
Teori graf merupakan bagian dari matematika yang dapat membantu dalam menemukan solusi untuk  masalah  di  beberapa  bidang. Bidang  matematika  ini  memiliki  beberapa  keunggulan  untuk menyelesaikan  masalah  dalam  kehidupan  sehari-hari  dan  di  masyarakat.  Teori  graf  diperkenalkan oleh  seorang  matematikawan  bernama  Leonhard  Euler  pada  tahun  1736.  Ide  muncul  ketika memecahkan masalah jembatan Konigsberg, Euler kemudian memodelkan masalah tersebut dalam bentuk  graf  dengan  mengasumsikan  massa  daratan  sebagai  simpul  dan  jembatan  yang menghubungkan  dua  massa  tanah  sebagai  graf  satu  sisi  [2].  Teori  graf  adalah  cabang  matematika diskrit  yang  menarik  untuk  membahas  masalah  yang  berkaitan  dengan  masalah  sehari-hari  [3]. Meskipun  graf  adalah  model  matematika  yang  sangat  rumit  dan  menantang,  graf  dapat  menjadi jawaban yang sangat praktis untuk beberapa masalah. Oleh karena itu, representasi graf tergantung pada sifat data dan operasi yang dilakukan pada  data kasus tertentu  [4].  Suatu masalah fisik yang konkrit dapat direpresentasikan dengan sebuah graf [5] .
Teori graf memiliki aplikasi yang sangat luas karena berbeda dan memiliki banyak keunikan, teori graf saat ini berkembang dan menarik. Meluasnya penggunaan teori graf dalam berbagai bidang ilmu pengetahuan dan dalam kehidupan sehari-hari merupakan salah satu faktor yang berkontribusi terhadap perkembangannya yang pesat [6]. Kesederhanaan topik yang dicakup oleh teori graf, yang dapat  direpresentasikan  sebagai  simpul  dan  sisi,  membuatnya  istimewa.  Salah  satu  permasalahan yang memanfaatkan teori graf yaitu masalah penjadwalan mata kuliah di Perguruan Tinggi. Pihak Perguruan Tinggi harus berhati-hati dalam memilih strategi penjadwalan yang akan digunakan untuk membuat  jadwal  perkuliahan  karena  beragamnya  teori  penjadwalan  yang  ada.  Tentunya  hal  ini merupakan  tugas  yang  cukup  sulit.  karena  Perguruan  Tinggi  harus  memiliki  urutan  proses pembelajaran yang baik agar mencapai tujuan yang maksimal [7].
Konsep pada teori graf biasanya sering muncul sesuai dengan kebutuhan dan kenyataan yang terjadi  pada  bidang  tertentu  seperti  halnya  penjadwalan  [8].  Penjadwalan  mata  kuliah  termasuk masalah  yang  selalu  menjadi  perioritas  Perguruan  Tinggi  yang  perlu  penanganan  khusus  di  setiap awal semester atau tahun akademik. Penjadwalan mata kuliah dalam aplikasi teori graf menggunakan matriks  ruang-waktu  untuk  menvisualisasikan  elemen  penjadwalan  yang  berbeda.  Universitas Nahdlatul  Ulama  Sunan  Giri  (UNUGIRI)  Salah  satu  perguruan  tinggi  yang  secara  rutin  membuat jadwal mata kuliah setiap awal tahun akademik. Studi kasus dalam penelitian ini adalah penjadwalan mata  kuliah  di  Program  Studi  Pendidikan  Matematika,  Fakultas  Keguruan  dan  Ilmu  Pendidikan. Penjadwalan mata pelajaran di Program Studi Pendidikan Matematika UNUGIRI ini masih secara manual  dengan  menggunakan  bantuan  Microsoft  Excel,  sehingga  memakan  banyak  waktu  dan memungkinkan terjadinya human error dan bentrok antar jadwal matakuliah.
Penyusunan  jadwal  dengan  menggunakan  Graf  pernah  pernah  dilakukan  sebelumnya  oleh Yahya,  dkk.  [9]. Penyusunan  jadwal  yang  dilakukan  menggunakan  penyusunan  graf  penjadwalan yang terdiri dari mata kuliah, ruang kuliah, dan tim dosen yang siap mengampu mata kuliah masing- masing strata semester  setiap  harinya. Penerapan  pewarnaan  graf  juga  dilakukan  oleh  Yakin  [10] pada penjadwalan perkuliahan Prodi Pendidikan Biologi. Penelitian ini dilakukan untuk menghindari bentrok  jadwal,  baik  dalam  hal  penggunaan  ruang  kuliah  maupun  alokasi  waktu  perkuliahan. Berdasarkan  alasan  tersebut,  maka  penjadwalan  dengan  menggunakan  pewarnaan  graf  dalam penelitian  ini  menggunakan  algoritma Welch-Powell .  Algoritma Welch-Powell adalah  algoritma pemecahan masalah penjadwalan, Aladağ and Hocaoğlu [11] menyatakan bahwa algoritma Welch- Powell sering  digunakan  untuk  mewarnai  graf  dengan  jumlah  warna  sesedikit  mungkin  dengan mengurutkan semua simpul berdasarkan derajat, dari derajat paling besar ke derajat paling kecil. Pada penelitian  Supiyandi  dan  Eka  [12],  algoritma Welch-Powell diterapkan  dalam  penjadwalan  ujian semester.  Algoritma  ini  pernah  digunakan  juga  untuk  pewarnaan  graf  dalam  penjadwalan  mata
pelajaran di sekolah [13]. Hasil penelitian menghasilkan jadwal pelajaran, dimana jika ada dua kelas yang memiliki mata pelajaran yang sama, dapat dijadwalkan pada hari yang sama namun dalam jam yang  berbeda.  Sehingga  didapatkan  jadwal  pelajaran  yang  tidak  ada  bentrok  antar  guru,  mata pelajaran, dan jam mengajar. Berbeda dengan penelitian sebelumnya, dalam penelitian ini algoritma Welch-Powell diterapkan dalam penjadwalan matakuliah.
Alokasi  waktu (sesuai SKS untuk setiap mata  kuliah), ketersediaan dosen di masing-masing program studi, dan ketersediaan ruang kuliah menjadi kendala dalam perencanaan jadwal perkuliahan di  kampus.  Salah  satu  program  studi  yang  bermasalah  dengan  penjadwalan  adalah  Program  studi Pendidikan  Matematika  UNUGIRI.  Saat  membuat  jadwal  kuliah,  penting  untuk  mengalokasikan waktu kuliah, mengidentifikasi presenter, dan menentukan ruang kuliah. Sedangkan jenjang semester di  Program  studi  Pendidikan  Matematika  UNUGIRI  ada  bermacam-macam,  mulai  dari  semester pertama sampai semester tujuh (untuk semester individu) dan dari semester kedua sampai semester delapan (sampai semester). Penggunaan ruang kuliah dan penjadwalan dosen yang tumpang tindih merupakan masalah penjadwalan yang umum terjadi di kampus. Selain itu, jadwal perkuliahan saat ini melampaui jumlah jam yang telah dialokasikan untuk perkuliahan berdasarkan SKS untuk setiap mata  kuliah.  Oleh  karena  itu,  diperlukan  sistem  penjadwalan  perkuliahan  yang  lebih  efektif  guna meningkatkan  efektifitas  dan  efisiensi  pembelajaran  di  kampus.  Berdasarkan  uraian  penjelasan tersebut,  maka  tujuan  dari  penelitian  ini  adalah  “mengimplementasikan  pewarnaan  graf  dalam penjadwalan  mata  kuliah  di  Program  Studi  Pendidikan  Matematika  UNUGIRI  menggunakan algoritma Welch-Powell” .

## 2. Metode Penelitian
Penelitian  dilakukan  menggunakan  metode  deduktif  aksiomatik,  yaitu  dengan  menurunkan aksioma  atau  teorema  yang  telah  ada,  kemudian  diterapkan  dalam  pewarnaan  simpul  pada representasi graf dari penjadwalan perkuliahan program studi pendidikan matematika semester ganjil tahun  akademik  2022/2023  Fakultas  Keguruan  dan  Ilmu  Pendiddikan  UNUGIRI.  Penjawalan merupakan alokasi dari sumber daya terhadap waktu untuk menhasilkan sebuah kumpulan pekerjaan.
Penelitian  ini  diawali  dengan  menetukan  variabel-variabel  yang  terlibat  yaitu,  mata  kuliah, mahasiswa, rangan, dosen dan waktu yang akan digunakan untuk menyususn penjadwalan. Berikut langkah-langkah dalam penelitian ini adalah:
1) Studi Literatur
Tahap  ini  dilakukan  pengumpulan  teori  yang  digunakan  menjadi  dasar  teori  dengan Penelusuran Jurnal/Reverensi dari internet atau buku untuk memperoleh deskripsi yang lebih jelas mengenai pengaturan waktu ( timetabel ), Algoritma Welch powell dan pewarnaan Graf.
2) Pengumpulan data
Data yang digunakan dalam penelitian ini adalah daftar pengampu matakuliah dan kesediaan mengajar  dosen  Fakultas  Keguruan  dan  Ilmu  Pendidikan  untuk  semester  ganjil  tahun  akademik 2022/2023.
3) Mempresentasikan data ke dalam bentuk graf bipartit
Pemanfaatan algoritma dalam mengimplementasikan metode algoritma Welch-Powell terhadap masalah yang dihadapi diperlukan data berupa graf. Sehingga perlu dilakukan konversi data.
4) Mengimplementasikan hasil
Hasil  penerapan  algoritma Welch-Powell dijadikan  dasar  pertimbangan  untuk  menentukan kombinasi dosen dan mata kuliah yang diampu. Kombinasi dosen dan mata kuliah yang diperoleh akan dipetakan menjadi jadwal penempatan kelas dosen dengan mata kuliah yang diampu.

## 3. Hasil dan Pembahasan
Distribusi jadwal untuk dosen menawarkan informasi tentang ketersediaan dosen mengajar di semester  ganjil  Th.  2022/2023  serta  informasi  akses  dosen  terhadap  waktu  mengajar.  dosen  yang bersedia di tempatkan dikelas manapun pada semester ganjil Th. 2022/2023 atas kebijaksanaan dosen, di samping kemauan dan pengalaman yang diminati dosen untuk mata kuliah tersebut.
Tabel 1 menjelaskan bahwa dalam penelitian ini menggunakan algoritma Welch-Powell yang digunakan  untuk  menerapkan  pewarnaan  simpul  pada  grafik  dengan  terlebih  dahulu merepresentasikan  mata  kuliah  sebagai  simpul  dan  kemudian  dosen  sebagai  sisi  yang menghubungkan kedua simpul tersebut. Dosen yang menyatakan keinginannya tanpa menyebutkan jam ketersediaan dapat diartikan siap setiap saat sepanjang hari dengan membagi waktu kuliah pagi dan kuliah siang. Dosen yang cuti atau tidak ada bahan ajar tidak ditampilkan pada semester ganjil Th. 2022/2023. Data ditampilkan pada Tabel 1 untuk memudahkan pengamatan. Keterkaitan dosen dengan mata kuliah yang diampunya digambarkan pada Tabel 1. Jika memiliki nilai 1 berarti dosen tersebut terbuka untuk mengajar kelas sesuai dengan minat dan latar belakangnya. Sebaliknya, jika nilainya  0,  menunjukkan  bahwa,  mengingat  keahlian  dan  minat  dosen,  dosen  tidak  siap  untuk mengajar mata kuliah tersebut.
Tabel 1. Hubungan Dosen dengan Mata Kuliah
Semester Mata Kuliah Dos en A Dos en B Dos en C Dos en D Dos en E Dos en F Dos en G Dos en H Dos en I Dos en J Dos en K Dos en L Dos en M 1 Pendidikan Pancasila 0 0 1 0 0 0 0 0 0 0 0 0 0 Pendidikan Agama Islam 0 0 0 0 0 0 0 0 1 1 0 1 0 Aswaja 1 0 0 0 0 0 1 0 0 1 0 0 0 0 Kalkulus 1 1 0 0 0 0 0 0 1 0 0 0 0 0 Program dan Aplikasi Komputer 0 0 0 0 1 0 0 0 0 0 0 0 0 Pengantar Dasar Matematika 0 1 0 0 0
0 0 0 0 0 0 0 0 Pengembangan Peserta Didik 0 0 0 0 0
0 1 0 0 0 0 0 0 Telaah Kurikulum 0 0 0 0 0
0 1 0 0 0 0 0 0 3 Bahasa Inggris 0 0 0 0 0
0 0 0 0 0 1 0 1 Kalkulus Lanjut 0 0 0 0 0
0 0 1 0 0 0 0 0 Geometri Dasar dan Ruang 0 1 0 1 0 0 0 0 0 0 0 0 0 Persamaan Diferensial Biasa 0 0 0 0 1 0 0 0 0 0 0 0 0 Struktur Aljabar 0 0 0 1 0 0 0 1 0 0 0 0 0 Teori Bilangan 1 0 0 1 0 0 0 0 0 0 0 0 0 Matematika Sekolah II 1 0 0 0 0 0 1 0 0 0 0 0 0 Media Pembelajaran 0 1 0 0 0 0 0 0 0 0 0 0 0 5 Participatory Action Research 0 0 0 0 0 0 0 0 0 0 0 1 0 Filsafat Ilmu 0 0 1 0 0 0 0 0 0 0 0 0 0 Geometri Transformasi 0 0 0 0 1 0 0 0 0 0 0 0 0 Metode Numerik 0 0 0 0 0 0 0 1 0 0 0 0 0 Metode  Penelitian  Pendidikan dan Penulisan Ilmiah 1 1 0 0 0 0 0 0 0 0 0 0 0 Teori Graf 0 0 0 1 0 0 0 0 0 0 0 0 0 Evaluasi Pembelajaran 0 0 0 0 0 0 1 0 0 0 0 0 0 Psikologi Pendidikan 0 1 0 0 0 0 0 0 0 0 0 0 0 Geometri Non Euclid 0 0 0 0 1 0 0 0 0 0 0 0 0 Teori Grup Hingga 0 0 0 1 0 0 0 0 0 0 0 0 0 7 PPL 0 0 0 0 0 0 0 0 0 0 0 0 0 KKN 0 0 0 0 0 0 0 0 0 0 0 0 0
Setelah  fokus  pada  kesiapan  untuk  mengajar  mata  kuliah,  perpaduan dosen  dan  mata  kuliah dibuat. Satu dosen dapat mengajar beberapa mata kuliah, dan beberapa dosen dapat mengajar satu mata  kuliah  untuk  mengatasi  masalah  kelas.  Sesuai  dengan  kelas  dan  mata  kuliah  yang  tersedia, pembagian kelas diterapkan pada setiap kombinasi dosen dan mata kuliah.
Tabel 2. Hasil kombinasi dosen dan mata kuliah ( Matriks Adjacency )
Verte x V 1 V 2 V 3 V 4 V 5 V 6 V 7 V 8 V 9 V 1 0 V 1 1 V 1 2 V 1 3 V 1 4 V 1 5 V 1 6 V 1 7 V 1 8 V 1 9 V 2 0 V 2 1 V 2 2 V 2 3 V 2 4 V 2 5 V 2 6 V1 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0 V2 0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0 V3 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 V4 0  0  0  0  0  0  0  0  0  1  0  0  1  1  1  0  0  0  0  1  1  0  0  0  0  0 V5 0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  1  0 V6 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  1  0  0  1  0  0 V7 0  0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  1  0  0  0 V8 0  0  0  0  0  0  1  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  1  0  0  0 V9 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 V10 0  0  0  1  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0 V11 0  0  0  0  0  1  0  0  0  0  0  0  1  1  0  1  0  0  0  0  1  1  0  1  0  1 V12 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  1  0 V13 0  0  0  1  0  0  0  0  0  1  1  0  0  1  0  0  0  0  0  1  0  1  0  0  0  1 V14 0  0  0  1  0  0  0  0  0  0  1  0  1  0  1  0  0  0  0  0  1  1  0  0  0  1 V15 0  0  0  1  0  0  1  1  0  0  0  0  0  1  0  0  0  0  0  0  1  0  1  0  0  0 V16 0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  0  0  0  0  0  1  0  0  1  0  0 V17 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 V18 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 V19 0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  1  0 V20 0  0  0  1  0  0  0  0  0  1  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0 V21 0  0  0  1  0  1  0  0  0  0  1  0  0  1  1  1  0  0  0  0  0  0  0  1  0  0 V22 0  0  0  0  0  0  0  0  0  0  1  0  1  1  0  0  0  0  0  0  0  0  0  0  0  1 V23 0  0  0  0  0  0  1  1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0 V24 0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  1  0  0  0  0  1  0  0  0  0  0 V25 0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  0
V26 0  0  0  0  0  0  0  0  0  0  1  0  1  1  0  0  0  0  0  0  0  1  0  0  0  0
Berdasarkan hasil kombinasi dosen dan mata kuliah ( matriks adjacency ) pada Tabel 2 adalah matriks yang baris dan kolomnya disusun berdasarkan urutan simpulnya dengan pemberian angka 1 jika dua simpul terhubung oleh kedua sisinya, dan angka 0 jika simpul tidak keterhubungan [14].
Algoritma Welch-Powell merupakan  salah  satu  algoritma  yang  dapat  digunakan  untuk menambah warna pada suatu graf dengan cara mengarsir simpul-simpul ( vertex ), seperti pada Tabel 2. Langkah-langkah dalam algoritma Welch-Powell [15] adalah sebagai berikut:
1) Mengatur semua simpul dalam urutan derajat, dari terbesar ke terkecil.
2) Mengambil warna pertama (misalnya kuning) untuk mewarnai simpul pertama (yang memiliki skor tertinggi). Kemudian warnai simpul yang tidak berdekatan dengan simpul pertama dengan warna yang sama (kuning).
3) Melanjutkan pada warna kedua dan seterusnya, sampai semua simpul diwarnai.
Langkah-langkah algoritma welch-powell ditampilkan menggunakan diagram alur pada Gambar 1.
Gambar 1. Diagram Alur Algoritma Welch-powell
Hasil  dari  penerapan  kombinasi  dosen  dan  mata  kuliah  ( Matriks  Adjacency ) pada  Tabel  2. Berikutnya adalah penerapan simpul dan simpul tetangga yang disajikan pada Tabel 3. Representasi 26 simpul digambarkan dalam Graf pada Gambar 2.
Gambar 2. Representasi simpul
Cari simpul yang berderajat tinggi kemudian dijadikan simpul pertama Cari simpul yang tidak bertetangga dengan simpul utama Beri warna baru Ada ? Ada ? Beriwarna yang sama dengan simpul utama Start Selesai Tidak Tidak Iya Iya

## Tabel 3. Penerapan vertex dan simpul tetangga
Berdasarkan  Tabel  3,  diterapkan  pewarnaan  untuk  menentukan  warna  setiap  simpul  setelah mengklasifikasikan semua simpul. Teorema 2.1 menyatakan bahwa representasi graf akan digunakan dalam  penjadwalan  kelas  matematika  di  UNUGIRI  pada  Th.  2022/2023.  Setiap  mata  kuliah diwakilkan  sebagai  sebuah  simpul  ( vertex )  pada  grafik,  setidaknya  dua  daerah  yang  berbatasan langsung  (bertetangga)  menjadi  alasan  pengembangan  graf  tersebut,  seperti  pada  Gambar  3. Mengingat  Graf  memiliki  jumlah  derajat  tertinggi  8,  jelas  bahwa  graf  yang  digunakan  untuk menggambarkan  penjadwalan  mata  kuliah  pendidikan  matematika  memiliki  enam  warna  yang berbeda, seperti yang ditunjukkan pada Gambar 4. Warna-warna tersebut adalah merah, biru, hijau, kuning, ungu, dan orange.
Gambar 3. Representasi simpul (Mata Kuliah) Yang Bertetangga
Seperti  yang  terlihat  pada  gambar  4,  pewarnaan  simpul  (juga  dikenal  sebagai  pewarnaan simpul) yang melibatkan pemberian warna pada setiap simpul ( vertex ) yang tidak bisa sama dengan warna  simpul  terdekat.  Berdasarkan  pewarnaan  menggunakan  algoritma welch-powell dalam pewarnaan  graf  dalam  penelitian  ini  menggunakan  enam  warna.  Dari  enam  warna  tersebut  dapat diartikan bahwa jadwal perkuliahan program studi pendidikan matematika Th. 2022/2023 ada 6 hari
Simpul Simpul tetangga Simpul Simpul tetangga V1 V18 V14 V4, V11, V13, V15, V21, V22, V26 V2 V3, V17 V15 V4, V7, V8, V14, V21, V23 V3 V2 V16 V6, V11, V21, V24 V4 V10, V13, V14, V15, V20, V21 V17 V2 V5 V12, V19, V25 V18 V1 V6 V11, V16, V21, V24 V19 V5, V12, V25 V7 V8, V15, V23 V20 V4, V10, V13 V8 V7, V15, V23 V21 V4, V6, V11, V14, V15, V16, V24 V9 - V22 V11, V13, V14, V26 V10 V4, V13, V20 V23 V7, V8, V15 V11 V6, V13, V14, V16, V21, V22, V24, V26 V24 V6, V11, V16, V21 V12 V5, V19, V25 V25 V5, V12, V19 V13 V4, V10, V11, V14, V20, V22, V26 V26 V11, V13, V14, V22
dalam satu minggu. Yaitu hari senin sampaidengan hari sabtu, mulai dari semester 1 (satu) sampai semester 5 (lima).
Gambar 4. Pemberian Simpul (Mata Kuliah) Pada Graf
Hasil  pewarnaan  yang  diterapkan  pada  Tabel  1  Kemampuan  dosen  untuk  mengampu  mata kuliah ditampilkan pada Gambar 4, sangat mungkin beralasan bahwa banyak dosen yang memutuskan untuk menampilkan topik yang sama dan mendapatkan nada yang berbeda, dengan maksud bahwa dengan asumsi dosen mendapatkan kelas yang sama, mereka tidak dapat ditempatkan di kelas yang sama. Jika dosen yang bersangkutan mengajar di kelas yang sama, maka harus mengajar mata kuliah yang  berbeda.  Dari  Tabel  1  juga  terlihat  pemilihan  nama  dosen  yang  mengajar  mata  kuliah  yang berbeda dalam satu kelas.
Matriks yang ditunjukkan pada Tabel 2 mewakili hasil konversi dari Tabel 1. Pertimbangkan hubungan antara dosen dan topik sebelum memilih dosen dan mata kuliah yang akan dibahas. Dengan pemikiran ini, penempatan kelas dan kursus akan diperhitungkan. Hasil penerapan algoritma Welch- Powell terhadap  kemampuan  atau  kemauan  dosen  untuk  mengajar  mata  kuliah  yang  ditawarkan menghasilkan  enam  warna  dengan  gugusan  simpul  yang  kontras  dengan  warna  yang  ditunjukkan pada Tabel 4. Berdasarkan temuan ini, dimungkinkan untuk memetakan dosen dan mata kuliah yang ditawarkan  sesuai  dengan  jumlah  ruang  kelas  yang  tersedia,  memastikan  dosen  yang  memiliki preferensi mata kuliah yang sama duduk di kelas yang berbeda.
Tabel 4. Pengelompokan mata kuliah sesuai hari Warna Mata Kuliah Merah Pendidikan Agama Islam, Program Aplikasi Komputer, Teori Bilangan, Filsafat Ilmu, Evaluasi pembelajaran Biru Pendidikan  Pancasila,  Pengembangan  Peserta  Didik,  Persamaan Deferensial Biasa, Participatory Action Research, Psikologi Pendidikan Hijau Pengantar Dasar Matematika, Struktur Aljabar, Matematika Sekolah II Kuning Aswaja  I,  Kalkulus  I,  Telaah  Kurikulum,  Media  Pembelajaran,  Teori Graf Ungu Bahasa Inggris, Kalkulus Lanjut, Geometri Dasar dan Ruang, Geometri Non Euclid Orange   Geometri  Transformasi,  Metode  Numerik,  Metode  Penelitian  dan Penulisan Ilmiah, Teori Group Hingga
Setiap  warna  pada  Tabel  4  penjelasan  pewarnaan  menunjukkan  hari  kuliah,  oleh  karena  itu warna yang berbeda menunjukkan hari yang berbeda.
a) Warna merah menunjukkan hari senin
b) Warna biru menunjukkan hari selasa
c) Warna hijau menunjukkan hari rabu
d) Warna kuning menunjukkan hari kamis
e) Warna ungu menunjukkan hari jum’at
f) Warna orange menunjukkan hari sabtu
Berikut  adalah  tabel-tabel  hasil  dari  pemberian  warna  sesuai  jadwal  dan  kesediaaan  dosen dalam mengampu mata kuliah.
Tabel 5. Jadwal mata kuliah semester 01 No Kode MK Mata Kuliah Dosen Pengampu SKS Warna 1 UNU  101101  Pendidikan Pancasila Dosen C 2 2 UNU  101103  Pendidikan Agama Islam Dosen J 2 3 MMI  102101  Aswaja I Dosen I 2 4 MTK  104101  Kalkulus I Dosen A 3 5 MTK  104109 Program dan Aplikasi Komputer Dosen E 3 6 MTK  104120  Pengantar Dasar Matematika Dosen B 3 7 MTK  104122  Perkembangan Peserta Didik Dosen G 3 8 MTK  104123  Telaah Kurikulum Dosen G 3 Total 21
Berdasarkan  Tabel  5  terdapat  4  warna  pada  jadwal  mata  kuliah  disemester  1  pendidikan matematika UNUGIRI, yang artinya dalam 1 minggu masuk 4 hari yaitu hari senin, selasa, rabu, dan kamis.
Tabel 6. Jadwal mata kuliah semester 03 No Kode MK Mata Kuliah Dosen Pengampu SKS Warna 1 MPK 0008 Bahasa Inggris Dosen M 2 2 MKK 3403 Kalkulus Lanjut Dosen H 3 3 MKK 3406 Geometri Dasar dan Ruang Dosen D 3 4 MKK 3409 Persamaan Diferensial Biasa Dosen E 3 5 MKK 3415 Struktur Aljabar Dosen D 3 6 MKK 3420 Teori Bilangan Dosen A 3 7 MKB 3407 Matematika Sekolah II Dosen G 3 8 MKB 3409 Media Pembelajaran Dosen B 3 Total 23
Berdasarkan  Tabel  6  terdapat  5  warna  pada  jadwal  mata  kuliah  disemester  3  pendidikan matematika  UNUGIRI,  yang  artinya  dalam  1  minggu  masuk  5  hari  yaitu  hari  senin,  selasa,  rabu, kamis, dan jum’at.

## Tabel 7. Jadwal mata kuliah semester 05
Berdasarkan  Tabel  7  terdapat  5  warna  pada  jadwal  mata  kuliah  di  semester  5,  yang  artinya dalam 1 minggu masuk 5 hari yaitu hari senin, selasa, kamis, jum’at, dan sabtu.
Tabel 8. Jadwal mata kuliah semester 07
No Kode MK Mata Kuliah Dosen Pengampu SKS Warna 1 MPB 002 PPL TIM 3 2 MPB 003 KKN TIM 4 Total 7
Tabel 8 adalah jadwal mata kuliah semester 7 pendidikan matematika UNUGIRI, pada tabel tersebut terdapat 2 mata kuliah yaitu PPL dan KKN dalam 2 mata kuliah tersebut dosen pengampu adalah TIM yang terdiri dari beberapa dosen yang ada di Universitas untuk menjadi dosen pengampu atau dosen DPL (dosen pembimbing lapangan).

## 4. Kesimpulan
Berdasarkan hasil dari penelitian dan pembahasan di atas, sangat logis bahwa pewarnaan graf dapat  digunakan  dalam  penjadwalan  di  Prodi  Pendidikan  Matematika  UNUGIRI  untuk  mencegah terjadinya tumpang tindih  ( cross-over) . Penelitian ini menggunakan Algoritma Welch-Powell yang dapat  diterapkan  pada  penjadwalan  mata  kuliah  semester  ganjil  Th.  2022/2023  di  Program  Studi Pendidikan Matematika UNUGIRI dengan membentuk matriks penyesuaian antara kesediaan dosen untuk mengajar mata kuliah. Berdasarkan matriks kesiapan mengajar mata kuliah individual semester ganjil  Th.  2022/2023,  6  warna  dapat  digunakan.  Diantara  keenam  warna  tersebut,  jika  simpul  – simpulnya berwarna tidak sana, berarti simpul – simpul tersebut tidak bersebelahan, sehingga dapat ditempatkan  pada  kelas  yang  sama,  sedangkan  jika  simpul–simpul  tersebut  bersebelahan  dan memiliki warna Yang sama maka harus ditempatkan di kelas yang berbeda. Hal yang sama berlaku saat  mengajar  disiplin  ilmu  lain.  Tergantung  pada  ketersediaan  Matriks  Waktu  Pengajaran  pada semester individu 2022/2023, 6 (enam) warna simpul ini dapat dihasilkan. Keenam warna tersebut merepresentasikan penjadwalan 26 matakuliah Program Studi Pendidikan Matematika UNUGIRI ke dalam enam hari tanpa adanya tumpang tindih ( cross-over ).
No Kode MK Mata Kuliah Dosen Pengampu SKS Warna 1 MPK  0005  Participatory Action Research Dosen L 2 2 MPK  0006  Filsafat Ilmu Dosen C 2 3 MKK  3408  Geometri Transformasi Dosen E 2 4 MKK  3411  Metode Numerik Dosen H 3 5 MKK  3423 Metode Penelitian Pendidikan dan Penulisan Ilmiah Dosen A 3 6 MKK  3421  Teori Graf Dosen D 2 7 MKB  3405  Evaluasi Pembelajaran Dosen G 3 8 MKB  3412  Psikologi Pendidikan Dosen B 2 9 MKP  3401  Geometri Non Euclid Dosen E 2 10 MKP  3407  Teori Grup Hingga Dosen D 2 Total 23

## Referensi
[1] F. K. S. Dewi, “Pembangunan Perangkat Lunak Pembangkit Jadwal Kuliah dan Ujian Dengan Metode Pewarnaan Graf,” Jurnal Buana Informatika , 2010.
[2] V.  Cacchiani,  A.  Caprara,  and  P.  Toth,  “Finding  cliques  of  maximum  weight  on  a generalization of permutation graphs,” Optim Lett , vol. 7, no. 2, pp. 289–296, 2013.
[3] S. Wibisono, “Matematika diskrit,” Yogyakarta: Graha Ilmu , 2008.
[4] D.  T.  Salaki,  “Penentuan  lintasan  terpendek  dari  FMIPA  ke  Rektorat  dan  Fakultas  lain  di UNSRAT Manado menggunakan Algoritma Djikstra,” Jurnal Ilmiah Sains , vol. 11, no. 1, pp. 73–76, 2011.
[5] E. Goodaire and M. Parmenter, “Semi-simplicity of alternative loop rings,” Acta Mathematica Hungarica , vol. 50, no. 3–4, pp. 241–247, 1987.
[6] I. K. Budayasa, “Teori graph dan aplikasinya.” Surabaya: Unesa University Press, 2007.
[7] S. A. Kamaruddin, “Character education and students social behavior,” Journal of Education and Learning , vol. 6, no. 4, pp. 223–230, 2012.
[8] Y.  Setyawan,  “Visualisasi  Graf  dan  Algoritma-algoritma  dalam  Teori  Graf  Menggunakan Beberapa Paket Software,” in Makalah dipresentasikan pada Seminar Nasional Aplikasi Sains & Teknologi, Yogyakarta , 2014, vol. 15.
[9] N. I. Yahya, P. Zakaria,  and L. Yahya, “Penerapan Konsep Graf dalam Penyusunan Jadwal Perkuliahan di Jurusan Pendidikan Matematika FMIPA UNG,” Skripsi , vol. 1, no. 411409097, 2013.
[10]  A. H. A. Yakin, “Penerapan Pewarnaan Graf dalam Penyusunan Jadwal Perkuliahan di Prodi Pendidikan Biologi,” UNIVERSITAS MUHAMMADIYAH JEMBER, 2016.
[11]  Ç.  H.  Aladağ  and  G.  Hocaoğlu,  “A  tabu  search  algorithm  to  solve  a  course  timetabling problem,” Hacettepe journal of mathematics and statistics , vol. 36, no. 1, pp. 53–64, 2007.
[12]  S.  Supiyandi  and  M.  Eka,  “Penerapan  Teknik  Pewarnaan  Graph  Pada  Penjadwalan  Ujian Dengan  Algoritma  Welch-Powell,” ALGORITMA:  Jurnal  Ilmu  Komputer  dan  Informatika , vol. 2, no. 2, p. 58, 2019.
[13]  P.  S.  Wicaksono  and  K.  Kartono,  “ANALISIS  PENJADWALAN  MATA  PELAJARAN MENGGUNAKAN ALGORITMA WELCH-POWELL,” Prismatika: Jurnal Pendidikan dan Riset Matematika , vol. 3, no. 1, pp. 1–21, 2020.
[14]  C. Mukherjee and G. Mukherjee, “Role of adjacency matrix in graph theory,” IOSR J Comput Eng , vol. 16, no. 2, pp. 58–63, 2014, doi: https://doi.org/10.9790/0661-16235863.
[15]  S. Astuti, “Penyusunan Jadwal Ujian Mata Kuliah Dengan Algoritma Pewarnaan Graf Welch Powell,” Jurnal Dian , vol. 11, no. 1, 2011.