## Implementasi Algoritma Vizing Untuk Proses Pewarnaan Sisi Graf Pada Penjadwalan Kuliah
Tuty Sinaga, Hery Sunandar, Murdani
Teknik Informatika, Universitas Budi Darma, Medan, Indonesia Email: tutysinaga@gmail.com Submitted 09-06-2020; Accepted 28-08-2020; Published 31-10-2020
Abstrak
Pewarnaan titik adalah mewarnai semua titik pada graph 𝐺 , sehingga setiap pasang titik yang terhubung langsung memiliki warna yang berbeda. Pewarnaan titik dapat digunakan untuk membantu menyelesaikan masalah penyusunan jadwal kuliah. Salah satu algoritma untuk menyelesaikan masalah pewarnaan graph pada penjadwalan kuliah adalah algoritma vizing.  Hasil pewarnaan graph dengan menggunakan algoritma tabu search digunakan untuk menyusun jadwal kuliah, sehingga tidak ada jadwal yang bentrok artinya tidak ada dua matakuliah yang diambil oleh seorang mahasiswa yang dilaksanakan pada waktu yang bersamaan. Dengan demikian dapat ditentukan waktu dan ruang untuk melaksanakan perkuliahan sehingga dapat dibuat jadwal kuliah.  Untuk mempermudah menyelesaikan permasalahan tersebut  maka dibuat program dengan vb2008. Data yang diinputkan berupa mata kuliah, dosen dan kelas mahasiswa yang akan representasikan sebagai titik graph. Proses pewarnaan dimulai dari 𝑘 = 1 sehingga diperoleh warna yang lebih minimum. Output yang dihasilkan program berupa tabel jadwal kuliah yang telah ditentukan waktu dan ruang.
Kata Kunci: Pewarnaan titik graph, algoritma vizing, penjadwalan kuliah.

## Abstract
Dots coloring is coloring all points in graph 𝐺 , so that each pair of directly connected points has a different color. Point coloring can be used to help solve the problem of preparing class schedules. One algorithm for solving graph coloring problems in college sch eduling is the vizing algorithm. The results of graph coloring using the taboo search algorithm are used to arrange class schedules, so that there are no conflicting schedules meaning that no two courses taken by a student are carried out at the same time. Thus, time and space can be determined to carry out lectures so that a class schedule can be made. To make it easier to solve these problems, a program with vb2008 was created. The data entered in the form of courses, lecturers and student classes will be represented as point graphs. The coloring process starts from 𝑘 = 1 so that the minimum color is obtained. The output produced by the program is in the form of class schedules that have been determined by time and space.
Keywords: Point Graph Coloring, Vizing Algorithm, Lecture Scheduling.

