## Pewarnaan  Fraksional  Fuzzy  Pada  Graf  Fuzzy  Beserta Aplikasinya Dalam Penjadwalan Ujian

## Muhammad Lutfi Prakasta, Arif Munandar.
Program  Studi  Matematika,  Fakultas  Sains  dan  Teknologi,  Universitas  Islam  Negeri  Sunan  Kalijaga Yogyakarta, Jl. Marsda Adisucipto No. 1 Yogyakarta 55281, Indonesia.
Korespondensi; Arif Munandar, Email: arif.munandar@uin-suka.ac.id

## Abstrak
Himpunan fuzzy dari waktu ke waktu terus berkembang. Himpunan fuzzy dikembangkan bersamaan dengan teori graf menghasilkan teori baru dinamakan graf fuzzy. Sebagaimana dalam teori graf terdapat pewarnaan, pada graf fuzzy juga terdapat pewarnaan. Inti pembahasan dari penelitian ini adalah pewarnaan fraksional fuzzy pada graf fuzzy. Pembahasan diawali dengan konsep dasar graf fuzzy dan pewarnaan graf fuzzy. Kemudian diakhiri dengan aplikasi penerapan pada penjadwalan ujian mahasiswa matematika.
Kata Kunci : Graf fuzzy, pewarnaan graf fuzzy, pewarnaan fraksional fuzzy.

## Abstract
Fuzzy sets will continue to develop from year to year. The development of fuzzy sets and graph theory resulted a new theory called fuzzy graphs. Similar to graph theory, fuzzy graphs also have coloring techniques. The main discussion of this research is fuzzy fractional coloring on fuzzy graphs. The discussion begins with the basic concepts of fuzzy graphs and fuzzy graph coloring. Then, at the end of the discussion also includes the application on scheduling student math exams.
Keywords : Fuzzy graph, coloring of fuzzy graph, fuzzy fractional coloring.

## Pendahuluan
Himpunan  tegas  merupakan  salah  satu  ilmu  dasar  matematika.  Himpunan  tegas  adalah  suatu pengelompokan objek-objek tertentu yang memiliki karakteristik  sama. Seiring perkembangan waktu, ditemukan  keterbatasan  dalam  penggunaan  himpunan  tegas,  misalnya  keambiguan  dalam  penentuang kelompok suhu, kelompok umur manusia, dan lain-lain.
Himpunan fuzzy adalah solusi dari keambiguan yang disebabkan oleh himpunan tegas. Fuzzy atau himpunan fuzzy pertama kali dikenalkan oleh [1] sebagai fenomena ketidakpastian di dunia nyata. Fuzzy merupakan salah satu dampak besar terhadap perkembangan teknologi saat ini.
Graf pertama kali dikenalkan oleh Euler pada tahun 1736 sebagai solusi dari jembatan konisbreg. Graf merupakan salah satu bentuk pengembangan dari himpunan tegas. Pewarnaan graf merupakan salah satu bagian dari graf yang paling banyak diaplikasikan pada kehidupan nyata. Salah satu aplikasinya adalah pada bidang penjadwalan.
Graf fuzzy yang diperkenalkan oleh [2], merupakan pengembangan dari teori graf dan relasi fuzzy. Konsep  dasar  graf  fuzzy  yang  meliputi  vertek  dan egde diperkenalkan  oleh  [3].  Konsep  dan  definisi tentang vertek, path, pohon, subgraph, serta komplemen dari graf fuzzy yang diperkenalkan oleh [4] atau [5]. Kemudian konsep tentang isomorfisma pada graf fuzzy diperkenalkan oleh [6]. Penelitian dalam [7] memperkenalkan konsep vertek adjacent kuat. Konsep tentang pewarnaan graf fuzzy diperkenalkan oleh
[8]  dengan  menggunakan 𝛼 − 𝑐𝑢𝑡 .  Setelah  itu  konsep lexicographic  product dari  dua  graf  fuzzy diperkenalkan oleh [9]. Kemudian [10] memperkenalkan konsep graf planar dan pewarnaan fuzzy pada graf fuzzy. Selanjutnya [11]  mengusulkan  suatu algoritma untuk menemukan himpunan fuzzy kromatik dari graf fuzzy. Konsep bilangan kromatik fuzzy pada gabungan dari graf fuzzy yang meliputi algoritma, sifat-sifatnya,  dan  aplikasi  diperkenalakan  oleh  [12].  Terakhir  [13]  memperkenalkan  konsep  baru pewarnaan  graf  fuzzy  yaitu  pewarnaan  fuzzy  fraksional . Penelitian  ini  kemudian  kami  kembangkan untuk optimalisasi penjadwalan ujian .