## 1. PENDAHULUAN
STMIK Budi Darma Medan merupakan salah satu perguruan tinggi yang memberikan sebuah fasilitas untuk penjadwalan kuliah dalam sistem akademik di Perguruan Tinggi yang dilakukan setiap menghadapi semester baru. Pada pelaksaanaannya, seringkali  jadwal  yang  telah  dikeluarkan  belum  maksimal  sehingga  membutuhkan  adanya  penjadwalan  ulang.  Hal  ini mengakibatkan  perkuliahan  di  awal  semester  berjalan  tidak  efektif  karena  harus  melakukan  penyesuaian  jadwal  yang dikeluarkan.
Penjadwalan yang sering terjadi, jadwal perkuliahan untuk beberapa semester yang ada, ruang perkuliahan yang dipakai atau  yang  digunakan  saling  tumpang  tindih/tabrakan[1].  Karena  permasalahan  sering  yang  terjadi  pada  dosen  tertentu, misalkan  dosen  tidak  bisa  mengajar  pagi  karena kesibukan  rumah  tangganya.  Adapun  dosen  yang  tidak  sanggup  dengan jadwal  yang ada, karena dosen tersebut  mempunyai  jadwal  di fakultas lain atu  mengajar disekolah. Adapun masalah dari faktor kelas seperti kelas pratikum. Karena kelas pratikum tidak hanya dipakai oleh prodi itu saja, banyak prodi lain yang membutuhkan  ruang  pratikumnya.  Sehingga  membutuhkan  waktu  yang  efisien  untuk  menentukan  sebagai  jadwal pratikumnya  sebelum  membuat  jadwal  harus  mengetahui  permasalahan  yang  terjadi  agar  dosen,  kelas  dan  waktu  dapat ditentukan  dalam  penjadwalannya.  Oleh  karena  itu,  diperlukan  sistem  penjadwalan  perkuliahan  yang  efisen  agar pembelajaran dikampus dapat terlaksana lebih maksimal dan efisien.
Proses penjadwalan pada graf dimisalkan hari senin derajat maksimumnya ada tiga, sehingga pewarnaan minimal pada grafnya ada tiga warna. Untuk membuat pewarnaan graf pada hari senin  harus minimal tiga warna. Hal kedua yang akan dilihat dari pewarnaan sisi adalah waktu perkuliahan yang terjadi pada setiap ruang kuliah. Jadi pewrnaan graf yang akan dibuat  yaitu  pewarnaan  graf  antara  kelas  dan  ruang  kuliah.  Warna  yang  berbeda  menyatakan  bahwa  waktu  kuliah  bisa dilaksanakan hari yang sama. Jika ada tiga macam warna berarti dalam hari senin ada tiga waktu perkuliahan. Warna hitam untuk jam pertama, warna biru untuk jam kedua, warna kuning untuk waktu jam ketiga[2].

## 2. METODE PENELITIAN

## 2.1 Graf
Graf G didefinisikan  sebagai  pasangan  himpunan  ( V,  E ),  di  tulis  dengan  notasi G =  ( V, E ),  yang  dalam  hal  ini V adalah himpunan tidak kosong dari titik-titik ( vertices dan node ) dan E adalah himpunan sisi ( edges atau arcs ) yang menghubungkan sepasang titik.[3]
Graf merupakan struktur diskrit yang terdiri himpunan sejumlah berhingga objek yang di sebut simpul ( vertices, vertex ) dan himpunan  sisi  ( edges )  yang  menghubungkan  simpul-simpul  tersebut.  Terdiri  dari  graf  yang  di  gunakan  untuk
mempresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Notasi sebuah graf adalah G = ( V, E ). Di mana : 1. V merupakan himpunan tak kosong dari titik – titik ( vertices ).  Misalkan V = { 𝑉 1 , 𝑉 2 , …. 𝑉 𝑛 } 2. E merupakan himpunan sisi - sisi ( edges ) yang menghubungkan sepasang titik. Misalkan E = { 𝑒 1 , 𝑒 2 , 𝑒 𝑛 …. }.

## 2.2 Algoritma Vizing
Suatu pewarnaan sisi untuk graf G adalah suatu penggunaan sebagian atau semua K warna untuk mewarnai semua sisi di G sehingga setiap pasang sisi yang mempunyai titik persekutuan diberiwarna yang berbeda.[4] Teorema 1 (vizing)[4]:
Jika G adalah graph sederhana yang derajat maksimum titiknya adalah m, maka bilangan khromatiknya 𝑥(𝐺) adalah.
𝑚  ≤ 𝑥 (𝐺) ≤ 𝑚 + 1 (1)
Teorema 2 (vizing) [4] :
Jika G adalah graph sederhana bipartit yang derajat maksimum titiknya adalah 𝑚 , maka
𝑥 (𝐺) = 𝑚
(2)