## Landasan Teori
Berikut  ini  diberikan  konsep-konsep  dasar  yang  akan  digunakan  pada  bagian  pembahasan,  meliputi definisi dan teorema.
Definisi 1. [14] Diberikan suatu graf 𝐺 = (𝑉, 𝐸) yang terdiri dari himpunan berhingga tak kosong vertek 𝑉(𝐺) dan himpunan berhingga edge 𝐸(𝐺) , sedemikian hingga:
1. Setiap edge 𝐸(𝐺) menghubungkan tepat dua vertek berbeda dalam G .
2.  Setiap  dua  vertek  dalam 𝑉(𝐺) dihubungkan  maksimal  oleh  1  edge  atau  tidak  terhubung  sama sekali.
Definisi 2. [1] Diberikan suatu himpunan fuzzy 𝐴 pada himpunan semesta X ditandai dengan fungsi yang dipetakan  pada [0, 1] ,  disebut  fungsi  keanggotaan (𝑚 ∶  𝑋  →   [0, 1]) .  Suatu  Himpunan  fuzzy 𝐴 dinotasikan dengan 𝐴 = (𝑋, 𝑚) .
Setelah  diberikan  definisi  dari  graf  dan  fuzzy,  selanjutnya  akan  diberikan  definisi  dari  graf  fuzzy. Berikut adalah definisi dari graf fuzzy.
Definisi 3. [2] Diberikan suatu graf fuzzy rangkap tiga 𝐺 = (𝑉, 𝜎, 𝜇) dengan dasar graf konvensional G*=(V,E)  dimana 𝜎 ∶  𝑉  →   [0, 1] adalah  suatu  himpunan  fuzzy  pada 𝑉 dan 𝜇 ∶  𝑉  × 𝑉  →   [0, 1] adalah suatu himpunan fuzzy pada 𝑉 × 𝑉 . Sedemikian hingga 𝜇(𝑎, 𝑏)   ≤  𝑚𝑖𝑛{𝜎(𝑎), 𝜎(𝑏)} , untuk setiap (𝑎, 𝑏) ∈ 𝑉 × 𝑉 dan 𝜇(𝑎, 𝑏) = 0 ,  untuk  setiap (𝑎, 𝑏)   ∈   (𝑉 × 𝑉  −  𝐸) .  Dimana 𝜎 merupakan  nilai keanggotaan dari vertek 𝐺 dan 𝜇 merupakan nilai keanggotaan dari edge 𝐺 .
Gambar 1. Graf fuzzy G
Definisi 4. [15] Diberikan graf fuzzy 𝐺 = (𝑉, 𝜎, 𝜇) . Dua vertek berbeda a dan b disebut adjacent kuat jika memenuhi
1 2 𝑚𝑖𝑛{𝜎(𝑎), 𝜎(𝑏)}   ≤  𝜇(𝑎𝑏)
dan disebut adjacent tidak kuat jika memenuhi 1 2 𝑚𝑖𝑛{𝜎(𝑎), 𝜎(𝑏)}   >  𝜇(𝑎𝑏).
Selanjutnya akan diberikan teorema yang menjamin vertek disebut sebagai adjacent kuat.
Teorema 5. Diberikan graf fuzzy 𝐺 . Jika nilai keanggotaan edge 𝜇(𝑎𝑏)   ≥  0.5 , maka kedua vertek yang dihubungkan oleh edge tersebut adalah vertek adjacent kuat.
Bukti. Diambil sebarang edge dengan nilai keanggotaan terkecil yang memenuhi 𝜇(𝑎𝑏)   ≥  0.5 , yaitu 𝜇(𝑎𝑏)   =  0.5 .  Kemudian  1  adalah  nilai  keanggotaan  terbesar  dari  suatu  vertek  yang  memungkinkan. Selanjutnya dengan menggunakan edge 𝜇(𝑎𝑏)   =  0.5 dan vertek dengan nilai keanggotaan terbesar yaitu 1, diperoleh nilai terbesar dari 1 2 𝑚𝑖𝑛{𝜎(𝑎), 𝜎(𝑏)}   → 1 2 𝑚𝑖𝑛{1, 1}   =  0.5
sehingga
1 2 𝑚𝑖𝑛{1, 1}   ≤  0.5  →  0.5  ≤  0.5.
Akibatnya untuk suatu vertek adjacent dengan nilai keanggotaan edge μ(ab) ≥ 0.5 memenuhi
1 2 𝑚𝑖𝑛{𝜎(𝑎), 𝜎(𝑏)}   ≤  𝜇(𝑎𝑏)   →  0.5  ≤  𝜇(𝑎𝑏).
Jadi vertek tersebut adalah vertek adjacent kuat.
■
Definisi  6. [15] Diberikan  himpunan  warna  dasar 𝐶 = 𝐶 1 , 𝐶 2 , … , 𝐶 𝑛 .  Himpunan  fuzzy (𝐶, 𝑓) disebut himpunan  warna  fuzzy,  dimana 𝑓: 𝐶 → [0,1] adalah  fungsi  keanggotaan  dari  warna 𝐶 𝑖 .  Warna 𝑐 𝑖 = (𝑐 𝑖 , 𝑓(𝑐 𝑖 )) adalah warna fuzzy yang sesuai dengan warna dasar 𝑐 𝑖 dan 𝑓 𝑖 adalah fungsi keanggotaannya. Warna dasar adalah warna fuzzy yang nilai keanggotaannya 1.
Gambar 2. Pewarnaan graf fuzzy G
Berdasarkan Gambar 2. diperoleh pewarnaan graf fuzzy G dengan menggunakan 3 warna dasar yaitu merah,  biru,  dan  kuning.  Bilangan  kromatik  dari  graf  fuzzy G adalah  2,    karena  terdapat  dua  warna berbeda dengan nilai keanggotaan 1 yaitu pada 𝑣 1 kuning dan 𝑣 5 biru.
Definisi 7. [13] Diberikan graf fuzzy G = (V, σ, μ). Himpunan 𝐼 𝐷 ⊂ 𝑉 disebut himpunan independen jika 𝜇{𝑎𝑏} < 1 2 𝑚𝑖𝑛{𝜎(𝑎), 𝜎(𝑏)} , untuk setiap 𝑎, 𝑏  ∈   𝐼 𝐷 .
Definisi 8. [13] Diberikan himpunan I(G) adalah semua himpunan independen dari suatu graf fuzzy G =  (V,  σ,  μ).  Pemetaan 𝑓: 𝐼(𝐺) →   [0, 1] disebut  perwarnaan  fraksional  fuzzy  dari  G  jika ∑ 𝑓(𝑆)   ≥  1 𝑣∈𝑆,𝑆∈𝑙(𝐺) untuk  setiap 𝑣 ∈  𝑉 .  Jumlah  nilai  fungsional  dari  semua  himpunan  independen disebut  bobot  pewarnaan  fraksional  fuzzy.  Bobot  terkecil  dari  pewarnaan  fraksional  fuzzy  disebut bilangan kromatik fraksional fuzzy dari G dinotasikan dengan 𝛾𝐹 (𝐺) .
Definisi  9. [13] Perwarnaan  fraksional  fuzzy  dari  graf  fuzzy  G  =(V,  σ,  μ)  dikatakan  teratur  jika ∑ 𝑓(𝑆) =  1 𝑣∈𝑆,𝑆∈𝑙(𝐺) untuk setiap 𝑣 ∈  𝑉 .
Algoritma 10. [13] Diberikan suatu graf fuzzy G = (V, σ, μ). Pewarnaan fraksional fuzzy pada graf fuzzy dapat dilakukan dengan sebagai berikut.
Langkah 1 Cari vertek adjacent kuat pada graf fuzzy G.
Langkah 2 Hilangkan semua edge yang menjadi penghubung vertek adjacent tidak kuat.
Langkah  3 Kemudian,  cari  himpunan  independen  di  antara  vertek  adjacent  kuat.  Karena  graf  yang diberikan berhingga, maka jumlah himpunan independen juga berhingga.
Langkah 4 Untuk setiap himpunan independen dipilih satu warna.
Langkah 5 Bagikan sebagian kecil ke setiap himpunan independen sedemikian hingga
∑ f(S) ≥  1 V∈S,S∈l(G)
Langkah ini dapat dilakukan dengan menyelesaikan program linier berikut:
Minimalkan 𝑧 = 𝑐𝑥 pada 𝐴𝑥  ≥ 1 dan 𝑥 > 0 , di mana 𝑥 = [𝑥 1 , 𝑥 2 , … , 𝑥 𝑛 ] 𝑇 , setiap 𝑥 𝑗 , 𝑗 = 1,2, … , 𝑛 merepresentasikan bobot warna,
1 = [1,1, … ,1] 𝑇 = 𝐶 𝑇
0 = [0,0, … , 0]
kemudian matrik A dapat dibangun dengan cara berikut:
1. Baris matrik merepresentasikan vertek dan kolom matrik merepresentasikan semua himpunan independent.
2. Setiap baris adalah fungsi karakteristik himpunan independen dengan entri 1 pada kolom yang bersesuaian atas vertek dan 0 jika tidak.
sementara z adalah bilangan kromatik fraksional fuzzy dari graf fuzzy G.
Langkah 6 Untuk vertek adjacent tidak kuat, beri warna yang sama dengan vertek yang berdekatan.

## Bahan dan Metode
Survei  diisi  oleh  30  mahasiswa  prodi  matematika  UIN  Sunan  Kalijaga  Yogyakarta  angkatan  2020 menghasilkan sebaran mata kuliah berikut
Tabel 1 Sebaran peserta mata kuliah semester 5 tahun ajaran 2022/2023.
No  Mata Kuliah Notasi Peserta Jml 1 Usul Fiqh 𝑎 1 Semua responden 30 2 Keuangan Islam 𝑎 2 Semua responden 30 3 Ilmu Falak 𝑎 3 Semua responden 30 4 Matematika Keuangan 𝑎 4 Semua responden 30 5 Pengantar Analisis Fungsional 𝑏 1 Awal, Dhiya, Ifa, Silvia 4 6 Fungsi Variabel Kompleks 𝑏 2 Awal, Dhiya, Ifa, Silvia 4 7 Analisis Vektor 𝑏 3 Dhiya, Ifa 2 8 Geometri Analitik 𝑏 4 Dhiya, Ifa 2 9 Teori Bilangan 𝑐 1 Aulia, Awal, Clarissa, Devi, Fauzi, Ilma, Kamal, Maul, Rido, Shofi, Silvia 11 10  Teori Grup Hingga 𝑐 2 Aulia, Clarissa, Shofi 3 11 Logika Fuzzy 𝑐 3 Aulia, Awal, Clarissa, Devi, Fauzi, Ilma, Kamal, Maul, Rido, Shofi, Silvia 11 12  Teori Pengkodean 𝑐 4 Aulia, Clarissa, Fauzi, Ilma, Kamal, Shofi 6 13  Riset Operasi 𝑑 1 Devi, Maul, Rido 3 14  Matematika Biologi 𝑑 2 Devi, Maul, Rido 3
15  Teori Permainan 𝑑 3 Clarissa, Devi, Maul, Rido, Shofi 5 16  Analisis Regresi 𝑒 1 Alfiyah, Alvia, Ana, Annindiya, Ardit, Brenda, Cindy, Evi, Fatma, Linggar, Reni, Reta, Rifa’i, Risma, Viona, Yumna, Zuva 17 17  Analisis Multivariat 𝑒 2 Alfiyah, Alvia, Ana, Annindiya, Ardit, Brenda, Cindy, Evi, Fatma, Linggar, Reni, Reta, Rifa’i, Risma, Viona, Yumna, Zuva 17 18  Analisis Data 𝑒 3 Alfiyah, Ana, Ardit, Fatma, Fauzi, Ilma, Kamal, Reni, Reta, Rifa’i, Risma, Viona, Yumna 13 19  Rancangan Percobaan 𝑒 4 Alfiyah, Ana, Annindiya, Brenda, Cindy, Evi, Fatma, Reta, Viona, Zuva 10 20  Pengantar Statistika Keuangan 𝑒 5 Alfiyah, Alivia, Ana, Annindiya, Ardit, Aulia, Brenda, Cindy, Evi, Fatma, Linggar, Reni, Reta, Rifa’i, Risma, Viona, Yumna, Zuva 18
Keterangan:
• Jumlah pengisi kuisioner mewakili himpunan semesta (𝑥).
• Vertek mewakili mata kuliah dan nilai keanggotaan diperoleh 𝑂𝑟𝑑𝑒𝑟 𝑀𝑎𝑡𝑎 𝐾𝑢𝑙𝑖𝑎ℎ 𝐻𝑖𝑚𝑝𝑢𝑛𝑎𝑛 𝑠𝑒𝑚𝑒𝑠𝑡𝑎 (𝑥)
• Edge mewakili irisan dari setiap mata kuliah dan nilai keanggotaan diperoleh 𝑂𝑟𝑑𝑒𝑟 𝐼𝑟𝑖𝑠𝑎𝑛
𝐻𝑖𝑚𝑝𝑢𝑛𝑎𝑛 𝑠𝑒𝑚𝑒𝑠𝑡𝑎 (𝑥)
Berdasarkan data diatas kemudian menghasilkan graf fuzzy sebagai berikut:

## Hasil dan Pembahasan
Menggunakan data yang telah dihimpun dan direpresentasikan dalam graf pada Gambar 3 di atas, akan dilakukan  pewarnaan  fraksional  fuzzy  pada  graf  fuzzy R .  Proses  pewarnaan  fraksional  menggunakan Algoritma  10  yang  dituliskan  di  atas.  Melalui  pewarnaan  fraksional  tersebut  diharapkan  diperoleh penjadwalan  yang  meminimumkan  jumlah  sesi  yang  dibutuhkan  jika  ruang  yang  diperlukan  untuk melaksanakan ujian sudah ditentukan.
Langkah 1 Cari vertek adjacent kuat pada graf fuzzy R
Langkah  2 Hapus  semua edge yang  menjadi  penghubung  vertek adjacent tidak  kuat  sehingga menghasilkan graf berikut
Gambar 4. Graf fuzzy R’ yang bersesuaian dengan graf fuzzy R.

## Langkah 3 Menentukan himpunan independent pada graf fuzzy R’
Langkah  4 Berikan  warna  dari  masing-masing  himpunan  independent.  Berdasarkan  himpunan independet  yang  diperoleh  pada  Langkah  3,  kemudian  diperoleh  pewarnaan  pada  masing-masing himpunan independen yang direpesentasikan dalam graf pada Gambar 5.
Langkah  5 Menentukan  bilangan  kromatik  fuzzy  berdasarkan  persamaan  warna  dari  himpunan idependent, proses ini dilakukan dengan menggunakan software matlab.
Langkah 6 Terakhir kembalikan edge yang menjadi penghubung vertek adjacent tidak kuat. Pewarnaan fraksional fuzzy pada graf fuzzy R selesai. Hasil pewarnaan fraksional graf fuzzy 𝑅 terlihat dalam Gambar 6.
Gambar 5. Pewarnaan graf fuzzy R’ berdasarkan himpunan independent.
Selanjutnya diasumsikan bahwa ruangan yang tersedia untuk melaksanakan ujian yaitu sebanyak 4, setiap sesi ujian berlangsung selama 2 jam, dan dalam sehari terdapat 2 sesi. Kemudian akan ditentukan jumlah sesi paling minimum untuk penyusunan jadwal ujian. Berikut adalah contoh penyusunan jadwal berdasarkan asumsi tersebut.