## 2.3  Penjadwalan Kuliah
Jadwal  adalah  pembagian  waaktu  berdasarkan  rencana  pengaturan  kerja.  Sedangkan  penjadwalan  adalah  proses,  cara perbuatan  menjadwalkan  atau  memasukan  dijadwal.  Salah  satu  tingkah  pendidikan  yang  mengalami  permasalahan penjadwalan  adalah  perguruan  tinggi  dalam  hal  ini  penjadwalan  perkuliah[5].  Komponen  dari  masalah  penjadwalan perkuliah (Syadid, 2007) adalah :
1. Kelompok dari mahasiswa
2. Kelompok dari pengajar
3. Kelompok dari mata kuliah
4. Kelompok dari slot waktu yang telah ditentukan.

## 3. HASIL DAN PEMBAHASAN
Dalam analisa penjadwalan kuliah berdasarkan banyaknya mata kuliah untuk semester ganjil pada  jurusan teknik informatika beserta sksnya, ruangan, dosen dan kelas. Adapun banyaknya mata kuliah beserta bobot sksnya untuk semester I, II, V dan VII. Diantaranya untuk semester I terbagi dua kelas TI-P1402 dan TI-S1405 dengan 7 jumlah ruangan diantaranya di lantai 2 satu lab, dilantai 3 dengan tiga ruangan dan dilantai 4 tiga ruangan, semester III di kelas TI-S1406 dan TI-S1407 dengan 7 jumlah ruangan diantaranya dilantai 2 satu lab, dilantai 3 empat ruangan dan dilantai 4 dua ruangan, semester V di kelas TI- P1402 dan TI-P1403 dengan 9 jumlah ruangan diantaranya dilantai 2 dua ruangan, dilantai 3 empat ruangan dan dilantai 4 tiga ruangan dan semester VII di kelas  TI-S1409 dan TI-P1405 dengan 6 jumlah ruangan diantaranya dilantai 2 satu  lab, dilantai 3 tiga ruangan dan dilantai 4 dua ruangan.  Dimana terdapat  29 matakuliah dan dosen pengajar pada mata kuliah untuk semester ganjil 60 Dosen.
Menganalisa serta membagi setiap mata kuliah yang dipelajari untuk masing-masing tingkatan semester yang terbagi dalam dua kelas kedalam bentuk tabel.
Tabel 1. Semester I Mata Kuliah Semester SKS Hari Jam Ruangan Kelas Perangkat Lunak Aplikasi I 3 Senin 13.15-15.30 RT.305 TI-P1402 Pengantar Teknologi Informatika I 2 Senin 08.15-09.45 RT.401 TI-P1402 Logika dan Algoritma I 3 Senin 10.45-13.00 Lab.202 TI-S1405 Kalkulus I I 3 Selasa 08.15-10.30 RT.314 TI-S1405 Fisika I 3 Selasa 10.45-13.00 RT.415 TI-P1402 Bahasa Inggris I I 2 Kamis 11.45-13.15 RT.316 TI-P1402 Agama Kristen I 3 Kamis 08.15-10.30 RT.412 TI-S1405
Pada graf Teorema (vizing) Jika G adalah graf sederhana bipartit yang derajat maksimum titiknya adalah m, maka x (G) = m. Pada graf dari derajat maksimumnya ada tiga, sehingga pewarnaan minimal pada grafnya ada tiga warna. Untuk membuat pewarnaan graf pada semester ganjil dan genap harus minimal tiga warna.Pewarnaan sisi pada grafVizing untuk pewarnaan sisi pada graf: Jika G merupakan graf sederhana teratur, maka
𝑚 ≤ 𝑥(𝐺) ≤ 𝑚 + 1 χ’(G) = Δ(G) atau χ’(G) = Δ(G) + 1
Dengan Δ adalah derajat simpul graf teratur.Teorema pewarnaan sisi  graf lengkap: Untuk setiap graf lengkap Kn berlaku χ’(Kn) = n – 1 jika n ganjil dan χ’(Kn) = n jika n genap Algoritma pewarnaan sisi graf lengkap untuk n ganjil:
1. Berilah warna pada sisi-sisi luar yang membentuk segi-n dengan warna berbeda untuk setiap sisinya.
2. Sisi-sisi yang tersisa diberi warna yang sama dangan sisi luar jika sisi tersebut sejajar dengan salah satu sisi luar.
Algoritma pewarnaan sisi graf lengkap untuk n genap: 1. Hapus salah satu simpul sehingga graf menjadi graf lengkap dengan n ganjil.
2. Lakukan langkah pewarnaan sisi pada graf lengkap dengan n ganjil hingga tuntas.
3. Tambahkan kembali simpul yang dihapus dan hubungkan simpul tersebut dengan sisi berwarna ke simpul yang belum bersisian dengan simpul dengan warna tersebut. Pewarnaan sisi pada graf bukan semata-mata hanya untuk menandai sisi graf, tetapi juga bertujuan untuk mendapatkan warna seminimal mungkin untuk pewarnaannya
Dengan  terbatasnya  ketersedian  ruang  perkuliahan  dibandingkan  jumlah  kelas  pada  setiap  tingkatan  semester,  maka diperlukan jadwal yang efisien yang tidak saling tunpang tindih baik dalam hal ruang kuliah maupun waktu perkuliahan pada semester  ganjil  dan  semester  genap.  Oleh  karen  itu,  sebelumnya  membuat  graf  penjadwalan  perkuliahan  terlebih  dahulu merepsentasikan komponen-komponen dalam penjadwalan kedalam graf, dalam penerapan vizing memiliki fungsi titik ganjil dan titik genap. Adapun graf yang menggambarkan banyaknya matakuliah, dan tingkatan semester ganjil.
Gambar 1 . Graf Semester 1 Keterangan : v1 = Mata kuliah Perangkat lunak aplikasi jadwal kuliah hari senin dengan 3 SKS pada ruangan 305. v2 = Mata kuliah Pengantar Teknologi Informatika jadwal kuliah hari senin dengan 2 SKS pada ruangan RT.401 v3 = Mata kuliah Logika dan Algoritma di hari senin dengan 3 SKS pada ruangan Lab.202 v4 = Mata kuliah Kalkulus I jadwal kuliah di hari selasa dengan 3 SKS pada ruangan RT.314 v5 = Mata kuliah Fisika jadwal kuliah di hari selasa dengan 3 SKS pada ruangan RT.415 v6 `= Mata kuliah Bahasa Inggris I jadwal kuliah di hari kamis dengan 3 SKS pada ruangan RT.316 v7 = Mata kuliah Agama Kristen jadwal kuliah di hari kamis dengan 3 SKS pada ruangan RT.412 Pewarna dinamis G untuk n ≥ 3 m ≥ 3 :
Fungsi titik 𝐶 𝑛 𝐶 𝑚 Untuk n ganjil m ganjil : 1, v = 𝑥 𝑖 , 𝑗𝑥 𝑖 ,j+1 ; untuk 1 ≤ i ≤ m, jika j adalah ganjil, 1 ≤ j < n − 1 1, v = 𝑥 𝑖 , 𝑛𝑥 𝑖 +1,n ; jika i adalah ganjil 2, v = 𝑥 𝑖 , 𝑗𝑥 𝑖 ,j+1 ; untuk 1 ≤ i ≤ m, jika j adalah genap, 1 < j < n − 1 f ( v ) =  2, v = 𝑥 𝑖 ,1 𝑥 𝑖 ,1 ; jika i adalah ganjil 3, v = 𝑥 𝑖 , 𝑛𝑥 𝑖 ,1 ; untuk 1 ≤ i ≤ m 3, v = 𝑥 𝑖 , 𝑗𝑥 𝑖 +1,j ; jika i adalah ganjil, 1 < j < n –1
1, v1 : 3 + 1 untuk m ganjil
1, v2 : 2 + 1 untuk m ganjil
2, v3 : 3 + 1untuk m ganjil
Χ(G) = Xd (G) = 2, v4 : 3 + 1 untuk m ganjil 3, v5 : 3 + 1 untuk m ganjil
3, v6 : 2 + 1 untuk m ganjil
4, v7 : 3 + 1 untuk m 𝑣1 3 +𝑣2 3 + 𝑣3 3 +𝑣4 3 +𝑣5 3 +𝑣6 3 +𝑣7 3 ke n Χ(G) = Xd (G) = X3 (G) = 4, untuk m = 3, m ganjil
1, v1 : 3 + 1 = 4 untuk m ganjil< n − 1 1, v2 : 2 + 1 = 3 untuk m ganjil< n − 1 2, v3 : 3 + 1 = 4 untuk m ganjil< n − 1
Χ(G) = Xd (G) = 2, v4 : 3 + 1 = 4 untuk m ganjil< n − 1 3, v5 : 3 + 1 = 4 untuk m ganjil< n − 1 3, v6 : 2 + 1 = 3 untuk m ganjil< n − 1
4, v7 : 3 + 1 = 4 untuk m 𝑣1 3 +𝑣2 3 + 𝑣3 3 +𝑣4 3 +𝑣5 3 +𝑣6 3 +𝑣7 3 , ke n 1, v1 : 3 + 1 = 4 untuk m ganjil
1, v2 : 2 + 1 = 3 untuk m ganjil
2, v3 : 3 + 1 = 4 untuk m ganjil
Χ(G) = Xd (G) = 2, v4 : 3 + 1 = 4 untuk m ganjil 3, v5 : 3 + 1 = 4 untuk m ganjil
3, v6 : 2 + 1 = 3 untuk m ganjil
4, v7 : 3 + 1 = 4 untuk m 4 − 1 3 +3 − 1 3 + 4 − 1 3 +4 − 1 3 +4 − 1 3 +3 − 1 3 +4 − 1 3 , ke n
Χ(G) = Xd (G) = X3 (G) = untuk m 4 − 1 3 +3 − 1 3 + 4 − 1 3 +4 − 1 3 +4 − 1 3 +3 − 1 3 +4 − 1 3 Χ(G) = Xd (G) = X3 (G) = untuk m 3 3 +2 3 + 3 3 +3 3 +3 3 +2 3 +3 3 Χ(G) = Xd (G) = X3 (G) = untuk m 27 + 8 + 27 + 27 + 27 + 8 +27 Χ(G) = Xd (G) = X3 (G) = untuk m 151
Gambar 2. Titik simpul Semester I (Ganjil)
Keterangan : Warna kuning menjadwalkan hari senin dengan simpul : v1, v2, v3 Warna biru menjadwalkan hari selasa dengan simpul : v4, v5 Warna ungu menjadwalkan hari kamis dengan simpul : v6, v5, v7 v1 = Menjadwalkan mata kuliah Perangkat Lunak Aplikasi di hari senin dengan ruangan RT.305 jam 13.15-15.30Kelas TI-P1402
v2 = Menjadwalkan mata kuliah Perangkat Teknologi Informatika di hari senin dengan ruangan RT.401 08.15- 09.45Kelas TI-P1402
v3 = Menjadwalkan mata kuliah Logika dan Algoritma di hari senin dengan ruangan RT.305 10.45-11.00 dan pindah di Lab.202 jam 11.15-15.30
v4 = Menjadwalkan mata kuliah Kalkulus I di hari selasa dengan ruangan RT.314 jam 08.15-10.30Kelas TI-P1405 v5 = Menjadwalkan mata kuliah Fisika di hari selasa dengan ruangan RT.415 jam 10.45-13.00 Kelas TI-P1402 v6 = Menjadwalkan mata kuliah Bahasa Inggris I di hari kamis dengan ruangan RT.316 jam 11.45-12.00 dan pindah di RT.415 12.15-13.15Kelas TI-P1402
v7 = Menjadwalkan mata kuliah Agama Kristen di hari kamis dengan ruangan RT.412 jam 08.15-10.30 Kelas TI-P1405
Tabel 2. Penjadwalan Mata Kuliah Semester I Hari Jam Mata kuliah Ruangan Kelas W.1 W.2 W.3 W.4 Senin 13.15-15.30  Perangkat lunak aplikasi Perangkat lunak aplikasi  RT.305  RT.305 TI-P1402 08.15-09.45  Pengantar teknologi informatika RT.401 TI-P1402 10.45-11.00  Logika dan Algoritma Logika dan Algoritma RT.305  Lab.202  TI-S1405 Selasa  10.45-13.00  Kalkulus I RT.314 TI-P1405 13.00-15.30  Fisika RT.415 TI-P1402 Kamis  11.45-13.15  Bahasa Inggris I Bahasa Inggris I RT.316  RT.415 TI-P1402 13.15-15.30  Agama Kristen RT.412 TI-S1405 Keterangan : W1 : Warna 1
W2 : Warna 2 W3 : Warna 3 W4 : Warna 4.

## 3.1 Implementasi Program
Adapun nilai hasil beserta dataset di tampilkan dalam satu tampilan agar perhitungan jelas terlihat. Adapun tampilan output yang ditampilkan adalah data yang diketahui, dataset,probabilitas dan nilai  hasil analisa,  berikut  output yang ditampilkan data ujicoba, dataset, probabilitas dan nilai hasil, dapat di lihat di tampilan di bawah ini. Tampilan ini merupakan penjadwalan kuliah berdasarkan dari titik simpul pada pewarnaan graf. Adapun tampilan form tersebut dapat dilihat pada gambar dibawah ini.
Gambar 3. Penjadwalan kuliah.

## 4. KESIMPULAN
Berdasarkan  hasil  yang  di  dapat  dalam  penelitian  dapat  disimpulkan  proses  pewarnaan  graf  pada  penjadwalan  kuliah  ini mendapatkan jadwal yang minimal dalam jumlah hari, penggunaan ruang kuliah, bahkan waktu dalam perkuliahannya sangat minimal  dalam  perharinya.  Penerapan  Algoritma  Vizing  untuk  pewarnaan  sisi  graf  pada  penjadwalan  kuliah  dapat dipresentasikan secara graf G, dengan menganggap semester ganjil sebagai edge, baris penjadwalan kuliah berdasarkan hari sebagai vertex.

## REFERENCES
[1]   Hery sunandar, 2014, Studi Tentang Penyelamatan Traveling Salesman Dengan Menggunakan Metode Reduksi Pada Teori Graf (Studi Kasus :  Perusahaan Kimia Farma), Informasi dan Teknologi Illmiah (INTI). STMIK Budidarma Medan
[2]   Usman, Nurdin, 2002, Konteks Implementasi Berbasis Kurikulum Jakarta, PT. Raja Grafindo Persada.
[3]   Rinaldi Munir, matematika diskrit, (Cet. 3; Bandung: Informatika Bandung,2005 M), h 356-357.
[4]   Martopo, 2006. Petal Graphs Classification Based On Vizing’s Theorem.
[5] Andi  Helmi Ainul  Yakin,  2014,  Penerapan pewarnaan graf  dalam penyusunan jadwal  perkuliahan  di prodi pendidikan  biologi  : Bandung
[6] Adi Nugroho, 2010, Rekayasa Perangkat Lunak Menggunakan UML dan Java. Penerbit ANDI : Yogyakarta
[7] Priyanto, Rahmat, 2009, Langsung Bisa Visual Basic.Net 2008 ,Penerbit ANDI, Yogyakarta.
[8] Mulyana,Y.B, Trik Membangun PHP dan MySQL, Jakarta, penerbitElex Media Komputindo. 2004