## Tabel 2 Jadwal Ujian.
No Mata Kuliah Waktu Pelaksanaan 1 Uslul Fiqh Senin, 5 Desember 2022 (07.00 - 09.00) 2 Keuangan Islam Selasa, 6 Desember 2022 (07.00 - 09.00) 3 Ilmu Falak Rabu, 7 Desember 2022 (07.00 - 09.00) 4 Matematika Keuangan Kamis, 8 Desember 2022 (07.00 - 09.00) 5 Pengantar Analisis Fungsional Senin, 5 Desember 2022 (09.30 - 11.30) 6 Fungsi Variabel Kompleks Selasa, 6 Desember 2022 (09.30 - 11.30) 7 Analisis Vektor Rabu, 7 Desember 2022 (09.30 - 11.30) 8 Geometri Analitik Kamis, 8 Desember 2022 (09.30 - 11.30) 9 Teori Bilangan Rabu, 7 Desember 2022 (09.30 - 11.30) 10 Teori Grup Hingga Selasa, 6 Desember 2022 (09.30 - 11.30) 11 Logika Fuzzy Kamis, 8 Desember 2022 (09.30 - 11.30) 12 Teori Pengkodean Senin, 5 Desember 2022 (09.30 - 11.30) 13 Riset Operasi Senin, 5 Desember 2022 (09.30 - 11.30) 14 Matematika Biologi Selasa, 6 Desember 2022 (09.30 - 11.30) 15 Teori Permainan Kamis, 8 Desember 2022 (09.30 - 11.30) 16 Analisis Regresi Jumat, 9 Desember 2022 (07.00 - 09.00) 17 Analisis Multivariat Senin, 5 Desember 2022 (09.30 - 11.30) 18 Analisis Data Rabu, 6 Desember 2022 (09.30 - 11.30) 19 Rancangan Percobaan Jumat, 9 Desember 2022 (07.00 - 09.00) 20 Pengantar Statistika Keuangan Kamis, 8 Desember 2022 (09.30 - 11.30)

## Kesimpulan
Penyusunan  jadwal  menggunakan  pewarnaan  fraksional  fuzzy  menghasilkan  solusi  optimum  yang tidak tunggal. Hal tersebut mungkin terjadi dikarenakan dalam menentukan nilai keanggotaan pada graf  fuzzy R masih  kurang  tepat.  Sehingga  masih  diperlukan  metode  tertentu  untuk  menghasilkan pewarnaan fraksional fuzzy dengan hasil yang lebih sesuai.

## Referensi
[1] L. A. Zadeh, “Fuzzy Sets,” California Information and Contro, pp. 338-353, 1965.
[2] A. Kauffman, “Introduction a la Theorie des Sous-emsembles,” Mansson et Cie, p. 1:1973, 1973.
[3] A. Rosenfeld, “Fuzzy Graphs, Fuzzy sets and their application,” Academic Press, pp. 77-95, 2015.
[4] J. N. Maderson, “Operation on Fuzyy Graphs,” Inf Sci, Vol. %1 dari %2iii-iv, no. 79, pp. 159-170, 1994.
[5] M. S. Sunitha, “Fuzzy Graphs Theory : A Survey,” Ann Pure Appl Math, no. 4, pp. 92-110, 2013.
[6] A. Nagoorgani, “Isomorphism on Fuzzy Graphs,” Int J Comput Math Sci, vol. xi, no. 2, pp. 835-831, 2008.
[7] K. R. Bhutani, “Strong Arcs in Fuzzy Graphs,” Inf Sci, no. 152, pp. 103-109, 2013.
[8] M. Ananthanarayanan, “Fuzzy Graph Coloring Using α-cut,” Int J Eng Appl Sci, vol. x, no. 4, pp. 23-28, 2015.
[9] K. Radha, “On Lexicographic Product of Two Fuzzy Graphs,” Int J Fuzzy Math Arch, vol. ii, no. 7, pp. 169-176, 2015.
[10] S. Samanta, “Fuzzy Planar Graphs,” IEEE Trans Fuzzy Syst, no. 23, pp. 1936-1942, 2015.
[11] I. Rosyida, “A New Approach Determining Fuzzy Chromatic Number of Fuzzy Graphs,” J Intell Fuzzy Sets, no. 28, pp. 2331-2341, 2015.
[12] I. Rosyida, “Fuzzy Chromatic Number of Union of Fuzzy Graphs: An Algoritma, Properties, and Its Application,” Fuzzy Sets Syst, 2019.
[13] T.  Mahapatra,  “Fuzzy  Fractional  Coloring  of  Guzzy  Graph  with  its  Application,” Journal  of  Ambient  Intelligence  and Humanized Computing, p. 5771 –5784, 2020.
[14]  A. Munandar, Pengantar Matematika Diskrit dan Teori Graf, Sleman: Depublish, 2022.
[15]  S . Samanta, “Fuzzy Colouring of Fuzzy Graphs,” Afrika Math, p. 27:37 –50, 2016.